Árboles B y árboles B+

Los árboles B y los árboles B+ son casos especiales de árboles de búsqueda. Un árbol de búsqueda es un tipo de árbol que sirve para guiar la búsqueda de un registro, dado el valor de uno de sus campos. Los índices multinivel de la sección anterior pueden considerarse como variaciones de los árboles de búsqueda. Cada bloque o nodo del índice multinivel puede tener hasta $p$ valores del campo de indexación y $p$ punteros. Los valores del campo de indexación de cada nodo guían al siguiente nodo (que se encuentra en otro nivel), hasta llegar al bloque del fichero de datos que contiene el registro deseado. Al seguir un puntero, se va restringiendo la búsqueda en cada nivel a un subárbol del árbol de búsqueda, y se ignoran todos los nodos que no estén en dicho subárbol.

Los árboles de búsqueda difieren un poco de los índices multinivel. Un árbol de búsqueda de orden $p$ es un árbol tal que cada nodo contiene como mucho $p-1$ valores del campo de indexación y $p$ punteros:

$$(P_{1},K_{1},P_{2},K_{2},\ldots, P_{q-1},K_{q-1},P_{q})$$

donde $q\leq p$, cada $P_{i}$ es un puntero a un nodo hijo y cada $K_{i}$ es un valor de búsqueda proveniente de algún conjunto ordenado de valores. Se supone que todos los valores de búsqueda son únicos. Un árbol de búsqueda debe cumplir, en todo momento, las siguientes restricciones:

1. Dentro de cada nodo: $K_{1}<K_{2}< \ldots K_{q-1}$.

2. Para todos los valores $X$ del subárbol al que apunta $P_{i}$, se tiene: $K_{i-1}<X<K_{i}$ para $1<i<q$, $X<K_{i}$ para $i=1$ y $K_{i-1}<X$ para $i=q$.

Al buscar un valor $X$ siempre se sigue el puntero $P_{i}$ apropiado de acuerdo con las condiciones de la segunda restricción. Para insertar valores de búsqueda en el árbol y eliminarlos, sin violar las restricciones anteriores, se utilizan algoritmos que no garantizan que el árbol de búsqueda esté equilibrado (que todas las hojas estén al mismo nivel). Es importante mantener equilibrados los árboles de búsqueda porque esto garantiza que no habrá nodos en niveles muy profundos que requieran muchos accesos a bloques durante una búsqueda. Además, las eliminaciones de registros pueden hacer que queden nodos casi vacíos, con lo que hay un desperdicio de espacio importante que también provoca un aumento en el número de niveles.

El árbol B es un árbol de búsqueda, con algunas restricciones adicionales, que resuelve hasta cierto punto los dos problemas anteriores. Estas restricciones adicionales garantizan que el árbol siempre estará equilibrado y que el espacio desperdiciado por la eliminación, si lo hay, nunca será excesivo. Los algoritmos para insertar y eliminar se hacen más complejos para poder mantener estas restricciones. No obstante, la mayor parte de las inserciones y eliminaciones son procesos simples, se complican sólo en circunstancias especiales: cuando se intenta insertar en un nodo que está lleno o cuando se intenta borrar en un nodo que está ocupado hasta la mitad.

Un árbol B de orden $p$ se define del siguiente modo:

1. La estructura de cada nodo interno tiene la forma:
   
   $$(P_{1},(K_{1},Pr_{1}), P_{2},(K_{2},Pr_{2}), P_{3},(K_{3},Pr_{3}), \ldots P_{q-1},(K_{q-1},Pr_{q-1}),P_{q})$$
   
   
   donde $q\leq p$. Cada $P_{i}$ es un puntero a un nodo interno del árbol y cada $Pr_{i}$ es un puntero al registro del fichero de datos que tiene el valor $K_{i}$ en el campo de búsqueda o de indexación.

2. Dentro de cada nodo se cumple: $K_{1}<K_{2}< \ldots K_{q-1}$.

3. Para todos los valores $X$ del campo de indexación del subárbol al que apunta $P_{i}$, se cumple: $K_{i-1}<X<K_{i}$ para $1<i<q$, $X<K_{i}$ para $i=1$ y $K_{i-1}<X$, para $i=q$.

4. Cada nodo tiene, como mucho, $p$ punteros a nodos del árbol.

5. Cada nodo, excepto la raíz y las hojas, tiene, al menos, $\lceil p/2 \rceil$ punteros a nodos del árbol. El nodo raíz tiene, como mínimo, dos punteros a nodos del árbol, a menos que sea el único nodo del árbol.

6. Un nodo con $q$ punteros a nodos, $q\leq p$, tiene $q-1$ valores del campo de indexación.

7. Todos los nodos hoja están al mismo nivel. Los nodos hoja tienen la misma estructura que los nodos internos, pero los punteros a nodos del árbol son nulos.

Como se puede observar, en los árboles B todos los valores del campo de indexación aparecen alguna vez en algún nivel del árbol, junto con un puntero al fichero de datos.

En un árbol B+ los punteros a datos se almacenan sólo en los nodos hoja del árbol, por lo cual, la estructura de los nodos hoja difiere de la de los nodos internos. Los nodos hoja tienen una entrada por cada valor del campo de indexación, junto con un puntero al registro del fichero de datos. Estos nodos están enlazados para ofrecer un acceso ordenado a los registros a través del campo de indexación. Los nodos hoja de un árbol B+ son similares al primer nivel (nivel base) de un índice. Los nodos internos del árbol B+ corresponden a los demás niveles del índice. Algunos valores del campo de indexación se repiten en los nodos internos del árbol B+ con el fin de guiar la búsqueda.

En un árbol B+ de orden $p$ la estructura de un nodo interno es la siguiente:

1. Todo nodo interno es de la forma:
   
   $$(P_{1},K_{1},P_{2},K_{2},P_{3},K_{3}, \ldots P_{q-1},K_{q-1},P_{q})$$
   
   
   donde $q\leq p$. Cada $P_{i}$ es un puntero a un nodo interno del árbol.

2. Dentro de cada nodo interno se cumple: $K_{1}<K_{2}< \ldots K_{q-1}$.

3. Para todos los valores $X$ del campo de indexación del subárbol al que apunta $P_{i}$, se cumple: $K_{i-1}<X \leq K_{i}$ para $1<i<q$, $X \leq K_{i}$ para $i=1$ y $K_{i-1}<X$ para $i=q$.

4. Cada nodo interno tiene, como mucho, $p$ punteros a nodos del árbol.

5. Cada nodo interno, excepto la raíz, tiene, al menos, $\lceil p/2 \rceil$ punteros a nodos del árbol. El nodo raíz tiene, como mínimo, dos punteros a nodos del árbol si es un nodo interno.

6. Un nodo interno con $q$ punteros a nodos, $q\leq p$, tiene $q-1$ valores del campo de indexación.

La estructura de los nodos hoja de un árbol B+ de orden $p$ es la siguiente:

1. Todo nodo hoja es de la forma:
   
   $$((K_{1},Pr_{1}), (K_{2},Pr_{2}), (K_{3},Pr_{3}), \ldots (K_{q-1},Pr_{q-1}),P_{siguiente})$$
   
   
   donde $q\leq p$. Cada $Pr_{i}$ es un puntero al registro de datos que tiene el valor $K_{i}$ en el campo de indexación, y $P_{siguiente}$ es un puntero al siguiente nodo hoja del árbol.

2. Dentro de cada nodo hoja se cumple: $K_{1}<K_{2}< \ldots K_{q-1}$, $q\leq p$.

3. Cada nodo hoja tiene, al menos, $\lfloor p/2 \rfloor$ valores.

4. Todos los nodos hoja están al mismo nivel.

Como las entradas en los nodos internos de los árboles B+ contienen valores del campo de indexación y punteros a nodos del árbol, pero no contienen punteros a los registros del fichero de datos, es posible ``empaquetar" más entradas en un nodo interno de un árbol B+ que en un nodo similar de un árbol B. Por tanto, si el tamaño de bloque (nodo) es el mismo, el orden $p$ será mayor para el árbol B+ que para el árbol B. Esto puede reducir el número de niveles del árbol B+, mejorándose así el tiempo de acceso. Como las estructuras de los nodos internos y los nodos hoja de los árboles B+ son diferentes, su orden $p$ puede ser diferente.

Se ha demostrado por análisis y simulación que después de un gran número de inserciones y eliminaciones aleatorias en un árbol B, los nodos están ocupados en un 69% cuando se estabiliza el número de valores del árbol. Esto también es verdadero en el caso de los árboles B+. Si llega a suceder esto, la división y combinación de nodos ocurrirá con muy poca frecuencia, de modo que la inserción y la eliminación se volverán muy eficientes.

Cuando los árboles se definen sobre un campo no clave, los punteros a datos pasan a ser punteros a bloques de punteros a datos (se añade un nivel de indirección).