ARBOL B

Estructuras de Datos No Lineales

 
Árboles B:
Los árboles B son estructuras no lineales que fueron introducidos por R. Bayer y E. McCreight en 1972, con el principal objetivo de mejorar el tiempo de acceso en estructuras de datos manejadas en memoria externa.
Los árboles B son una generalización de los árboles balanceados, con una estructura jerárquica que beneficia considerablemente labúsqueda de un elemento en específico, reduciendo el número de nodos o archivos accesados.
En un árbol B se debe procurar:
1. Conservar la altura del árbol al mínimo, por lo que no deben existir subárboles vacíos al interior del árbol.
2. Que todos los nodos, excepto la raíz, tengan un mínimo número de llaves (quizás la mitad del máximo).
3. Que todas las hojas se mantengan al mismo nivel,garantizando así que las búsquedas se consigan con aproximadamente el mínimo número de accesos.
 
Luego, un árbol B de "orden d" se puede formalizar de la siguiente forma:
1. Cada página (nodo), exceptuando la raíz contiene entre d y 2d elementos.
2. Cada página (nodo), excepto la página raíz y las páginas hojas, tienen entre d+1 y 2d+1 descendientes. Se utiliza m para expresar el número deelementos pos cada página.
3. La página raíz posee al menos dos descendientes.
4. Las páginas hojas están todas al mismo nivel.
___________________________________
La inserción en árboles B: Para insertar elementos en un árbol B se debe:
1. Determinar el máximo y mínimo número de elementos por nodo, de acuerdo al orden del árbol B:
Key mínimo = d
Key máximo = 2*d
2. Hacer una búsqueda enel árbol B del lugar donde debe insertarse la llave.
3. Toda inserción en un árbol B tiene lugar siempre en una hoja del árbol. Si la hoja no está llena, la llave es añadida en ésa hoja.
4. Si el nodo hoja está lleno, entonces, éste se divide en dos (requiriendo la creación de un nuevo nodo) y la llave de valor medio se promueve como padre de los nodos. Si el nodo padre también está lleno, serepite el proceso, teniendo cuidado de mantener el orden de las llaves entre los subárboles.
 
Ejemplo de inserción en un árbol B de orden 2:
Para un árbol B de orden 2 (d=2) se utilizarán nodos que podrán contener hasta d (2) elementos como mínimo y 2*d (2*2=4) elementos como máximo.
Insertemos los siguientes elementos en el árbol:
10 – 20 – 5 – 25 – 30 – 35 – 34 – 9 – 40 – 45 – 18 – 2 –70 – 65 – 27 – 50 – 42 – 17 – 13 – 1 – 54 – 12 – 22 – 67
Paso 1) Para el primer paso se insertan los elementos en forma ordenada en el primer nodo hasta que se llene y se deba insertar uno que sobrepase el número de elementos máximo por nodo. Como se muestra en el ejemplo, se insertan los elementos 10, 20, 5 y 25 hasta que llega el número 30, que produce que el nodo se rebalse y se aumente en unnivel como se muestra en el paso 2.

Paso 2) La inserción del número 30 produce que el nodo se rompa en dos y que el número que se encuentra en el centro de todos pase a se padre, como se aprecia, al ingresar el número 30 es el número 20 el que queda en el centro de los 5 (los cuatro del nodo y el que viene ingresando), por lo que es el 20 el que se transforma en padre de los demás nodos. Secontinúa insertando hasta que llega el 40, que produce un nuevo quiebre del nodo, pasando el 34 al nodo padre.

Paso 3) Como se aprecia, al ingresar el 40, el 34 pasa al nodo padre, separándose el nodo formado por los números 25, 30, 34 y 35. Lo mismo ocurre al ingresar el número 2, pasando al paso 4.

 
Paso 4) Se continúa la inserción hasta que llega el número 65, que produce un nuevo quiebre yque el 45 llegue al nodo padre.

Paso 5) Se continúa la inserción de elementos hasta que llega el número 12, lo que provoca que el 13 pase al nodo padre que en este momento esta lleno, por lo que llegamos a la situación vista en el paso 1, donde el nodo que esta lleno, al recibir otro elemento se divide en dos, volviéndose a subir un nivel, como se aprecia en el paso 6.

 
Paso 6) La...