Árbol B

Una estructura de datos basada en árboles y con autoequilibrio que permite el acceso de lectura y escritura en tiempo logarítmico.

En informática , un árbol B es una estructura de datos de árbol autoequilibrado que mantiene datos ordenados y permite búsquedas, acceso secuencial, inserciones y eliminaciones en tiempo logarítmico . El árbol B generaliza el árbol binario de búsqueda , permitiendo nodos con más de dos hijos. ^[2] A diferencia de otros árboles binarios de búsqueda autoequilibrados , el árbol B es adecuado para sistemas de almacenamiento que leen y escriben bloques de datos relativamente grandes , como bases de datos y sistemas de archivos .

Historia

Los árboles B fueron inventados por Rudolf Bayer y Edward M. McCreight mientras trabajaban en Boeing Research Labs , con el propósito de administrar de manera eficiente las páginas de índice para archivos grandes de acceso aleatorio. La suposición básica era que los índices serían tan voluminosos que solo pequeños fragmentos del árbol podrían caber en la memoria principal. El artículo de Bayer y McCreight Organization and maintain of large ordered indices ^[1] se distribuyó por primera vez en julio de 1970 y luego se publicó en Acta Informatica . ^[3]

Bayer y McCreight nunca explicaron qué significa la B , si es que significa algo ; se han sugerido Boeing , balanced , between , broad , bushy y Bayer . ^{[4] [5] [6]} McCreight ha dicho que "cuanto más piensas en lo que significa la B en los árboles B, mejor entiendes los árboles B". ^[5]

Definición

Según la definición de Knuth , un árbol B de orden m es un árbol que satisface las siguientes propiedades: ^[7]

1. Cada nodo tiene como máximo m hijos.
2. Cada nodo, excepto la raíz y las hojas, tiene al menos ⌈ m /2⌉ hijos.
3. El nodo raíz tiene al menos dos hijos a menos que sea una hoja.
4. Todas las hojas aparecen en el mismo nivel.
5. Un nodo que no es hoja con k hijos contiene k −1 claves.

Las claves de cada nodo interno actúan como valores de separación que dividen sus subárboles. Por ejemplo, si un nodo interno tiene 3 nodos secundarios (o subárboles), entonces debe tener 2 claves: un ₁ y un _2. Todos los valores en el subárbol más a la izquierda serán menores que un ₁ , todos los valores en el subárbol del medio estarán entre un ₁ y un ₂ , y todos los valores en el subárbol más a la derecha serán mayores que un ₂ .

Nodos internos

Los nodos internos (también conocidos como nodos internos ) son todos los nodos excepto los nodos hoja y el nodo raíz. Por lo general, se representan como un conjunto ordenado de elementos y punteros secundarios. Cada nodo interno contiene un máximo de U hijos y un mínimo de L hijos. Por lo tanto, el número de elementos siempre es 1 menos que el número de punteros secundarios (el número de elementos está entre L −1 y U −1). U debe ser 2 L o 2 L −1; por lo tanto, cada nodo interno está al menos medio lleno. La relación entre U y L implica que dos nodos medio llenos se pueden unir para formar un nodo legal, y un nodo lleno se puede dividir en dos nodos legales (si hay espacio para empujar un elemento hacia arriba en el padre). Estas propiedades permiten eliminar e insertar nuevos valores en un árbol B y ajustar el árbol para preservar las propiedades del árbol B.

El nodo raíz

El número de hijos del nodo raíz tiene el mismo límite superior que el de los nodos internos, pero no tiene límite inferior. Por ejemplo, cuando hay menos de L −1 elementos en todo el árbol, la raíz será el único nodo del árbol que no tenga hijos.

Nodos de hojas

En la terminología de Knuth, los nodos "hoja" son los objetos/fragmentos de datos reales. Los nodos internos que están un nivel por encima de estas hojas son lo que otros autores llamarían "hojas": estos nodos solo almacenan claves (como máximo m -1, y como mínimo m /2-1 si no son la raíz) y punteros (uno para cada clave) a los nodos que contienen los objetos/fragmentos de datos.

Un árbol B de profundidad n +1 puede contener aproximadamente U veces más elementos que un árbol B de profundidad n , pero el costo de las operaciones de búsqueda, inserción y eliminación aumenta con la profundidad del árbol. Como sucede con cualquier árbol equilibrado, el costo crece mucho más lentamente que la cantidad de elementos.

Algunos árboles equilibrados almacenan valores solo en los nodos de hoja y utilizan distintos tipos de nodos para los nodos de hoja y los nodos internos. Los árboles B mantienen los valores en todos los nodos del árbol, excepto en los nodos de hoja.

Diferencias en la terminología

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

Bayer y McCreight (1972), ^[3] 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 raíz. Folk y Zoellick ^[9] 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 puede 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). ^[7]

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

Para simplificar, la mayoría de los autores suponen que hay una cantidad fija de claves que caben en un nodo. El supuesto básico es que el tamaño de la clave es fijo y el tamaño del nodo es fijo. En la práctica, se pueden utilizar claves de longitud variable. ^[11]

Descripción informal

Un árbol B (Bayer y McCreight 1972) de orden 5 (Knuth 1998).

Estructura de nodo

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 conocido como 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).
• ${\displaystyle pt_{i}}$:El puntero a un nodo secundario que inicia un subárbol.
• ${\displaystyle pr_{i}}$:El puntero a un registro que almacena los datos.
• ${\displaystyle k_{i}}$:La clave de búsqueda en el índice del nodo basado en cero . ${\displaystyle i}$

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

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

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

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

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

Inserción y eliminación

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

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

Si un nodo interno tiene claves, se puede agregar una clave a ese nodo dividiendo el nodo clave hipotético en dos nodos clave y moviendo la clave que habría estado en el medio al nodo padre. Cada nodo dividido tiene la cantidad mínima requerida de claves. De manera similar, si un nodo interno y su vecino tienen claves, se puede eliminar una clave del nodo interno combinándola con su vecino. Eliminar la clave haría que el nodo interno tuviera claves; unir el vecino agregaría claves más una clave más obtenida del padre del vecino. El resultado es un nodo completamente lleno de claves. ${\displaystyle 2d}$ ${\displaystyle 2d+1}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d-1}$ ${\displaystyle d}$ ${\displaystyle 2d}$

Un árbol B se mantiene equilibrado después de la inserción dividiendo un nodo que podría estar sobrecargado, de claves, en dos hermanos de clave intermedia e insertando la clave de valor medio en el padre. La profundidad solo aumenta cuando se divide la raíz, lo que mantiene el equilibrio. De manera similar, un árbol B se mantiene equilibrado después de la eliminación fusionando o redistribuyendo claves entre hermanos para mantener el mínimo de claves para nodos que no son raíz. Una fusión reduce la cantidad 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 claves y (transicionalmente) , en cuyo caso los dos hermanos y el padre se fusionan, lo que reduce la profundidad en uno. ${\displaystyle 2d+1}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d-1}$

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 de las hojas estén un nodo más lejos de la raíz.

Comparación con otros árboles

Debido a que se permite un rango de nodos secundarios, 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 tienen ventajas sustanciales sobre las implementaciones alternativas cuando el tiempo para acceder a los datos de un nodo excede en gran medida el tiempo empleado en procesar esos datos, porque entonces el costo de acceder al nodo puede amortizarse en múltiples operaciones dentro del nodo. Esto suele ocurrir cuando los datos del nodo están en un almacenamiento secundario , como unidades de disco . Al maximizar la cantidad de claves dentro de cada nodo interno , la altura del árbol disminuye y se reduce la cantidad de accesos costosos a los nodos. Además, el reequilibrio del árbol ocurre con menos frecuencia. La cantidad máxima de nodos secundarios depende de la información que se debe almacenar para cada nodo secundario y del tamaño de un bloque de disco completo o un tamaño análogo en el almacenamiento secundario. Si bien es más fácil explicar 2 o 3 árboles B, los árboles B prácticos que utilizan almacenamiento secundario necesitan una gran cantidad de nodos secundarios para mejorar el rendimiento.

Variantes

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 claves en sus nodos internos, pero no necesita almacenar esas claves en los registros de las hojas. La clase general incluye variaciones como el árbol B+ , el árbol B ^* y el árbol B ^*+ .

• En el árbol B+ , los nodos internos no almacenan ningún puntero a registros, por lo que 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 más superficial 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. ^[13] Como la parte más costosa de la operación de insertar el nodo en el árbol B es dividir el nodo, se crean árboles B ^* para posponer la operación de división tanto como sea posible. ^[14] Para mantener esto, en lugar de dividir inmediatamente un nodo cuando se llena, sus claves se comparten con un nodo contiguo. Esta operación de desbordamiento es menos costosa de hacer que la división, porque solo requiere cambiar las claves entre nodos existentes, no asignar memoria para uno nuevo. ^[14] Para insertar, primero se verifica si el nodo tiene algo de espacio libre en él y, si es 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 número máximo de punteros a subárboles desde un nodo), es necesario comprobar si el hermano derecho existe y tiene algo de espacio libre. Si el hermano derecho tiene j < m − 1 claves, entonces las claves se redistribuyen entre los dos nodos hermanos lo más uniformemente posible. Para este propósito, m - 1 claves del nodo actual, la nueva clave insertada, una clave del nodo padre y j claves del nodo hermano se ven como una matriz ordenada de m + j + 1 claves. La matriz se divide a la mitad, de modo que ⌊ ( m + j + 1)/2 ⌋ las claves más bajas permanecen en el nodo actual, la siguiente clave (del medio) se inserta en el padre y el resto va al hermano derecho. ^[14] (La clave recién insertada puede terminar en cualquiera de los tres lugares). La situación cuando el hermano derecho está lleno y el izquierdo no es análoga. ^[14] 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, al nodo padre. ^[14] Si el padre está lleno, entonces la operación de desbordamiento/división se propaga hacia el nodo raíz. ^[14] Sin embargo, eliminar nodos es algo más complejo que insertarlos.
• El árbol B ^{*+ combina las características principales} del árbol B+ y del árbol B ^* . ^[15]
• Los árboles B se pueden transformar en árboles estadísticos de orden para permitir búsquedas rápidas del registro N en orden clave, o contar la cantidad de registros entre dos registros cualesquiera y varias otras operaciones relacionadas. ^[16]

Uso de árboles B en bases de datos

Es hora de buscar un archivo ordenado

Los algoritmos de ordenación y búsqueda se pueden caracterizar por la cantidad de operaciones de comparación que se deben realizar utilizando la notación de orden . Una búsqueda binaria de 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 se podría localizar un registro específico con un máximo de 20 comparaciones: ⌈ log ₂ (1.000.000) ⌉ = 20 .

Históricamente, las bases de datos de gran tamaño se han guardado en unidades de disco. El tiempo necesario para leer un registro en una unidad de disco supera con creces el tiempo necesario para comparar las claves una vez que el registro está disponible debido al tiempo de búsqueda y a un retraso rotacional. El tiempo de búsqueda puede ser de 0 a 20 o más milisegundos, y el retraso rotacional promedia aproximadamente la mitad del período de rotación. Para una unidad de 7200 RPM, el período de rotación es de 8,33 milisegundos. Para una unidad como la 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. ^[17] Para simplificar, supongamos que la lectura del disco demora aproximadamente 10 milisegundos.

El tiempo para localizar un registro entre un millón en el ejemplo anterior tomaría 20 lecturas de disco multiplicadas por 10 milisegundos por lectura de disco, 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 16 kilobytes. Si cada registro tiene 160 bytes, se pueden almacenar 100 registros en cada bloque. El tiempo de lectura del disco anterior en realidad era para un bloque completo. Una vez que el cabezal del disco está en posición, se pueden leer uno o más bloques de disco con poca demora. Con 100 registros por bloque, las últimas 6 o más comparaciones no necesitan realizar ninguna lectura de disco: todas las comparaciones se realizan dentro del último bloque de disco leído.

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

Un índice acelera la búsqueda

Se puede utilizar un índice de árbol B para mejorar el rendimiento. Un índice de árbol B crea una estructura de árbol de varios niveles que divide una base de datos en bloques o páginas de tamaño fijo. Cada nivel de este árbol se puede utilizar para vincular esas páginas a través de una ubicación de dirección, lo que permite que una página (conocida como nodo o página interna) haga referencia a otra con páginas hoja en el nivel más bajo. Una página suele ser el punto de inicio del árbol o la "raíz". Aquí es donde comenzaría la búsqueda de una clave en particular, recorriendo una ruta que termina en una hoja. La mayoría de las páginas de esta estructura serán páginas hoja que hacen referencia a filas de tabla específicas.

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

En el ejemplo anterior, el índice contendría 10 000 entradas y se necesitarían como máximo 14 comparaciones para obtener un resultado. Al igual que la base de datos principal, las últimas seis comparaciones aproximadamente en el índice auxiliar se realizarían en el mismo bloque de disco. Se podría buscar en el índice en aproximadamente ocho lecturas de disco y se podría acceder al registro deseado en nueve lecturas de disco.

Se puede repetir la creación de un índice auxiliar para crear un índice auxiliar para el índice auxiliar. Esto crearía un índice auxiliar-auxiliar que necesitaría solo 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 bloques. Este bloqueo es la idea central detrás de la creación del árbol B, donde los bloques de disco completan una jerarquía de niveles para formar el índice. La lectura y búsqueda del primer (y único) bloque del índice aux-aux, que es la raíz del árbol, identifica el bloque relevante en aux-index en el nivel inferior. La lectura y búsqueda de ese bloque aux-index identifica el bloque relevante para leer, hasta que el nivel final, conocido como el nivel de 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 se realizan búsquedas frecuentes en la base de datos principal, el índice auxiliar-auxiliar y gran parte del índice auxiliar pueden residir en una caché de disco , por lo que no se produciría 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. ^[18]

Inserciones y eliminaciones

Si la base de datos no cambia, compilar el índice es sencillo y no es necesario modificarlo nunca. 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 puede simplemente marcarse como eliminado. La base de datos permanece ordenada. Si hay una gran cantidad de eliminaciones diferidas , la búsqueda y el almacenamiento se vuelven menos eficientes. ^[19]

Las inserciones pueden ser muy lentas en un archivo secuencial ordenado porque se debe hacer espacio para el registro insertado. Insertar un registro antes del primero requiere desplazar todos los registros hacia abajo. Esta operación es demasiado costosa para ser práctica. Una solución es dejar algunos espacios. En lugar de comprimir densamente todos los registros en un bloque, el bloque puede tener algo de espacio libre para permitir inserciones posteriores. Esos 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 encontrar espacio libre en algún bloque cercano y ajustar los índices auxiliares. El mejor caso es que haya suficiente espacio disponible cerca para que se pueda minimizar la cantidad de reorganización de bloques. Alternativamente, se pueden utilizar algunos bloques de disco fuera de secuencia. ^[18]

Ventajas del uso de árboles B para bases de datos

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 la cantidad 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 garantizar que los nodos interiores estén al menos medio llenos. Un árbol B puede manejar una cantidad arbitraria de inserciones y eliminaciones. ^[18]

Alturas en el mejor y peor de los casos

Sea h ≥ –1 la altura del árbol B clásico (véase Árbol (estructura de datos) § Terminología para la definición de altura del árbol). Sea n ≥ 0 el número de entradas en el árbol. Sea m el número máximo de hijos que puede tener un nodo. Cada nodo puede tener como máximo m −1 claves.

Se puede demostrar (por inducción, por ejemplo) que un árbol B de altura h con todos sus nodos completamente llenos tiene n = m ^{h +1} –1 entradas. Por lo tanto, la altura del mejor caso (es decir, la altura mínima) de un árbol B es:

${\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}$

Sea el número mínimo de hijos que debe tener un nodo interno (no raíz). Para un árbol B común, ${\displaystyle d}$ ${\displaystyle d=\left\lceil m/2\right\rceil .}$

Comer (1979) y Cormen et al. (2001) dan la altura del peor caso (la altura máxima) de un árbol B como ^[20]

${\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}$

Algoritmos

Buscar

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

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

Inserción

Ejemplo de inserción de un árbol B con cada iteración. Los nodos de este árbol B tienen como máximo 3 hijos (orden Knuth 3).

Todas las inserciones comienzan en un nodo de hoja. Para insertar un nuevo elemento, busque en el árbol el nodo de 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 que el número máximo permitido, entonces hay espacio para el nuevo elemento. Inserte el nuevo elemento en el nodo, manteniendo ordenados los elementos del nodo.
2. De lo contrario, el nodo está lleno, divídalo uniformemente 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 menores que la mediana se colocan en el nuevo nodo izquierdo y los valores mayores que la mediana se colocan en el nuevo nodo derecho, siendo la mediana la que actúa como valor de separación.
   3. El valor de separación se inserta en el nodo padre del nodo, lo que puede provocar que se divida, y así sucesivamente. Si el nodo no tiene padre (es decir, el nodo era la raíz), se crea una nueva raíz por encima de este nodo (lo que aumenta 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, por lo que 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 se divide un nodo, un elemento se mueve al padre, pero se agrega un elemento. Por lo tanto, debe ser posible dividir el número máximo U −1 de elementos en dos nodos legales. 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 legal, y el otro contiene un elemento más, y por lo tanto también es legal. 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 realizar un único paso por el árbol desde la raíz hasta el nodo donde se realizará la inserción, dividiendo preventivamente cualquier nodo completo que se encuentre en el camino. Esto evita la necesidad de recuperar los nodos padre en la memoria, lo que puede resultar costoso si los nodos están en un 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 legales, sin agregar un nuevo elemento. Esto requiere U = 2 L en lugar de U = 2 L −1, lo que explica por qué algunos libros de texto ^{[¿ cuáles? ]} imponen este requisito al definir árboles B.

Supresión

Hay dos estrategias populares para la eliminación de un árbol B.

1. Localice y elimine el elemento, luego reestructure el árbol para conservar sus invariantes, O
2. Realice una sola pasada por el árbol, pero antes de ingresar (visitar) un nodo, reestructure el árbol de modo que una vez que se encuentre la clave que se va a eliminar, se pueda eliminar sin generar la necesidad de ninguna reestructuración adicional.

El algoritmo siguiente utiliza la primera estrategia.

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

1. El elemento de un nodo interno es un separador para sus nodos secundarios.
2. Eliminar un elemento puede poner su nodo por debajo del número mínimo de elementos y elementos secundarios.

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

Eliminación de un nodo hoja

1. Busque el valor a eliminar.
2. Si el valor está en un nodo hoja, simplemente elimínelo del nodo.
3. Si se produce un desbordamiento, reequilibre el árbol como se describe en la sección "Reequilibrio después de la eliminación" a continuación.

Eliminación de un nodo interno

Cada elemento de un nodo interno actúa como un valor de separación para dos subárboles, por lo tanto, necesitamos encontrar un reemplazo para la separación. Tenga en cuenta que el elemento más grande en el subárbol izquierdo sigue siendo menor que el separador. Del mismo modo, el elemento más pequeño en el subárbol derecho sigue siendo mayor que el separador. Ambos elementos están en nodos de hoja y cualquiera de ellos puede ser el nuevo separador para los dos subárboles. Se describe algorítmicamente a continuación:

1. Elija un nuevo separador (ya sea el elemento más grande en el subárbol izquierdo o el elemento más pequeño en el subárbol derecho), elimínelo del nodo hoja en el que se encuentra y reemplace el elemento que se eliminará con el nuevo separador.
2. El paso anterior eliminó un elemento (el nuevo separador) de un nodo hoja. Si ese nodo hoja ahora es deficiente (tiene menos nodos que la cantidad requerida), entonces reequilibre el árbol comenzando desde el nodo hoja.

Reequilibrio después de la eliminación

El reequilibrio comienza desde una hoja y avanza hacia la raíz hasta que el árbol está equilibrado. Si la eliminación de un elemento de un nodo lo ha reducido al tamaño mínimo, entonces algunos elementos deben redistribuirse para que todos los nodos alcancen el mínimo. Por lo general, la redistribución implica mover un elemento de un nodo hermano que tiene más que el número mínimo de nodos. Esa operación de redistribución se denomina rotación . Si ningún hermano puede prescindir de un elemento, entonces el nodo deficiente debe fusionarse con un hermano. La fusión hace que el padre pierda un elemento separador, por lo que el padre puede volverse deficiente y necesitar un reequilibrio. La fusión y el reequilibrio pueden continuar hasta la raíz. Dado que el recuento mínimo de elementos no se aplica a la raíz, hacer que la raíz sea el único nodo deficiente no es un problema. El algoritmo para reequilibrar el árbol es el siguiente:

• Si el hermano derecho del nodo deficiente existe y tiene más que el número mínimo de elementos, entonces gire a la izquierda
  1. Copiar el separador desde el padre hasta el final del nodo deficiente (el separador se mueve hacia abajo; el nodo deficiente ahora tiene el número mínimo de elementos)
  2. Reemplace el separador en el padre con el primer elemento del hermano derecho (el hermano derecho pierde un nodo pero aún tiene al menos el número mínimo de elementos)
  3. El árbol ahora está equilibrado.
• De lo contrario, si el hermano izquierdo del nodo deficiente existe y tiene más que el número mínimo de elementos, entonces gire a la derecha.
  1. Copiar el separador del padre al inicio del nodo deficiente (el separador se mueve hacia abajo; el nodo deficiente ahora tiene la cantidad mínima de elementos)
  2. Reemplace el separador en el padre con el último elemento del hermano izquierdo (el hermano izquierdo pierde un nodo pero aún tiene al menos el número mínimo de elementos)
  3. El árbol ahora está equilibrado.
• De lo contrario, si ambos hermanos inmediatos tienen solo la cantidad mínima de elementos, entonces se fusionan con un hermano que intercala su separador quitado de su padre.
  1. Copiar el separador al final del nodo izquierdo (el nodo izquierdo puede ser el nodo deficiente o puede ser el hermano con el número mínimo de elementos)
  2. Mueva todos los elementos del nodo derecho al nodo izquierdo (el nodo izquierdo ahora tiene la cantidad máxima de elementos y el nodo derecho, vacío)
  3. Eliminar el separador del padre junto con su hijo derecho vacío (el padre pierde un elemento)
     • Si el padre es la raíz y ahora no tiene elementos, entonces libérelo y haga que el nodo fusionado sea la nueva raíz (el árbol se vuelve menos profundo)
     • De lo contrario, si el padre tiene menos elementos que el número requerido, entonces reequilibre al padre ^[21]

Nota : Las operaciones de reequilibrio son diferentes para los árboles B+ (por ejemplo, la rotación es diferente porque el padre tiene una copia de la clave) y los árboles B ^* (por ejemplo, tres hermanos se fusionan en dos hermanos).

Acceso secuencial

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 problemas de E/S aleatorios y de rendimiento. ^[22]

Construcción inicial

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 bastante 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 medio 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 más alto.

Cuando se ordena la entrada, todas las inserciones se realizan en el borde más a la derecha del árbol y, en particular, cada vez que se divide un nodo, tenemos la garantía de que no se producirán más inserciones en la mitad izquierda. Al realizar una carga masiva, aprovechamos esto y, en lugar de dividir los nodos demasiado llenos de manera uniforme, los dividimos de la manera más desigual posible: dejamos el nodo izquierdo completamente lleno y creamos un nodo derecho con cero claves y un hijo (en violación de las reglas habituales del árbol B).

Al final de 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 menos que lleno. Debido a que esos nodos también pueden estar menos que medio llenos, para restablecer las reglas normales del árbol B, combine esos nodos con sus hermanos izquierdos (completos garantizados) y divida las claves para producir dos nodos al menos medio llenos. El único nodo que carece de un hermano izquierdo completo es la raíz, que puede estar menos que medio lleno.

En sistemas de archivos

Además de su uso en bases de datos, el árbol B (o § Variantes) también se utiliza en sistemas de archivos para permitir un acceso aleatorio rápido a un bloque arbitrario en un archivo en particular. El problema básico es convertir la dirección del bloque del archivo en una dirección del bloque del disco. ${\displaystyle i}$

Algunos sistemas operativos requieren que el usuario asigne el tamaño máximo del archivo cuando se crea el archivo. El archivo puede entonces asignarse como bloques de disco contiguos. En ese caso, para convertir la dirección del bloque de archivo en una dirección de bloque de disco, el sistema operativo simplemente suma la dirección del bloque de archivo a la dirección del primer bloque de disco que constituye el archivo. El esquema es simple, pero el archivo no puede exceder su tamaño creado. ${\displaystyle i}$ ${\displaystyle i}$

Otros sistemas operativos permiten que un archivo crezca. Los bloques de disco resultantes pueden no ser contiguos, por lo que la asignación de bloques lógicos a bloques físicos es más compleja.

MS-DOS , por ejemplo, utilizaba una sencilla tabla de asignación de archivos (FAT). La FAT tiene una entrada para cada bloque de disco ^{[nota 1]} y esa entrada identifica si su bloque es utilizado por un archivo y, en caso afirmativo, qué bloque (si lo hay) es el siguiente bloque de disco del mismo archivo. Por lo tanto, la asignación de cada archivo se representa como una lista enlazada en la tabla. Para encontrar la dirección de disco del bloque de archivo , el sistema operativo (o la utilidad de discos) debe seguir secuencialmente la lista enlazada del archivo en la FAT. Peor aún, para encontrar un bloque de disco libre, debe escanear secuencialmente la FAT. Para MS-DOS, eso no era una gran penalización porque los discos y archivos eran pequeños y la FAT tenía pocas entradas y cadenas de archivos relativamente cortas. En el sistema de archivos FAT12 (utilizado en disquetes y primeros discos duros), no había más de 4080 ^{[nota 2]} entradas y la FAT normalmente residía en la memoria. A medida que los discos se hicieron más grandes, la arquitectura FAT comenzó a enfrentar penalizaciones. En un disco grande que utiliza FAT, puede ser necesario realizar lecturas de disco para conocer la ubicación del disco de un bloque de archivo que se leerá o escribirá. ${\displaystyle i}$

TOPS-20 (y posiblemente TENEX ) usaba un árbol de nivel 0 a 2 que tiene similitudes con un árbol B ^{[ cita requerida ]} . Un bloque de disco tenía 512 palabras de 36 bits. Si el archivo cabía en un bloque de 512 (2 ⁹ ) palabras, entonces el directorio del archivo apuntaría a ese bloque de disco físico. Si el archivo cabía en 2 ¹⁸ palabras, entonces el directorio apuntaría a un índice auxiliar; las 512 palabras de ese índice serían NULL (el bloque no está asignado) o apuntarían a la dirección física del bloque. Si el archivo cabía en 2 ²⁷ palabras, entonces el directorio apuntaría a un bloque que contenía un índice auxiliar-auxiliar; cada entrada sería NULL o apuntaría a un índice auxiliar. En consecuencia, el bloque de disco físico para un archivo de 2 ²⁷ palabras podría ubicarse en dos lecturas de disco y leerse en la tercera.

Los sistemas de archivos HFS+ y APFS de Apple , NTFS de Microsoft , ^[23] AIX (jfs2) y algunos sistemas de archivos Linux , como Bcachefs , Btrfs y ext4 , utilizan árboles B.

Los árboles B ^* se utilizan en los sistemas de archivos HFS y Reiser4 .

El sistema de archivos HAMMER de DragonFly BSD utiliza un árbol B+ modificado. ^[24]

Actuación

Un árbol B crece más lentamente con una cantidad creciente de datos que la linealidad de una lista enlazada. En comparación con una lista de saltos , ambas estructuras tienen el mismo rendimiento, pero el árbol B escala mejor con una cantidad creciente de n . Un árbol T , para sistemas de bases de datos de memoria principal , es similar pero más compacto.

Variaciones

Concurrencia de acceso

Lehman y Yao ^[25] demostraron que todos los bloqueos de lectura se podían evitar (y, por lo tanto, mejorar enormemente el acceso concurrente) vinculando los bloques del árbol en cada nivel con un puntero "next". Esto da como resultado una estructura de árbol donde tanto las operaciones de inserción como las de búsqueda descienden de la raíz a la hoja. Los bloqueos de escritura solo se requieren 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 con esta mejora es que las páginas vacías no se pueden eliminar del árbol B durante las operaciones normales. (Sin embargo, consulte ^[26] para conocer varias estrategias para implementar la fusión de nodos y el código fuente en ^[27] ) .

La patente estadounidense 5283894, otorgada en 1994, parece mostrar una forma de utilizar un "método de acceso meta" ^[28] para permitir el acceso y la modificación simultáneos del árbol B+ sin bloqueos. La técnica accede al árbol "hacia arriba" tanto para búsquedas como para actualizaciones por medio de índices adicionales en memoria que apuntan a los bloques en cada nivel de la caché de bloques. No se necesita ninguna reorganización para las eliminaciones y no hay punteros "siguientes" en cada bloque como en Lehman y Yao.

Algoritmos paralelos

Dado que los árboles B son similares en estructura a los árboles rojo-negros , los algoritmos paralelos para árboles rojo-negros también se pueden aplicar a los árboles B.

árbol de arce

Un árbol Maple es un árbol B desarrollado para su uso en el núcleo de Linux para reducir la contención de bloqueo en la gestión de memoria virtual. ^{[29] [30] [31]}

Véase también

• Árbol B+
• Árbol R
• Árbol rojo-negro
• 2–3 árboles
• 2–3–4 árboles

Notas

1. Para FAT, lo que aquí se denomina "bloque de disco" es lo que la documentación de FAT denomina "clúster", que es un grupo de tamaño fijo de uno o más sectores de disco físico completos y contiguos . Para los fines de este análisis, un clúster no tiene una diferencia significativa con respecto a un sector físico.
2. Dos de estos estaban reservados para propósitos especiales, por lo que solo 4078 podían representar bloques de disco (clústeres).

Referencias

1. Bayer, R.; McCreight, E. (julio de 1970). "Organización y mantenimiento de grandes índices ordenados" (PDF) . Actas del taller ACM SIGFIDET (ahora SIGMOD) de 1970 sobre descripción, acceso y control de datos - SIGFIDET '70 . Boeing Scientific Research Laboratories. pág. 107. doi :10.1145/1734663.1734671. S2CID  26930249.
2. Comer 1979.
3. Bayer y McCreight 1972.
4. Comer 1979, pág. 123 nota 1.
5. Weiner, Peter G. (30 de agosto de 2013). "4- Edward M McCreight" – vía Vimeo.
6. "Stanford Center for Professional Development". scpd.stanford.edu . Archivado desde el original el 4 de junio de 2014. Consultado el 16 de enero de 2011 .
7. Knuth 1998, pág. 483.
8. Folk y Zoellick 1992, pág. 362.
9. Folk y Zoellick 1992, pág. 363.
10. Bayer y McCreight (1972) evitaron el problema diciendo que un elemento de índice es un par (físicamente adyacente) de ( x ,  a ) donde x es la clave y a es alguna información asociada. La información asociada podría ser un puntero a un registro o registros en un acceso aleatorio, pero lo que fuera realmente no importaba. Bayer y McCreight (1972) afirman: "Para este artículo, la información asociada no tiene mayor interés".
11. Folk y Zoellick 1992, pág. 379.
12. Navathe, Ramez Elmasri, Shamkant B. (2010). Fundamentos de los sistemas de bases de datos (6ª ed.). Upper Saddle River, Nueva Jersey: Pearson Education. págs. 652–660. ISBN 9780136086208.{{cite book}}: CS1 maint: multiple names: authors list (link)
13. Knuth 1998, pág. 488.
14. Tomašević, Milo (2008). Algoritmos y estructuras de datos . Belgrado, Serbia: Akademska misao. págs. 274-275. ISBN 978-86-7466-328-8.
15. Rigin AM, Shershakov SA (10 de septiembre de 2019). "Extensión SQLite RDBMS para indexación de datos mediante modificaciones de árbol B". Actas del Instituto de Programación de Sistemas del RAS . 31 (3). Instituto de Programación de Sistemas del RAS (ISP RAS): 203–216. doi : 10.15514/ispras-2019-31(3)-16 . S2CID  203144646 . Consultado el 29 de agosto de 2021 .
16. Árboles B contados, consultado el 25 de enero de 2010
17. Manual del producto: Barracuda ES.2 Serial ATA, Rev. F., publicación 100468393 (PDF) . Seagate Technology LLC. 2008. pág. 6.
18. Kleppmann, Martin (2017). Diseño de aplicaciones con uso intensivo de datos. Sebastopol, California : O'Reilly Media . pág. 80. ISBN. 978-1-449-37332-0.
19. Jan Jannink. "Implementación de la eliminación en árboles B+". Sección "4 Eliminación diferida".
20. Comer 1979, pag. 127; Cormen et al. 2001, págs. 439–440
21. "Eliminación en un árbol B" (PDF) . cs.rhodes.edu . Archivado (PDF) desde el original el 2022-10-09 . Consultado el 24 de mayo de 2022 .
22. "Cache Oblivious B-trees" (Árboles B ajenos a la caché). Universidad Estatal de Nueva York (SUNY) en Stony Brook . Consultado el 17 de enero de 2011 .
23. Mark Russinovich (30 de junio de 2006). "Inside Win2K NTFS, Part 1". Microsoft Developer Network . Archivado desde el original el 13 de abril de 2008. Consultado el 18 de abril de 2008 .
24. Matthew Dillon (21 de junio de 2008). "El sistema de archivos HAMMER" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022.
25. Lehman, Philip L.; Yao, s. Bing (1981). "Bloqueo eficiente para operaciones concurrentes en árboles B". ACM Transactions on Database Systems . 6 (4): 650–670. doi : 10.1145/319628.319663 . S2CID  10756181.
26. Wang, Paul (1 de febrero de 1991). "Análisis en profundidad de algoritmos de árbol B concurrente" (PDF) . dtic.mil . Archivado desde el original (PDF) el 4 de junio de 2011 . Consultado el 21 de octubre de 2022 .
27. "Descargas - high-concurrency-btree - Código de árbol B de alta concurrencia en C - Alojamiento de proyectos en GitHub". GitHub . Consultado el 27 de enero de 2014 .
28. "Método de acceso meta al índice de árbol B concurrente sin bloqueo para nodos almacenados en caché".
29. Presentación de los arces (LWN.net)
30. Maple Tree (Documentación del kernel de Linux)
31. Presentación del árbol de arce (LWN.net / github)

Fuentes

• Bayer, R. ; McCreight, E. (1972). "Organización y mantenimiento de índices ordenados de gran tamaño" (PDF) . Acta Informatica . 1 (3): 173–189. doi :10.1007/bf00288683. S2CID  29859053..
• Comer, Douglas (junio de 1979). "El árbol B ubicuo". Computing Surveys . 11 (2): 123–137. doi : 10.1145/356770.356776 . ISSN  0360-0300. S2CID  101673..
• Cormen, Tomás ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2001). Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. págs. 434–454. ISBN 0-262-03293-7.Capítulo 18: Árboles B.
• Folk, Michael J.; Zoellick, Bill (1992). Estructuras de archivos (2.ª ed.). Addison-Wesley. ISBN 0-201-55713-4..
• Knuth, Donald (1998). Ordenación y búsqueda . El arte de la programación informática . Vol. 3 (segunda edición). Addison-Wesley. ISBN 0-201-89685-0.Sección 6.2.4: Árboles multidireccionales, págs. 481–491. Además, en las págs. 476–477 de la sección 6.2.3 (Árboles equilibrados) se analizan los árboles de 2 a 3 vías.

Documentos originales

• Bayer, Rudolf ; McCreight, E. (julio de 1970), Organización y mantenimiento de índices ordenados de gran tamaño , vol. Informe de ciencias matemáticas y de la información n.° 20, Boeing Scientific Research Laboratories.
• Bayer, Rudolf (1971). "Binary B-Trees for Virtual Memory". Actas del taller ACM-SIGFIDET de 1971 sobre descripción, acceso y control de datos . San Diego, California..

Enlaces externos

• Conferencia sobre el árbol B a cargo de David Scot Taylor, SJSU
• Visualización del árbol B (haga clic en "init")
• Visualización animada del árbol B
• Árbol B y árbol UB en Scholarpedia Curador: Dr Rudolf Bayer
• B-Trees: estructuras de datos de árboles equilibrados Archivado el 5 de marzo de 2010 en Wayback Machine
• Diccionario de algoritmos y estructuras de datos del NIST: árbol B
• Tutorial de árbol B
• La implementación de InfinityDB BTree
• Árboles B(+) ajenos al almacenamiento en caché
• Entrada del Diccionario de algoritmos y estructuras de datos para árbol B*
• Estructuras de datos abiertas - Sección 14.2 - Árboles B, Pat Morin
• Árboles B contados
• B-Tree .Net, una implementación de RAM y disco virtualizados y modernos

Carga masiva

• Shetty, Soumya B. (2010). Una implementación configurable por el usuario de árboles B (Tesis). Universidad Estatal de Iowa.
• Kaldırım, Semih (28 de abril de 2015). "Organización de archivos, ISAM, árbol B+ y carga masiva" (PDF) . Ankara, Turquía: Universidad Bilkent . pp. 4–6. Archivado (PDF) desde el original el 9 de octubre de 2022.
• "ECS 165B: Implementación de sistemas de bases de datos: lección 6" (PDF) . Universidad de California, Davis . 9 de abril de 2010. pág. 23. Archivado (PDF) desde el original el 2022-10-09.
• "BULK INSERT (Transact-SQL) en SQL Server 2017". Microsoft Docs. 6 de septiembre de 2018.