|
|
|
|
Introducción La administración de un gran conjunto de datos y su almacenamiento en ficheros es una tarea vital para los sistemas informáticos. El ordenador debe recuperar un elemento del fichero y cargarlo en memoria principal, antes de ser procesado. Una organización inteligente de los datos en el fichero puede hacer que el sistema informático minimize el número de accesos al dispositivo secundario. De tal manera de optimizar su funcionamiento. Como una propuesta inicial para la ordenación lógica de datos se presenta la estructura de datos Arbol Binario de Búsqueda (ABB). El cual mediante el uso de punteros permite establecer un orden de relación entre los datos sin importar su orden físico. Recordemos que en un ABB cada nodo contiene un dato, así como punteros a los subarboles izquierdo y derecho. El primer nodo se denomina raíz del árbol y aquellos nodos que están al final de las ramas se llaman hojas. Para buscar un dato en el ABB se debía recorrer el árbol desde su raíz y comparar el dato buscado con el dato existente en el nodo. Si era menor al dato en el nodo se buscaba en el subarbol izquierdo y si era mayor en el subarbol derecho. Así recursivamente, hasta encontrarlo o encontrarse con una rama vacía. Estos árboles binarios tan simples, aunque fáciles de entender y de implementar, tienen algunas desventajas en la práctica. Si los datos no están bien distribuidos o son añadidos de forma no aleatoria, el árbol puede resultar bastante asimétrico, dando lugar a un aumento bastante amplio en el tiempo total de recorrido. Como solución ha este problema se presentó la estructura de datos Arbol Binario Balanceado (AVL), el cual tenía las mismas propiedades que un ABB pero además debía satisfacer que las alturas de los subarboles izquierdo y derecho no difirieran en más de uno. Esto se logra utilizando herramientas de balanceo que se denominan rotaciones. Ahora retomando nuestra idea inicial de tener una gran cantidad de datos almacenada en algún dispositivo secundario (HDD, Diskette, CD, etc.). Los ABB y los AVL deben realizar un acceso al disco cada vez que cargan en memoria un dato del fichero. Lo cual es bastante costoso si consideramos que el tiempo de búsqueda en una cantidad N de datos es del orden de log2N más el tiempo de cada acceso al disco (Un acceso al diskette, por ejemplo, demora alrededor de 1 seg.) Para optimizar esta situación usaremos la estructura de datos Arbol B y sus métodos de mantenimiento. El Método de Trabajo de los Arboles B sobre los datos en memoria secundaria es abordado en el apartado Funcionamiento de un Arbol B.
|
|
|||||||||||||
|
|
|
|
|
| Introducción | - | Funcionamiento | - | ¿Qué es un Arbol B? | - | Búsqueda | - | Inserción | |
|
|
| Borrado | - | Costos | - | Casos especiales | - | Conclusión | - | Bibliografía | |
|
|
|
|
| . | |
|
Web diseñado y creado por |
Copyright © 2001 |
Homepage
