árbol B

Una estructura de datos basada en árbol y autoequilibrada que permite el acceso de lectura/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 de búsqueda binario , permitiendo nodos con más de dos hijos. ^[2] A diferencia de otros árboles de búsqueda binarios autoequilibrados , el árbol B es muy 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 fin de gestionar eficientemente páginas de índice para grandes archivos de acceso aleatorio. La suposición básica era que los índices serían tan voluminosos que sólo pequeños trozos del árbol podrían caber en la memoria principal. El artículo de Bayer y McCreight Organización y mantenimiento de grandes índices ordenados ^[1] circuló 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 , equilibrado , entre , amplio , tupido , 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 interno 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 no 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 _: 1 y 2 . Todos los valores en el subárbol más a la izquierda serán menores que ₁ , todos los valores en el subárbol central estarán entre 1 y 2 , y todos los valores _{en el subárbol más} a la derecha serán mayores que 2 _.

Nodos internos

Los nodos internos (también conocidos como nodos internos ) son todos los nodos excepto los nodos hoja y el nodo raíz. Generalmente 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 es siempre 1 menor 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 hasta la mitad. La relación entre U y L implica que se pueden unir dos nodos medio llenos para formar un nodo legal, y un nodo completo se puede dividir en dos nodos legales (si hay espacio para insertar un elemento 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 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 sin ningún hijo.

Nodos de hoja

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 sólo almacenan claves (como máximo m -1, y al menos m /2-1 si no son la raíz) y punteros (uno para cada clave) a los nodos que transportan 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 crece con la profundidad del árbol. Como ocurre con cualquier árbol equilibrado, el coste crece mucho más lentamente que el número de elementos.

Algunos árboles equilibrados almacenan valores sólo en los nodos de las hojas y utilizan diferentes tipos de nodos para los nodos de las hojas y los nodos internos. Los árboles B mantienen valores en todos los nodos del árbol excepto en los nodos de hoja.

Diferencias en 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 del árbol B como el número mínimo de claves en un nodo no 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 la hoja era el nivel más bajo de claves, pero Knuth consideró que el nivel de la hoja estaba un nivel por debajo de las claves más bajas. ^[10] Hay muchas opciones de implementación posibles. En algunos diseños, las hojas pueden contener todo el registro de datos; en otros diseños, las hojas sólo pueden contener indicaciones hacia el registro de datos. Esas elecciones no son fundamentales para la idea de un árbol B. ^[11]

Para simplificar, la mayoría de los autores suponen que hay un número fijo de claves que caben en un nodo. La suposición básica es que el tamaño de la clave es fijo y el tamaño del nodo es fijo. En la práctica, se pueden emplear claves de longitud variable. ^[12]

descripción informal

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

Estructura de nodo

Al igual que con 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}}$: puntero a un registro que almacena los datos.
• ${\displaystyle k_{i}}$: La clave de búsqueda en el índice de nodo de base 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 las hojas 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 siguiente tabla:

Inserción y eliminación

Para mantener el rango predefinido de nodos secundarios, los nodos internos se pueden unir o dividir.

Por lo general, se elige que el número de claves varíe entre y , donde es el número mínimo 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, entonces 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 principal. Cada nodo dividido tiene la cantidad mínima requerida de claves. De manera similar, si un nodo interno y su vecino tienen 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 claves; unirse al vecino agregaría llaves más una llave más que le trajo el padre del vecino. El resultado es un nodo de claves completamente completo . ${\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 de claves que podría estar sobrellenado en dos hermanos de clave e insertando la clave de valor medio en el padre. La profundidad solo aumenta cuando se parte la raíz, manteniendo 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 los 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, las claves of y (transicionalmente) , en cuyo caso los dos hermanos y el padre se fusionan, reduciendo 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 alejado de la raíz.

Comparación con otros árboles

Debido a que se permite una variedad 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 implementaciones alternativas cuando el tiempo para acceder a los datos de un nodo excede en gran medida el tiempo dedicado a 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 costosos accesos a los nodos. Además, el reequilibrio del árbol ocurre con menos frecuencia. El número máximo 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 2 o 3 árboles B son más fáciles de explicar, 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 puede referirse 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 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 garantiza que los nodos que no son raíz estén llenos al menos en 2/3 en lugar de 1/2. ^[14] Como la parte más costosa de la operación de insertar el nodo en el árbol B es dividir el nodo, los árboles B ^* se crean para posponer la operación de división tanto como sea posible. ^[15] Para mantener esto, en lugar de dividir inmediatamente un nodo cuando se llena, sus claves se comparten con un nodo al lado. Esta operación de derrame es menos costosa que la división, porque solo requiere cambiar las claves entre los nodos existentes, no asignar memoria para uno nuevo. ^[15] Para insertar, 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 número máximo de punteros a subárboles de un nodo), es necesario verificar si existe el hermano correcto y si tiene algo de espacio libre. . Si el hermano derecho tiene claves j < m − 1 , las claves se redistribuyen entre los dos nodos hermanos de la manera más uniforme posible. Para este propósito, m - 1 claves del nodo actual, la nueva clave insertada, una clave del nodo principal y j claves del nodo hermano se ven como una matriz ordenada de m + j + 1 claves. La matriz se divide por 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. ^[15] (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. ^[15] Cuando ambos nodos hermanos están llenos, los dos nodos (el nodo actual y un hermano) se dividen en tres y una clave más se desplaza hacia arriba en el árbol, al nodo padre. ^[15] Si el padre está lleno, la operación de derrame/división se propaga hacia el nodo raíz. ^[15] 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 ^* . ^[dieciséis]
• Los árboles B se pueden convertir en árboles de estadísticas de orden para permitir búsquedas rápidas del enésimo registro en orden de clave, o contar el número de registros entre dos registros cualesquiera, y varias otras operaciones relacionadas. ^[17]

Uso del árbol B en bases de datos

Es hora de buscar un archivo ordenado

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

Históricamente, las grandes bases de datos se han mantenido en unidades de disco. El tiempo necesario para leer un registro en una unidad de disco supera con creces el tiempo necesario para comparar claves una vez que el registro está disponible. El tiempo para leer un registro de una unidad de disco implica un tiempo de búsqueda y un retraso de rotación. El tiempo de búsqueda puede ser de 0 a 20 o más milisegundos, y el retraso de rotación 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 medio de búsqueda de lectura es de 8,5 milisegundos. ^[18] Para simplificar, supongamos que la lectura desde el disco tarda unos 10 milisegundos.

Entonces, ingenuamente, el tiempo para localizar un registro entre un millón tomaría 20 lecturas de disco multiplicadas por 10 milisegundos por lectura de disco, lo que es 0,2 segundos.

El tiempo no será tan malo 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, entonces se podrían almacenar 100 registros en cada bloque. El tiempo de lectura del disco anterior fue en realidad 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 comparaciones aproximadamente 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 deben acelerar las primeras 13 a 14 comparaciones (cada una de las cuales requirió acceso al disco).

Un índice acelera la búsqueda

Se puede lograr una mejora significativa en el rendimiento con un índice de árbol B. 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 partida del árbol o la "raíz". Aquí es donde comenzaría la búsqueda de una clave determinada, recorriendo un camino que termina en una hoja. La mayoría de las páginas de esta estructura serán páginas hoja que, en última instancia, 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 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 en un factor de dos. Esto se puede mejorar sustancialmente creando un índice auxiliar que contenga el primer registro en cada bloque de 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 más rápidamente. Encontrar una entrada en el índice auxiliar nos diría qué bloque buscar en la base de datos principal; después de buscar en el índice auxiliar, tendríamos que buscar sólo en ese bloque de la base de datos principal, a un costo de una lectura de disco más. El índice contendría 10.000 entradas, por lo que se necesitarían como máximo 14 comparaciones. Al igual que la base de datos principal, las últimas seis comparaciones en el índice auxiliar estarían en el mismo bloque de disco. Se puede buscar el índice en aproximadamente ocho lecturas de disco y se puede acceder al registro deseado en nueve lecturas de disco.

El truco de crear un índice auxiliar se puede repetir para crear un índice auxiliar para el índice auxiliar. Eso crearía un índice auxiliar que necesitaría sólo 100 entradas y cabría en un bloque de disco.

En lugar de leer 14 bloques de disco para encontrar el registro deseado, sólo 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. Leer y buscar el primer (y único) bloque del índice aux-aux, que es la raíz del árbol, identifica el bloque relevante en el índice aux en el nivel siguiente. La lectura y búsqueda de ese bloque de índice auxiliar identifica el bloque relevante a leer, hasta que el nivel final, conocido como nivel de hoja, identifica un registro en la base de datos principal. En lugar de 150 milisegundos, sólo necesitamos 30 milisegundos para obtener el récord.

Los índices auxiliares han convertido 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 y gran parte del índice auxiliar pueden residir en un caché de disco , por lo que no incurrirían en 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. ^[19]

Inserciones y eliminaciones

Si la base de datos no cambia, entonces compilar el índice es sencillo y nunca es necesario cambiarlo. Si hay cambios, la gestión de la base de datos y su índice se vuelve más complicada.

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 en orden. Si hay una gran cantidad de eliminaciones diferidas , la búsqueda y el almacenamiento se vuelven menos eficientes. ^[20]

Las inserciones pueden ser muy lentas en un archivo secuencial ordenado porque se debe dejar espacio para el registro insertado. Para insertar un registro antes del primer registro es necesario desplazar todos los registros uno hacia abajo. Una operación de este tipo es demasiado costosa para ser práctica. Una solución es dejar algunos espacios. En lugar de empaquetar 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, entonces se debe encontrar algo de espacio libre en algún bloque cercano y ajustar los índices auxiliares. La esperanza es que haya suficiente espacio disponible en las cercanías, de modo que no sea necesario reorganizar muchos bloques. Alternativamente, se pueden utilizar algunos bloques de disco fuera de secuencia. ^[19]

Ventajas del uso del árbol B para bases de datos

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

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

Además, un árbol B minimiza el desperdicio asegurándose de que los nodos interiores estén llenos al menos hasta la mitad. Un árbol B puede manejar un número arbitrario de inserciones y eliminaciones. ^[19]

Alturas en el mejor y el peor caso

Sea h ≥ –1 la altura del árbol B clásico (consulte Á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 en el mejor de los casos (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 ordinario, ${\displaystyle d}$ ${\displaystyle d=\left\lceil m/2\right\rceil .}$

Comer (1979) y Cormen et al. (2001) dan la altura en el peor de los casos (la altura máxima) de un árbol B como ^[21]

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

Algoritmos

Buscar

La búsqueda es similar a buscar en un árbol de búsqueda binario. Comenzando en 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

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

Todas las inserciones comienzan en un nodo de 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 con los siguientes pasos:

1. Si el nodo contiene menos elementos que el 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 modo que:
   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, actuando la mediana como valor de separación.
   3. El valor de separación se inserta en el padre del nodo, lo que puede provocar que se divida, etc. Si el nodo no tiene padre (es decir, el nodo era la raíz), cree 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 de 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 se divide un nodo, un elemento se mueve al padre, pero se agrega un elemento. Entonces, 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 tanto, es un nodo legal, y el otro contiene un elemento más, y por tanto es un nodo legal. legal también. Si U −1 es par, entonces U =2 L −1, entonces 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 admite un único paso por el árbol desde la raíz hasta el nodo donde se realizará la inserción, dividiendo de forma preventiva cualquier nodo completo que se encuentre en el camino. Esto evita la necesidad de recuperar los nodos principales en la memoria, lo que puede resultar costoso si los nodos están en el almacenamiento secundario. Sin embargo, para utilizar este algoritmo, debemos poder enviar un elemento al padre y dividir los elementos U −2 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 ^{[ ¿ cuales? ]} los libros de texto imponen este requisito al definir los árboles B.

Supresión

Existen 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 un único recorrido hacia abajo en el árbol, pero antes de ingresar (visitar) un nodo, reestructure el árbol para 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 siguiente algoritmo utiliza la estrategia anterior.

Hay dos casos especiales a considerar al eliminar un elemento:

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

Los procedimientos para estos casos están en orden 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 insuficiente, 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 en 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 es aún menor que el separador. Asimismo, el elemento más pequeño del subárbol derecho sigue siendo mayor que el separador. Ambos elementos están en nodos hoja y cualquiera de ellos puede ser el nuevo separador de los dos subárboles. Algorítmicamente se describe 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 desea 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 del número requerido), entonces reequilibre el árbol comenzando desde el nodo hoja.

Reequilibrio después de la eliminación

El reequilibrio comienza desde una hoja y continúa hacia la raíz hasta que el árbol está equilibrado. Si eliminar 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 tamaño mínimo. Por lo general, la redistribución implica mover un elemento de un nodo hermano que tiene más del número mínimo de nodos. Esa operación de redistribución se llama 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 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 del número mínimo de elementos, entonces gire a la izquierda
  1. Copie el separador del padre al final 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 primer elemento del hermano derecho (el hermano derecho pierde un nodo pero aún tiene al menos la cantidad mínima de elementos)
  3. El árbol ahora está equilibrado.
• De lo contrario, si el hermano izquierdo del nodo deficiente existe y tiene más del número mínimo de elementos, entonces gire a la derecha.
  1. Copie 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 la cantidad mínima de elementos)
  3. El árbol ahora está equilibrado.
• De lo contrario, si ambos hermanos inmediatos tienen solo la cantidad mínima de elementos, entonces fusione con un hermano intercalando su separador quitado de su padre.
  1. Copie 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 el número máximo de elementos y el nodo derecho está vacío)
  3. Elimine 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, libérelo y convierta el nodo fusionado en la nueva raíz (el árbol se vuelve menos profundo)
     • De lo contrario, si el padre tiene menos elementos de los requeridos, entonces reequilibre el padre ^[22]

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 el árbol 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 E/S aleatorias y desafíos de rendimiento. ^[23]

Construcción inicial

Un caso especial común es agregar una gran cantidad de datos preclasificados en un árbol B inicialmente vacío. Si bien es muy posible realizar simplemente 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 su lugar, 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 derecho del árbol y, en particular, cada vez que se divide un nodo, tenemos la garantía de que no se realizará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 del procedimiento B- habitual). reglas del árbol).

Al final de la carga masiva, el árbol se compone casi en su totalidad de nodos completamente llenos; sólo 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 de la mitad de su capacidad, para restablecer las reglas normales del árbol B, combine dichos nodos con sus hermanos izquierdos (garantizados llenos) y divida las claves para producir dos nodos al menos hasta la mitad de su capacidad. El único nodo que carece de un hermano izquierdo completo es la raíz, a la que se le permite estar menos de la mitad de su capacidad.

En sistemas de archivos

Además de su uso en bases de datos, el árbol B (o § Variantes) también se usa 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 de archivos en una dirección de bloque de disco. ${\displaystyle i}$

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

Otros sistemas operativos permiten que un archivo crezca. Es posible que los bloques de disco resultantes no sean contiguos, por lo que la asignación de bloques lógicos a bloques físicos es más complicada.

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, de ser así, qué bloque (si lo hay) es el siguiente bloque de disco del mismo archivo. Entonces, la asignación de cada archivo se representa como una lista vinculada en la tabla. Para encontrar la dirección de disco del bloque de archivos , el sistema operativo (o utilidad de disco) debe seguir secuencialmente la lista vinculada 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 fue una gran penalización porque los discos y archivos eran pequeños y el FAT tenía pocas entradas y cadenas de archivos relativamente cortas. En el sistema de archivos FAT12 (utilizado en disquetes y los primeros discos duros), no había más de 4.080 ^{[nota 2]} entradas, y el FAT normalmente residía en la memoria. A medida que los discos crecieron, la arquitectura FAT comenzó a enfrentar penalizaciones. En un disco grande que utiliza FAT, puede ser necesario realizar lecturas del disco para conocer la ubicación en el disco de un bloque de archivos que se va a leer o escribir. ${\displaystyle i}$

TOPS-20 (y posiblemente TENEX ) utilizó un árbol de niveles de 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 cabe en un bloque de 512 (2 ⁹ ) palabras, entonces el directorio de archivos apuntará a ese bloque de disco físico. Si el archivo cabe entre 2 ^{y 18} 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 cabe en 2 ²⁷ palabras, entonces el directorio apuntaría a un bloque que contiene un índice aux-aux; 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 ^{a 27} 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 , ^[24] AIX (jfs2) y algunos sistemas de archivos de 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. ^[25]

Actuación

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

Variaciones

Acceder a la simultaneidad

Lehman y Yao ^[26] demostraron que se podían evitar todos los bloqueos de lectura (y, por tanto, mejorar enormemente el acceso concurrente) vinculando 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 de árbol. Esto maximiza la concurrencia de acceso por parte de múltiples usuarios, una consideración importante para bases de datos y/u otros métodos de almacenamiento ISAM basados ​​en árbol B. El costo asociado con esta mejora es que las páginas vacías no se pueden eliminar del btree durante las operaciones normales. (Sin embargo, consulte ^[27] para conocer varias estrategias para implementar la fusión de nodos y el código fuente en ^[28] ) .

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

Algoritmos paralelos

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

árbol de arce

Un árbol de arce 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. ^{[30] [31] [32]}

Ver también

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

Notas

1. Para FAT, lo que aquí se llama "bloque de disco" es lo que la documentación de FAT llama "clúster", que es un grupo de tamaño fijo de uno o más sectores de disco físico completos contiguos . Para los propósitos de esta discusión, un cluster no tiene una diferencia significativa con un sector físico.
2. Dos de ellos 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 . Laboratorios de investigación científica de Boeing. pag. 107. doi :10.1145/1734663.1734671. S2CID  26930249.
2. Comer 1979.
3. Bayer y McCreight 1972.
4. Comer 1979, pag. 123 nota al pie 1.
5. Weiner, Peter G. (30 de agosto de 2013). "4- Edward M McCreight" - vía Vimeo.
6. "Centro de Stanford para el desarrollo profesional". 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.
10. Folk y Zoellick 1992, pág. 363.
11. Bayer y McCreight (1972) evitaron el problema diciendo que un elemento í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 realmente no importaba lo que fuera. Bayer y McCreight (1972) afirman: "Para este artículo, la información asociada ya no tiene ningún interés".
12. Folk y Zoellick 1992, pág. 379.
13. 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)
14. Knuth 1998, pag. 488.
15. Tomašević, Milo (2008). Algoritmos y estructuras de datos . Belgrado, Serbia: Akademska misao. págs. 274-275. ISBN 978-86-7466-328-8.
16. Rigin AM, Shershakov SA (10 de septiembre de 2019). "Extensión SQLite RDBMS para indexación de datos mediante modificaciones del árbol B". Actas del Instituto de Programación de Sistemas del RAS . Instituto de Programación de Sistemas del RAS (ISP RAS). 31 (3): 203–216. doi : 10.15514/ispras-2019-31(3)-16 . S2CID  203144646 . Consultado el 29 de agosto de 2021 .
17. Árboles B contados, consultado el 25 de enero de 2010
18. Manual del producto: Barracuda ES.2 Serial ATA, Rev. F., publicación 100468393 (PDF) . Tecnología Seagate LLC. 2008. pág. 6.
19. Kleppmann, Martín (2017). Diseño de aplicaciones con uso intensivo de datos. Sebastopol, California : O'Reilly Media . pag. 80.ISBN _ 978-1-449-37332-0.
20. Jan Jannink. "Implementación de la eliminación en árboles B +". Sección "4 Eliminación diferida".
21. Comer 1979, pag. 127; Cormen et al. 2001, págs. 439–440
22. "Eliminación en un árbol B" (PDF) . cs.rhodes.edu . Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 24 de mayo de 2022 .
23. "Caché de árboles B ajenos" . Universidad Estatal de Nueva York (SUNY) en Stony Brook . Consultado el 17 de enero de 2011 .
24. Mark Russinovich (30 de junio de 2006). "Dentro de Win2K NTFS, parte 1". Red de desarrolladores de Microsoft . Archivado desde el original el 13 de abril de 2008 . Consultado el 18 de abril de 2008 .
25. Matthew Dillon (21 de junio de 2008). "El sistema de archivos HAMMER" (PDF) . Archivado (PDF) desde el original el 9 de octubre de 2022.
26. Lehman, Philip L.; Yao, s. Bing (1981). "Bloqueo eficiente para operaciones simultáneas en árboles B". Transacciones ACM en sistemas de bases de datos . 6 (4): 650–670. doi : 10.1145/319628.319663 . S2CID  10756181.
27. Wang, Paul (1 de febrero de 1991). "Un análisis en profundidad de algoritmos de árbol B concurrentes" (PDF) . dtic.mil . Archivado desde el original (PDF) el 4 de junio de 2011 . Consultado el 21 de octubre de 2022 .
28. "Descargas - árbol-btree de alta concurrencia - Código de árbol B de alta concurrencia en C - Alojamiento de proyectos GitHub". GitHub . Consultado el 27 de enero de 2014 .
29. "Método de metaacceso al índice de árbol B simultáneo sin bloqueo para nodos almacenados en caché".
30. Presentamos los arces (LWN.net)
31. Maple Tree (documentación del kernel de Linux)
32. Presentamos el árbol de arce (LWN.net/github)

Fuentes

• Bayer, R .; McCreight, E. (1972). «Organización y Mantenimiento de Grandes Índices Ordenados» (PDF) . Acta Informática . 1 (3): 173–189. doi :10.1007/bf00288683. S2CID  29859053..
• Comer, Douglas (junio de 1979). "El omnipresente árbol B". Encuestas Informáticas . 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.
• Gente, Michael J.; Zoellick, Bill (1992). Estructuras de archivos (2ª ed.). Addison-Wesley. ISBN 0-201-55713-4..
• Knuth, Donald (1998). Ordenar y buscar . El arte de la programación informática . vol. 3 (Segunda ed.). Addison-Wesley. ISBN 0-201-89685-0.Sección 6.2.4: Árboles de múltiples vías, págs. 481–491. Además, las páginas 476 y 477 de la sección 6.2.3 (Árboles equilibrados) analizan 2 o 3 árboles.

papeles originales

• Bayer, Rudolf ; McCreight, E. (julio de 1970), Organización y mantenimiento de grandes índices ordenados , vol. Informe de Ciencias de la Información y Matemáticas No. 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..

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 árbol equilibradas
• Diccionario de algoritmos y estructuras de datos del NIST: árbol B
• Tutorial del árbol B
• La implementación de InfinityDB BTree
• Caché de árboles B(+) ajenos al caché
• Entrada del Diccionario de algoritmos y estructuras de datos para el árbol B*
• Estructuras de datos abiertas - Sección 14.2 - B-Trees, Pat Morin
• Árboles B contados
• B-Tree .Net, una implementación moderna y virtualizada de RAM y disco

Carga masiva

• Shetty, Soumya B. (2010). Una implementación configurable por el usuario de árboles B (Tesis). Universidad del Estado 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 . págs. 4–6. Archivado (PDF) desde el original el 9 de octubre de 2022.
• "ECS 165B: Implementación del sistema de base de datos: Clase 6" (PDF) . Universidad de California, Davis . 9 de abril de 2010. p. 23. Archivado (PDF) desde el original el 9 de octubre de 2022.
• "INSERCIÓN A GRANEL (Transact-SQL) en SQL Server 2017". Documentos de Microsoft. 6 de septiembre de 2018.