Árbol B

La literatura sobre árboles B no es uniforme en su terminología. ^{[ 10 ]}

Bayer y McCreight (1972), ^{[ 5 ]} Comer (1979), ^{[ 2 ]} y otros definen el orden de un árbol B como el número mínimo de claves en un nodo que no es la raíz. Folk y Zoellick ^{[ 11 ]} señalan que la terminología es ambigua porque el número máximo de claves no está claro. Un árbol B de orden 3 podría contener un máximo de 6 claves o un máximo de 7 claves. Knuth (1998) evita el problema definiendo el orden como el número máximo de hijos (que es uno más que el número máximo de claves). ^{[ 9 ]}

El término hoja también es inconsistente. Bayer y McCreight (1972) ^{[ 5 ]} consideraron que el nivel de hoja era el nivel más bajo de claves, pero Knuth lo consideró un nivel por debajo de las claves más bajas. ^{[ 11 ]} Existen muchas opciones de implementación posibles. En algunos diseños, las hojas pueden contener el registro de datos completo; en otros, pueden contener solo punteros al registro de datos. Estas opciones no son fundamentales para la idea de un árbol B. ^{[ 12 ]}

Para simplificar, la mayoría de los autores asumen que existe un número fijo de claves que caben en un nodo. La suposición básica es que tanto el tamaño de la clave como el del nodo son fijos. En la práctica, se pueden emplear claves de longitud variable. ^{[ 13 ]}

Al igual que otros árboles, los árboles B se pueden representar como una colección de tres tipos de nodos: raíz , interno (también llamado interior) y hoja .

Tenga en cuenta las siguientes definiciones de variables:

• K - Número máximo de claves de búsqueda potenciales para cada nodo en un árbol B. (Este valor es constante en todo el árbol).
• pt _i - El puntero a un nodo hijo que inicia un subárbol.
• pr _i - El puntero a un registro que almacena los datos.
• k _i - La clave de búsqueda en el índice de nodo basado en cero i .

En los árboles B, se mantienen las siguientes propiedades para estos nodos:

• Si k _i existe en cualquier nodo de un árbol B, entonces k _{i -1} existe en ese nodo donde${\displaystyle i\geq 1}$.
• Todos los nodos hoja tienen el mismo número de ancestros (es decir, todos están a la misma profundidad).

Cada nodo interno en un árbol B tiene el siguiente formato:

Cada nodo hoja en un árbol B tiene el siguiente formato:

Los límites de los nodos se resumen en la tabla siguiente:

Para mantener el rango predefinido de nodos secundarios, los nodos internos pueden unirse o dividirse.

Por lo general, el número de claves se elige para que varíe entre d y${\displaystyle 2d}$, donde d es el número mínimo de claves, y${\displaystyle d+1}$es el grado mínimo o factor de ramificación del árbol. Un factor de 2 garantiza que los nodos se puedan dividir o combinar.

Si un nodo interno tiene${\displaystyle 2d}$claves, luego agregar una clave a ese nodo se puede lograr dividiendo la hipotética${\displaystyle 2d+1}$un nodo clave en dos d nodos clave y moviendo la clave que habría estado en el medio al nodo padre. Cada nodo dividido tiene el número mínimo requerido de claves. De manera similar, si un nodo interno y su vecino tienen cada uno d ​​claves, entonces se puede eliminar una clave del nodo interno combinándola con su vecino. Eliminar la clave haría que el nodo interno tuviera${\displaystyle d-1}$claves; unirse al vecino agregaría d claves más una clave adicional tomada del padre del vecino. El resultado es un nodo completamente lleno de${\displaystyle 2d}$llaves.

Un árbol B se mantiene equilibrado después de la inserción dividiendo un nodo que podría estar sobrecargado, de${\displaystyle 2d+1}$claves, en dos hermanos de d claves e insertando la clave de valor medio en el padre. La profundidad solo aumenta cuando la raíz se divide, manteniendo el equilibrio. De manera similar, un árbol B se mantiene equilibrado después de la eliminación mediante la fusión o redistribución de claves entre hermanos para mantener el mínimo de d claves para nodos que no son la raíz. Una fusión reduce el número de claves en el padre, lo que potencialmente lo obliga a fusionar o redistribuir claves con sus hermanos, y así sucesivamente. El único cambio en la profundidad ocurre cuando la raíz tiene dos hijos, de d y (transicionalmente)${\displaystyle d-1}$claves, en cuyo caso los dos hermanos y el padre se fusionan, reduciendo la profundidad en uno.

Esta profundidad aumentará lentamente a medida que se agreguen elementos al árbol, pero un aumento en la profundidad general es poco frecuente y da como resultado que todos los nodos hoja estén un nodo más lejos de la raíz.

Debido a que se permite un rango de nodos hijos, los árboles B no necesitan reequilibrarse con tanta frecuencia como otros árboles de búsqueda autoequilibrados, pero pueden desperdiciar algo de espacio ya que los nodos no están completamente llenos.

Los árboles B ofrecen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los datos de un nodo supera ampliamente el tiempo de procesamiento, ya que el costo de acceso puede amortizarse entre múltiples operaciones dentro del nodo. Esto suele ocurrir cuando los datos del nodo se almacenan en almacenamiento secundario , como discos duros . Al maximizar el número de claves dentro de cada nodo interno , la altura del árbol disminuye y se reduce el número de accesos costosos a los nodos. Además, el reequilibrio del árbol se produce con menos frecuencia. El número máximo de nodos hijos depende de la información que debe almacenarse para cada uno y del tamaño de un bloque de disco completo o un tamaño análogo en el almacenamiento secundario. Si bien los árboles B de 2 a 3 nodos son más fáciles de explicar, los árboles B prácticos que utilizan almacenamiento secundario requieren un gran número de nodos hijos para mejorar el rendimiento.

El término árbol B puede referirse a un diseño específico o a una clase general de diseños. En sentido estricto, un árbol B almacena las claves en sus nodos internos, pero no necesariamente en los registros de las hojas. La clase general incluye variantes como el árbol B+ , el árbol B ^* y el árbol B ^{*+ .}

• En el árbol B+ , los nodos internos no almacenan punteros a registros; por lo tanto, todos los punteros a registros se almacenan en los nodos hoja. Además, un nodo hoja puede incluir un puntero al siguiente nodo hoja para acelerar el acceso secuencial. ^{[ 2 ]} Debido a que los nodos internos del árbol B+ tienen menos punteros, cada nodo puede contener más claves, lo que hace que el árbol sea menos profundo y, por lo tanto, más rápido de buscar.
• El árbol B ^* equilibra más nodos internos vecinos para mantener los nodos internos más densamente empaquetados. ^{[ 2 ]} Esta variante asegura que los nodos que no son raíz estén al menos 2/3 llenos en lugar de 1/2. ^{[ 15 ]} Como la parte más costosa de la operación de insertar el nodo en un árbol B es dividir el nodo, los árboles B ^* se crean para posponer la operación de división tanto como sea posible. ^{[ 16 ]} Para mantener esto, en lugar de dividir inmediatamente un nodo cuando se llena, sus claves se comparten con un nodo adyacente. Esta operación de desbordamiento es menos costosa que la división porque solo requiere mover las claves entre nodos existentes, no asignar memoria para uno nuevo. ^{[ 16 ]} Para la inserción, primero se verifica si el nodo tiene algo de espacio libre y, de ser así, la nueva clave simplemente se inserta en el nodo. Sin embargo, si el nodo está lleno (tiene m − 1 claves, donde m es el orden del árbol como el número máximo de punteros a subárboles desde un nodo), es necesario comprobar si existe el hermano derecho y si tiene espacio libre. Si el hermano derecho tiene j < m − 1 claves, entonces las claves se redistribuyen entre los dos nodos hermanos de la manera más equitativa posible. Para ello, m − 1 claves del nodo actual, la nueva clave insertada, una clave del nodo padre y j claves del nodo hermano se consideran como un arreglo ordenado de m + j + 1 claves. El arreglo se divide por la mitad de manera que ⌊ ( m + j + 1)/2 ⌋ las claves más bajas permanecen en el nodo actual, la siguiente clave (la del medio) se inserta en el padre y el resto va al hermano derecho. ^{[ 16 ]} (La clave recién insertada podría terminar en cualquiera de los tres lugares.) La situación cuando el hermano derecho está lleno y el izquierdo no lo está es análoga. ^{[ 16 ]} Cuando ambos nodos hermanos están llenos, entonces los dos nodos (nodo actual y un hermano) se dividen en tres, y una clave más se desplaza hacia arriba en el árbol hasta el nodo padre. ^{[ 16 ]} Si el padre está lleno, entonces la operación de desbordamiento/división se propaga hacia el nodo raíz. ^{[ 16 ]} Sin embargo, eliminar nodos es algo más complejo que insertar.
• El árbol B ^{*+ combina las características principales} del árbol B+ y del árbol B ^* . ^{[ 17 ]}
• Los árboles B se pueden convertir en árboles de estadísticas de orden para permitir búsquedas rápidas del enésimo registro en el orden de la clave, o contar el número de registros entre dos registros cualesquiera, y varias otras operaciones relacionadas. ^{[ 18 ]}

Los algoritmos de ordenación y búsqueda se pueden caracterizar por el número de operaciones de comparación que deben realizarse utilizando la notación de orden . Una búsqueda binaria en una tabla ordenada con N registros, por ejemplo, se puede realizar en aproximadamente ⌈ log ₂ N ⌉ comparaciones. Si la tabla tuviera 1.000.000 de registros, entonces un registro específico podría localizarse con como máximo 20 comparaciones: ⌈ log ₂ (1.000.000) ⌉ = 20 .

Históricamente, las bases de datos grandes se han almacenado en discos duros. El tiempo necesario para leer un registro en un disco duro supera con creces el tiempo necesario para comparar las claves una vez que el registro está disponible, debido al tiempo de búsqueda y al retardo de rotación. El tiempo de búsqueda puede ser de 0 a 20 milisegundos o más, y el retardo de rotación es, en promedio, aproximadamente la mitad del período de rotación. Para un disco de 7200 RPM, el período de rotación es de 8,33 milisegundos. Para un disco como el Seagate ST3500320NS, el tiempo de búsqueda de pista a pista es de 0,8 milisegundos y el tiempo de búsqueda de lectura promedio es de 8,5 milisegundos. ^{[ 19 ]} Para simplificar, supongamos que la lectura del disco tarda unos 10 milisegundos.

En el ejemplo anterior, el tiempo necesario para localizar un registro entre un millón sería de 20 lecturas de disco, cada una de las cuales tardaría 10 milisegundos, lo que equivale a 0,2 segundos.

El tiempo de búsqueda se reduce porque los registros individuales se agrupan en un bloque de disco . Un bloque de disco puede tener un tamaño de 16 kilobytes. Si cada registro ocupa 160 bytes, se podrían almacenar 100 registros en cada bloque. El tiempo de lectura del disco mencionado anteriormente corresponde a un bloque completo. Una vez que el cabezal del disco está en posición, se pueden leer uno o más bloques con poca demora. Con 100 registros por bloque, las últimas 6 comparaciones aproximadamente no requieren ninguna lectura del disco, ya que todas se encuentran dentro del último bloque leído.

Para acelerar aún más la búsqueda, debe reducirse el tiempo necesario para realizar las primeras 13 o 14 comparaciones (cada una de las cuales requería acceso al disco).

Un índice B-tree puede utilizarse para mejorar el rendimiento. Este tipo de índice crea una estructura de árbol multinivel que divide la base de datos en bloques o páginas de tamaño fijo. Cada nivel del árbol permite enlazar las páginas mediante una dirección, de modo que una página (conocida como nodo o página interna) haga referencia a otra, con las páginas hoja en el nivel más bajo. Una página suele ser el punto de partida del árbol, o la "raíz". Aquí es donde comienza la búsqueda de una clave específica, recorriendo una ruta que termina en una página hoja. La mayoría de las páginas de esta estructura son páginas hoja que hacen referencia a filas específicas de la tabla.

Debido a que cada nodo (o página interna) puede tener más de dos hijos, un índice B-tree generalmente tendrá una altura menor (la distancia desde la raíz hasta la hoja más alejada) que un árbol de búsqueda binaria. En el ejemplo anterior, las lecturas iniciales del disco redujeron el rango de búsqueda a la mitad. Esto se puede mejorar creando un índice auxiliar que contenga el primer registro de cada bloque de disco (a veces llamado índice disperso ). Este índice auxiliar tendría un tamaño del 1 % del de la base de datos original, pero se puede buscar rápidamente. Encontrar una entrada en el índice auxiliar nos indicaría qué bloque buscar en la base de datos principal; después de buscar en el índice auxiliar, solo tendríamos que buscar en ese bloque de la base de datos principal, a costa de una lectura de disco adicional.

En el ejemplo anterior, el índice contendría 10 000 entradas y requeriría como máximo 14 comparaciones para obtener un resultado. Al igual que en la base de datos principal, las últimas seis comparaciones del índice auxiliar se ubicarían en el mismo bloque de disco. La búsqueda en el índice podría realizarse en aproximadamente ocho lecturas de disco, y el acceso al registro deseado podría efectuarse en nueve lecturas.

La creación de un índice auxiliar puede repetirse para crear un índice auxiliar del índice auxiliar. Esto crearía un índice auxiliar-auxiliar que solo necesitaría 100 entradas y cabría en un bloque de disco.

En lugar de leer 14 bloques de disco para encontrar el registro deseado, solo necesitamos leer 3. Este bloqueo es la idea central detrás de la creación del árbol B, donde los bloques de disco forman una jerarquía de niveles que componen el índice. Al leer y buscar el primer (y único) bloque del índice auxiliar (la raíz del árbol), se identifica el bloque correspondiente en el índice auxiliar del nivel inferior. Al leer y buscar ese bloque del índice auxiliar, se identifica el bloque que se debe leer hasta que el último nivel, conocido como nivel hoja, identifica un registro en la base de datos principal. En lugar de 150 milisegundos, solo necesitamos 30 milisegundos para obtener el registro.

Los índices auxiliares han transformado el problema de búsqueda de una búsqueda binaria que requiere aproximadamente log ₂ N lecturas de disco a una que requiere solo log _b N lecturas de disco, donde b es el factor de bloqueo (el número de entradas por bloque: b = 100 entradas por bloque en nuestro ejemplo; log ₁₀₀ 1.000.000 = 3 lecturas).

En la práctica, si la base de datos principal se consulta con frecuencia, el índice auxiliar y gran parte del índice auxiliar pueden residir en una caché de disco , por lo que no implicarían una lectura de disco. El árbol B sigue siendo la implementación de índice estándar en casi todas las bases de datos relacionales , y muchas bases de datos no relacionales también lo utilizan. ^{[ 20 ]}

Si la base de datos no cambia, compilar el índice es sencillo y no es necesario modificarlo. Si hay cambios, la gestión de la base de datos y su índice requiere cálculos adicionales.

Eliminar registros de una base de datos es relativamente fácil. El índice puede permanecer igual y el registro simplemente puede marcarse como eliminado. La base de datos se mantiene ordenada. Si hay un gran número de eliminaciones diferidas , la búsqueda y el almacenamiento se vuelven menos eficientes. ^{[ 21 ]}

Las inserciones pueden ser muy lentas en un archivo secuencial ordenado, ya que es necesario crear espacio para el registro que se va a insertar. Insertar un registro antes del primero requiere desplazar todos los registros una posición hacia abajo. Esta operación resulta demasiado costosa para ser práctica. Una solución consiste en dejar espacios. En lugar de agrupar densamente todos los registros en un bloque, este puede tener espacio libre para permitir inserciones posteriores. Estos espacios se marcarían como si fueran registros "eliminados".

Tanto las inserciones como las eliminaciones son rápidas siempre que haya espacio disponible en un bloque. Si una inserción no cabe en el bloque, se debe buscar espacio libre en algún bloque cercano y ajustar los índices auxiliares. Lo ideal es que haya suficiente espacio disponible cerca para minimizar la reorganización de bloques. Como alternativa, se pueden usar algunos bloques de disco fuera de secuencia. ^{[ 20 ]}

El árbol B utiliza todas las ideas descritas anteriormente. En particular, un árbol B:

• Mantiene las claves en orden ordenado para el recorrido secuencial.
• Utiliza un índice jerárquico para minimizar el número de lecturas de disco.
• Utiliza bloques parcialmente llenos para acelerar las inserciones y eliminaciones.
• Mantiene el índice equilibrado con un algoritmo recursivo.

Además, un árbol B minimiza el desperdicio al asegurar que los nodos internos estén al menos medio llenos. Un árbol B puede manejar un número arbitrario de inserciones y eliminaciones. ^{[ 20 ]}

La búsqueda es similar a la de un árbol de búsqueda binaria. Partiendo de la raíz, el árbol se recorre recursivamente de arriba abajo. En cada nivel, la búsqueda reduce su campo de visión al puntero hijo (subárbol) cuyo rango incluye el valor buscado. El rango de un subárbol está definido por los valores, o claves, contenidos en su nodo padre. Estos valores límite también se conocen como valores de separación.

La búsqueda binaria se utiliza normalmente (aunque no necesariamente) dentro de los nodos para encontrar los valores de separación y el árbol hijo de interés.

Todas las inserciones comienzan en un nodo hoja. Para insertar un nuevo elemento, busque en el árbol el nodo hoja donde se debe agregar el nuevo elemento. Inserte el nuevo elemento en ese nodo siguiendo estos pasos:

1. Si el nodo contiene menos elementos de los permitidos, hay espacio para el nuevo elemento. Inserte el nuevo elemento en el nodo, manteniendo el orden de los elementos existentes.
2. De lo contrario, el nodo está lleno, divídalo equitativamente en dos nodos, de la siguiente manera:
   1. Se elige una única mediana entre los elementos de la hoja y el nuevo elemento que se está insertando.
   2. Los valores inferiores a la mediana se colocan en el nuevo nodo izquierdo, y los valores superiores a la mediana se colocan en el nuevo nodo derecho, actuando la mediana como valor de separación.
   3. El valor de separación se inserta en el nodo padre, lo que puede provocar que se divida, y así sucesivamente. Si el nodo no tiene padre (es decir, si era la raíz), se crea una nueva raíz encima de este nodo (aumentando la altura del árbol).

Si la división llega hasta la raíz, crea una nueva raíz con un único valor separador y dos hijos, razón por la cual el límite inferior del tamaño de los nodos internos no se aplica a la raíz. El número máximo de elementos por nodo es U −1. Cuando un nodo se divide, un elemento se mueve al padre, pero se agrega otro. Por lo tanto, debe ser posible dividir el número máximo U −1 de elementos en dos nodos válidos. Si este número es impar, entonces U = 2 L y uno de los nuevos nodos contiene ( U −2)/2 = L −1 elementos, y por lo tanto es un nodo válido, y el otro contiene un elemento más, y por lo tanto también es válido. Si U −1 es par, entonces U = 2 L −1, por lo que hay 2 L −2 elementos en el nodo. La mitad de este número es L −1, que es el número mínimo de elementos permitidos por nodo.

Un algoritmo alternativo permite un único recorrido descendente del árbol desde la raíz hasta el nodo donde se realizará la inserción, dividiendo de forma preventiva cualquier nodo lleno que se encuentre en el camino. Esto evita la necesidad de recuperar los nodos padre en memoria, lo cual puede resultar costoso si los nodos se encuentran en almacenamiento secundario. Sin embargo, para utilizar este algoritmo, debemos poder enviar un elemento al padre y dividir los U −2 elementos restantes en dos nodos válidos, sin añadir un nuevo elemento. Esto requiere U = 2 L en lugar de U = 2 L −1, lo que explica por qué algunos libros de texto imponen este requisito al definir los árboles B.

Existen dos estrategias populares para eliminar elementos de un árbol B.

1. Localice y elimine el elemento, luego reestructure el árbol para conservar sus invariantes, O
2. Realice un único recorrido por el árbol, pero antes de entrar (visitar) un nodo, reestructure el árbol de manera que, una vez que se encuentre la clave que se va a eliminar, se pueda eliminar sin que sea necesario realizar ninguna reestructuración adicional.

El algoritmo que se muestra a continuación utiliza la primera estrategia.

Hay dos casos especiales a tener en cuenta al eliminar un elemento:

1. El elemento en un nodo interno es un separador para sus nodos hijos.
2. Eliminar un elemento puede hacer que su nodo tenga un número mínimo de elementos e hijos.

Los procedimientos para estos casos se detallan a continuación.

Si bien las bases de datos recién cargadas tienden a tener un buen comportamiento secuencial, este comportamiento se vuelve cada vez más difícil de mantener a medida que la base de datos crece, lo que genera más E/S aleatorias y problemas de rendimiento. ^{[ 24 ]}

Un caso especial común es la adición de una gran cantidad de datos preordenados a un árbol B inicialmente vacío. Si bien es posible realizar una serie de inserciones sucesivas, la inserción de datos ordenados da como resultado un árbol compuesto casi en su totalidad por nodos parcialmente llenos. En cambio, se puede utilizar un algoritmo especial de "carga masiva" para producir un árbol más eficiente con un factor de ramificación mayor.

Cuando la entrada está ordenada, todas las inserciones se encuentran en el extremo derecho del árbol, y en particular, cada vez que se divide un nodo, se garantiza que no se realizarán más inserciones en la mitad izquierda. Al cargar datos en bloque, aprovechamos esto y, en lugar de dividir los nodos sobrecargados de manera uniforme, los dividimos de la forma más desigual posible: dejamos el nodo izquierdo completamente lleno y creamos un nodo derecho con cero claves y un hijo (en contra de las reglas habituales de los árboles B).

Al finalizar la carga masiva, el árbol está compuesto casi en su totalidad por nodos completamente llenos; solo el nodo más a la derecha de cada nivel puede estar parcialmente lleno. Dado que estos nodos también pueden estar parcialmente llenos , para restablecer las reglas normales del árbol B, se combinan con sus hermanos izquierdos (que están completamente llenos) y se dividen las claves para obtener dos nodos que estén al menos parcialmente llenos. El único nodo que carece de un hermano izquierdo completo es la raíz, que puede estar parcialmente llena.

Lehman y Yao ^{[ 27 ]} demostraron que se podían evitar todos los bloqueos de lectura (y, por lo tanto, mejorar considerablemente el acceso concurrente) al vincular los bloques del árbol en cada nivel con un puntero "siguiente". Esto da como resultado una estructura de árbol donde tanto las operaciones de inserción como las de búsqueda descienden desde la raíz hasta la hoja. Los bloqueos de escritura solo son necesarios cuando se modifica un bloque del árbol. Esto maximiza la concurrencia de acceso por parte de múltiples usuarios, una consideración importante para las bases de datos y/u otros métodos de almacenamiento ISAM basados ​​en árboles B. El costo asociado a esta mejora es que las páginas vacías no se pueden eliminar del árbol B durante las operaciones normales. (Existen estrategias para implementar la fusión de nodos. ^{[ 28 ] [ 29 ]} )

La patente estadounidense 5283894, concedida en 1994, parece mostrar una forma de utilizar un «método de metaacceso» ^{[ 30 ]} para permitir el acceso y la modificación concurrentes de árboles B+ sin bloqueos. La técnica accede al árbol «hacia arriba» tanto para búsquedas como para actualizaciones mediante índices adicionales en memoria que apuntan a los bloques de cada nivel en la caché de bloques. No se requiere reorganización para las eliminaciones y no hay punteros «siguiente» en cada bloque como en Lehman y Yao.

Dado que los árboles B tienen una estructura similar a la de los árboles rojo-negro , los algoritmos paralelos para árboles rojo-negro también se pueden aplicar a los árboles B.

Un árbol Maple es un árbol B desarrollado para su uso en el kernel de Linux para reducir la contención de bloqueos en la gestión de memoria virtual. ^{[ 31 ] [ 32 ] [ 33 ]}

Los árboles (a,b) son generalizaciones de los árboles B. Los árboles B requieren que cada nodo interno tenga un mínimo de${\displaystyle \lfloor K/2\rfloor +1}$niños y un máximo de${\displaystyle K}$niños, para algún valor preestablecido de${\displaystyle K}$En cambio, un árbol (a,b) permite que el número mínimo de hijos para un nodo interno se establezca arbitrariamente bajo. En un árbol (a,b), cada nodo interno tiene entre a y b hijos, para algunos valores preestablecidos de a y b .

• Bayer, Rudolf ; McCreight, E. (julio de 1970), Organización y mantenimiento de grandes índices ordenados , vol.  Informe de Ciencias Matemáticas e Informáticas n.º 20, Laboratorios de Investigación Científica de Boeing.
• Bayer, Rudolf (1971). "Árboles B binarios para memoria virtual". Actas del taller ACM-SIGFIDET de 1971 sobre descripción, acceso y control de datos . San Diego, California..