Árbol B

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Una estructura de datos basada en árboles, que permite el acceso de lectura/escritura en tiempo logarítmico

En informática, un árbol B es una estructura de datos de árbol autoequilibrada 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 binaria, permitiendo nodos con más de dos hijos. A diferencia de otros árboles de búsqueda binarios autoequilibrados, el árbol B es ideal para sistemas de almacenamiento que leen y escriben bloques de datos relativamente grandes, como bases de datos y sistemas de archivos.

Origen

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 cabrían en la memoria principal. El artículo de Bayer y McCreight, Organización y mantenimiento de grandes índices ordenados, circuló por primera vez en julio de 1970 y luego se publicó en Acta Informatica.

Bayer y McCreight nunca explicaron qué significa, en todo caso, la B: Boeing, equilibrado, amplio, bushy y Bayer han sido sugeridos. McCreight ha dicho que "cuanto más piensas en lo que significa la B en los árboles B, mejor entiendes los árboles B".

Definición

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

Cada nodo tiene m niños.
Cada nodo interno tiene al menos ⌈mNiños.
Cada nodo sordo tiene al menos dos hijos.
Todas las hojas aparecen en el mismo nivel.
Un nodo sin hojas k niños k- 1 llaves.

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: a₁ y a₂. Todos los valores en el subárbol más a la izquierda serán menores que a₁, todos los valores en el subárbol central estarán entre a₁ y a₂, y todos los valores en el subárbol más a la derecha serán mayores que a₂.

Nodos internos: Los nodos internos (también conocidos como nodos interiores) son todos los nodos excepto los nodos de hoja y el nodo raíz. Por lo general están representados como un conjunto ordenado de elementos y punteros infantiles. Cada nodo interno contiene un máximo de U niños y niñas mínimo de L niños. Por lo tanto, el número de elementos es siempre 1 menos que el número de niños punteros (el número de elementos es entre L−1 y U-1). U debe ser 2L o 2L−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 pueden unirse para hacer un nodo legal, y un nodo completo puede dividirse en dos nodos legales (si hay espacio para empujar un elemento hacia 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 niños del nodo raíz tiene el mismo límite superior que los nodos internos, pero no tiene un límite inferior. Por ejemplo, cuando hay menos que L−1 elementos en todo el árbol, la raíz será el único nodo en el árbol sin hijos.

Nodos de hoja: En la terminología de Knuth, los nodos "leaf" son los objetos de datos / pedazos. Los nodos internos que son un nivel por encima de estas hojas son lo que se llamaría "leaves" por otros autores: estos nodos sólo almacenan claves (en la mayoría de las hojas) m-1, y al menos m/2-1 si no son la raíz) y punteros (uno para cada clave) a nodos que llevan los objetos de datos / pedazos.

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 con cualquier árbol balanceado, el costo crece mucho más lentamente que el número de elementos.

Algunos árboles balanceados almacenan valores solo en los nodos de hoja y usan diferentes tipos de nodos para los nodos de hoja y los nodos internos. Los árboles B mantienen valores en cada nodo del árbol, excepto en los nodos hoja.

Diferencias en terminología

La literatura sobre árboles B no es uniforme en su terminología.

Bayer y McCreight (1972), Comer (1979) y otros definen el orden de B-tree como el número mínimo de claves en un nodo no raíz. señala que la terminología es ambigua porque no está claro el número máximo de claves. 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 al definir el orden como el número máximo de hijos (que es uno más que el número máximo de claves).

El término hoja también es inconsistente. Bayer y McCreight (1972) consideraron que el nivel de la hoja era el nivel más bajo de las claves, pero Knuth consideró que el nivel de la hoja estaba un nivel por debajo de las claves más bajas. 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 solo pueden contener punteros al registro de datos. Esas elecciones no son fundamentales para la idea de un árbol B.

Para simplificar, la mayoría de los autores asumen 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, pueden emplearse llaves de longitud variable.

Descripción informal

A B-tree (Bayer & McCreight 1972) of order 5 (Knuth 1998).

En los árboles B, los nodos internos (no hojas) pueden tener un número variable de nodos secundarios dentro de un rango predefinido. Cuando se insertan o eliminan datos de un nodo, su número de nodos secundarios cambia. Para mantener el rango predefinido, los nodos internos pueden unirse o dividirse. 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 límites inferior y superior en la cantidad de nodos secundarios generalmente se fijan para una implementación particular. Por ejemplo, en un árbol 2–3 (a veces denominado árbol B 2–3), cada nodo interno puede tener solo 2 o 3 nodos secundarios.

Cada nodo interno de un árbol B contiene una serie de llaves. Las claves actúan como valores de separación que dividen sus subárboles. Por ejemplo, si un nodo interno tiene 3 nodos (o subárboles) entonces debe tener 2 llaves: $a_{1}$ y $a_{2}$ . Todos los valores en el subárbol izquierdo serán inferiores a $a_{1}$ , todos los valores en el subárbol medio serán entre $a_{1}$ y $a_{2}$ , y todos los valores en el subárbol más adecuado será mayor que $a_{2}$ .

Por lo general, el número de llaves se elige para variar entre $d$ y $2d$ , donde $d$ es el número mínimo de llaves, y $d+1$ es el grado mínimo o factor ramificador del árbol. En la práctica, las llaves ocupan el mayor espacio en un nodo. El factor de 2 garantizará que los nodos pueden dividirse o combinarse. Si un nodo interno tiene $2d$ claves, luego añadir una llave a ese nodo se puede lograr dividiendo la hipotética $2d+1$ nodo clave en dos $d$ nodos clave y mover la llave que habría estado en el medio al nodo padre. Cada nodo de división tiene el número mínimo requerido de llaves. Del mismo modo, si un nodo interno y su vecino tienen cada uno $d$ llaves, entonces se puede eliminar una llave del nodo interno combinando con su vecino. Eliminar la llave haría que el nodo interno tuviera $d-1$ llaves; unirse al vecino añadiría $d$ llaves más una llave más derribada del padre del vecino. El resultado es un nodo totalmente completo $2d$ llaves.

El número de ramas (o nodos infantiles) de un nodo será uno más que el número de llaves almacenadas en el nodo. En un árbol de 2-3 B, los nodos internos almacenarán una llave (con dos nudos infantiles) o dos llaves (con tres nudos infantiles). A veces se describe un árbol B con los parámetros $(d+1)$ — $(2d+1)$ o simplemente con el orden de ramificación más alto, $(2d+1)$ .

Un árbol B se mantiene equilibrado después de la inserción dividiendo un nodo sobrefilado, de $2d+1$ llaves, en dos $d$ - hermanos clave e insertar la clave de valor medio en el padre. La profundidad sólo aumenta cuando la raíz se divide, manteniendo el equilibrio. Del mismo modo, un árbol B se mantiene equilibrado después de la eliminación fusionando o redistribuyendo claves entre hermanos para mantener el $d$ - Mínimo clave para nodos de raíz. Una fusión reduce el número de llaves en el padre potencialmente forzándolo a fusionar o redistribuir llaves con sus hermanos, y así sucesivamente. El único cambio en profundidad ocurre cuando la raíz tiene dos hijos, de $d$ y (transicionalmente) $d-1$ claves, en cuyo caso se fusionan los dos hermanos y padres, reduciendo la profundidad por uno.

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

Los árboles B tienen ventajas sustanciales sobre las implementaciones alternativas cuando el tiempo para acceder a los datos de un nodo supera con creces 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 se encuentran 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 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 debe almacenarse para cada nodo secundario y el 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 usan almacenamiento secundario necesitan una gran cantidad de nodos secundarios para mejorar el rendimiento.

Variantes

El término B-tree 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+ se almacenan copias de las llaves en los nodos internos; las llaves y los registros se almacenan en hojas; además, un nodo de hoja puede incluir un puntero al siguiente nodo de hoja para acelerar el acceso secuencial.
El B^* equilibrios de árboles más nodos internos vecinos para mantener los nodos internos más densamente empaquetados. Esta variante garantiza que los nodos no arraigados estén al menos 2/3 llenos en lugar de 1/2. Como la parte más costosa del funcionamiento de insertar el nodo en B-tree está dividiendo el nodo, B^*- Se crean árboles para posponer la operación de división siempre que puedan. Para mantener esto, en lugar de dividir inmediatamente un nodo cuando se llena, sus llaves se comparten con un nodo junto a él. Esta operación de derrame es menos costosa que dividir, porque sólo requiere cambiar las claves entre los nodos existentes, no asignar la memoria para uno nuevo. Para insertar, primero se comprueba si el nodo tiene algún espacio libre en él, y si es así, la nueva clave se inserta en el nodo. Sin embargo, si el nodo está lleno (tiene $m - 1$ llaves, donde $m$ es el orden del árbol como número máximo de punteros a subárboles de un nodo), necesita ser revisado si el hermano adecuado existe y tiene algún espacio libre. Si el hermano adecuado tiene $j . m - 1$ claves, entonces las claves se redistribuyen entre los dos nodos hermanos tan uniformemente como sea posible. Para ello, $m - 1$ claves del nodo actual, la nueva clave insertada, una clave del nodo padre y $j$ claves del nodo de hermano se ven como un conjunto ordenado de $m + j + 1$ llaves. El array se divide a la mitad, de modo que $⌊ () m + j + 1)/2 ⌋$ Las teclas más bajas permanecen en el nodo actual, la siguiente tecla (medio) se inserta en el padre y el resto va al hermano adecuado. (La llave recién insertada podría terminar en cualquiera de los tres lugares.) La situación cuando el hermano derecho está lleno, y la izquierda no es análoga. Cuando ambos los nodos hermanos están llenos, entonces los dos nodos (nodo actual y un hermano) se dividen en tres y una clave más se cambia el árbol, al nodo padre. Si el padre está lleno, la operación de derrame/split se propaga hacia el nodo raíz. Eliminar los nodos es algo más complejo que insertar sin embargo.
El B^*+ árbol combina el árbol B+ principal y B^* características de árbol juntos.
Los árboles B se pueden convertir en árboles estadísticos de orden para permitir búsquedas rápidas del registro Nth en orden clave, o contar el número de registros entre dos registros, y varias otras operaciones relacionadas.

Uso de árbol B en bases de datos

Tiempo para buscar un archivo ordenado

Por lo general, los algoritmos de clasificación y búsqueda se han caracterizado 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 registros $N$ , por ejemplo, se puede realizar en aproximadamente $⌈ log 2 N ⌉$ comparaciones. Si la tabla tuviera 1 000 000 de registros, entonces se podría ubicar un registro específico con un máximo de 20 comparaciones: $⌈ log 2 (1,000,000) ⌉ = 20$ .

Históricamente, grandes bases de datos se han mantenido en unidades de disco. El tiempo 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 de búsqueda de lectura promedio es de 8,5 milisegundos. Para simplificar, suponga que la lectura desde el disco tarda unos 10 milisegundos.

Ingenuamente, entonces, el tiempo para ubicar un registro entre un millón tomaría 20 lecturas de disco por 10 milisegundos por lectura de disco, 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 la cabeza 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 no necesitan realizar ninguna lectura de disco; todas las comparaciones están dentro de la última lectura de bloque de disco.

Para acelerar aún más la búsqueda, se deben acelerar las primeras 13 a 14 comparaciones (cada una de las cuales requería un acceso al disco).

Un índice acelera la búsqueda

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 usar 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) se refiera 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 en particular, 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, se refieren a filas específicas de la tabla.

Se puede lograr una mejora significativa en el rendimiento con un índice de árbol B. Debido a que cada nodo (o página interna) puede tener más de dos elementos secundarios, 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. Eso 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 solo ese bloque de la base de datos principal, a costa de una lectura de disco más. El índice tendría 10.000 entradas, por lo que tomaría 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. El índice se puede buscar en aproximadamente ocho lecturas de disco y se puede acceder al registro deseado en 9 lecturas de disco.

El truco de crear un índice auxiliar se puede repetir para crear un índice auxiliar para el índice auxiliar. Eso harí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. Leer y buscar el primer (y único) bloque del índice auxiliar-auxiliar que es la raíz del árbol identifica el bloque relevante en el índice auxiliar en el nivel inferior. Leer y buscar ese bloque de índice auxiliar identifica el bloque relevante para leer, hasta que el nivel final, conocido como nivel hoja, identifica un registro en la base de datos principal. En lugar de 150 milisegundos, solo necesitamos 30 milisegundos para obtener el registro.

Los índices auxiliares han convertido el problema de búsqueda de una búsqueda binaria que requiere aproximadamente $log 2 N$ lecturas de disco a uno requiriendo solo $log b N$ lecturas de disco donde estilo $b$ es el factor de bloqueo (el número de entradas por bloque: $b = 100$ entradas por bloque en nuestro ejemplo; $log 100 1,000,000 = 3$ lecturas).

En la práctica, si la base de datos principal se busca con frecuencia, el índice auxiliar-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 los utilizan.

Inserciones y eliminaciones

Si la base de datos no cambia, entonces compilar el índice es fácil de hacer y el índice nunca necesita cambiarse. 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 ordenada. Si hay una gran cantidad de eliminaciones diferidas, la búsqueda y el almacenamiento se vuelven menos eficientes.

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 primer registro requiere desplazar todos los registros uno hacia abajo. Tal operación 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 "borrados" registros.

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 algún espacio libre en algún bloque cercano y se deben ajustar los índices auxiliares. La esperanza es que haya suficiente espacio disponible cerca, de modo que no sea necesario reorganizar muchos bloques. Alternativamente, se pueden usar algunos bloques de disco fuera de secuencia.

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 teclas ordenadas para el rastreo secuencial
utiliza un índice jerárquico para minimizar el número de lecturas de disco
usa bloques parcialmente completos para acelerar las inserciones y eliminaciones
mantiene el índice equilibrado con un algoritmo recurrente

Además, un árbol B minimiza el desperdicio al asegurarse de que los nodos interiores estén al menos a la mitad. Un árbol B puede manejar un número arbitrario de inserciones y eliminaciones.

Alturas en el mejor y el peor de los casos

Sea h ≥ –1 la altura del árbol B clásico (ver Árbol (estructura de datos) § Terminología para la definición de la 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}

Vamos $d$ ser el número mínimo de niños que debe tener un nodo interno (no raíz). Para un árbol B común, ${displaystyle d=leftlceil m/2rightrceil.}$

Comer (1979) y Cormen et al. (2001) dan la altura del peor de los casos (la altura máxima) de un árbol B como

{displaystyle h_{mathrm {max} }=leftlfloor log _{d}{frac {n+1}{2}}rightrfloor.}

Algoritmos

Buscar

Buscar 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 usa típicamente (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 B Tree con cada iteración. Los nudos de este árbol B tienen a la mayoría de 3 niños (orden numérico 3).

Todas las inserciones comienzan en un nodo hoja. Para insertar un nuevo elemento, busque en el árbol para encontrar el nodo hoja donde se debe agregar el nuevo elemento. Inserte el nuevo elemento en ese nodo con los siguientes pasos:

Si el nodo contiene menos que el número máximo permitido de elementos, entonces hay espacio para el nuevo elemento. Inserte el nuevo elemento en el nodo, manteniendo los elementos del nodo ordenados.
De lo contrario, el nodo está lleno, dividido uniformemente en dos nodos así:
1. Se elige una sola mediana entre los elementos de la hoja y el nuevo elemento que se inserta.
2. Valores inferiores a la mediana se ponen en el nuevo nodo izquierdo y los valores superiores a la mediana se ponen en el nuevo nodo derecho, con la mediana actuando como un valor de separación.
3. El valor de separación se inserta en el padre del nodo, lo que puede causar que sea dividido, y así sucesivamente. Si el nodo no tiene padre (es decir, el nodo era la raíz), crear una nueva raíz sobre este nodo (aumento de la altura del árbol).

Si la división llega hasta la raíz, crea una nueva raíz con un solo valor de separador y dos elementos secundarios, 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. 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=2L 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=2L−1, entonces hay 2L−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 solo paso por el árbol desde la raíz hasta el nodo donde se realizará la inserción, dividiendo cualquier nodo completo que se encuentre en el camino de forma preventiva. Esto evita la necesidad de recuperar los nodos principales en la memoria, lo que puede resultar costoso si los nodos se encuentran en un almacenamiento secundario. Sin embargo, para usar 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 = 2L en lugar de U = 2L−1, lo que explica por qué algunos libros de texto imponen este requisito en la definición de árboles B.

Eliminación

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

Localizar y eliminar el artículo, luego reestructurar el árbol para retener sus invariantes, O
Hacer un solo paso por el árbol, pero antes de entrar (visitar) un nodo, reestructurar el árbol para que una vez que se encuentre la clave que se elimina, se puede eliminar sin desencadenar la necesidad de cualquier reestructuración adicional

El siguiente algoritmo utiliza la estrategia anterior.

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

El elemento en un nodo interno es un separador de sus nodos infantiles
Eliminar un elemento puede poner su nodo bajo el número mínimo de elementos y niños

Los procedimientos para estos casos están en orden a continuación.

Eliminación de un nodo hoja

Busque el valor para eliminar.
Si el valor está en un nodo de hoja, simplemente eliminarlo del nodo.
Si la subfluencia sucede, rebalance el árbol como se describe en la sección "Rebalancing after deletion" abajo.

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 que 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. 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 descrito a continuación:

Elija un nuevo separador (ya sea el elemento más grande del subárbol izquierdo o el elemento más pequeño del subárbol derecho), retírelo del nodo de hoja en el que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.
El paso anterior suprimió un elemento (el nuevo separador) de un nodo de hoja. Si ese nodo de hoja es ahora deficiente (tiene menos que el número requerido de nodos), entonces rebalance el árbol a partir del nodo de 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 dejado por debajo del tamaño mínimo, entonces se deben redistribuir algunos elementos para llevar todos los nodos al 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 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, girar a la izquierda
1. Copiar el separador del padre al final del nodo deficiente (el separador se mueve hacia abajo; el nodo deficiente ahora tiene el número mínimo de elementos)
2. Reemplazar el separador en el padre con el primer elemento del hermano adecuado (el hermano correcto pierde un nodo pero todavía 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, luego girar a la derecha
1. Copiar el separador del padre al comienzo del nodo deficiente (el separador se mueve hacia abajo; el nodo deficiente ahora tiene el número mínimo de elementos)
2. Reemplazar el separador en el padre con el último elemento del hermano izquierdo (el hermano izquierdo pierde un nodo pero todavía tiene al menos el número mínimo de elementos)
3. El árbol ahora está equilibrado
De lo contrario, si ambos hermanos inmediatos tienen sólo el número mínimo de elementos, luego se fusionan con un hermano sándwich de su separador quitado de sus padres
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 el número máximo de elementos, y el nodo derecho – vacío)
3. Quitar 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 líbralo y haz el nudo fusionado la nueva raíz (el árbol se vuelve más profundo)
  - De lo contrario, si el padre tiene menos que el número requerido de elementos, entonces reequilibrar el padre

Nota: Las operaciones de reabastecimiento son diferentes para los árboles B+ (por ejemplo, la rotación es diferente porque el padre tiene copia de la clave) y B^*- árbol (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 crece la base de datos, lo que genera más E/S aleatorias y desafíos de rendimiento.

Construcción inicial

Un caso especial común es agregar una gran cantidad de datos preordenados 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, una "carga a granel" El algoritmo se puede utilizar 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 encuentran en el extremo 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. Cuando se realiza una carga masiva, aprovechamos esto y, en lugar de dividir los nodos demasiado llenos de manera uniforme, los dividimos de la manera desigual posible: deje el nodo izquierdo completamente lleno y cree un nodo derecho con cero claves y un elemento secundario (en violación de las reglas habituales del árbol B).

Al final de la carga masiva, el árbol se compone casi en su totalidad de nodos completamente llenos; solo el nodo más a la derecha en cada nivel puede estar menos que lleno. Debido a que esos nodos también pueden estar menos de la mitad llenos, para restablecer las reglas normales del árbol B, combine dichos nodos con sus hermanos izquierdos (llenos garantizados) y divida las claves para producir al menos dos nodos. medio lleno. 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.

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 el acceso aleatorio rápido a un bloque arbitrario en un archivo particular. El problema básico es convertir el bloque de archivos $i$ dirección en un bloque de disco (o quizás a una dirección de cilindro).

Algunos sistemas operativos requieren que el usuario asigne el tamaño máximo del archivo cuando se crea el archivo. El archivo se puede asignar como bloques de disco contiguos. En ese caso, para convertir la dirección del bloque de archivos $i$ en una dirección del bloque de disco, el sistema operativo simplemente añade la dirección del bloque de archivos $i$ 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.

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 complicada.

MS-DOS, por ejemplo, utilizó una sencilla tabla de asignación de archivos (FAT). El FAT tiene una entrada para cada bloque de disco, y esa entrada identifica si su bloque es utilizado por un archivo y si es así, qué bloque (si hay) es el siguiente bloque de disco del mismo archivo. Por lo tanto, 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 $i$ , el sistema operativo (o utilidad de disco) debe seguir secuencialmente la lista de enlaces del archivo en el FAT. Peor, para encontrar un bloque de disco libre, debe escanear secuencialmente el FAT. Para MS-DOS, eso no era una penalidad enorme 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 discos duros tempranos), no había más de 4.080 entradas, y el FAT normalmente sería residente en memoria. A medida que los discos se hicieron más grandes, la arquitectura FAT comenzó a enfrentar sanciones. En un disco grande usando FAT, puede ser necesario realizar lecturas de disco para aprender la ubicación del disco de un bloque de archivos para ser leído o escrito.

TOPS-20 (y posiblemente TENEX) utilizó un árbol de 0 a 2 niveles que tiene similitudes con un árbol B. Un bloque de disco tenía 512 palabras de 36 bits. Si el archivo cabe en un bloque de palabras de 512 (2⁹), el directorio de archivos apuntará a ese bloque de disco físico. Si el archivo cabe en 2¹⁸ palabras, entonces el directorio apuntará 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 un bloque que contiene 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.

El sistema de archivos HFS+ y APFS de Apple, el NTFS de Microsoft, AIX (jfs2) y algunos sistemas de archivos de Linux, como btrfs y Ext4, usan á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.

Rendimiento

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

Variaciones

Simultaneidad de acceso

Lehman y Yao demostraron que se podían evitar todos los bloqueos de lectura (y, por lo tanto, mejorar mucho el acceso simultáneo) vinculando los bloques de árbol en cada nivel junto con un "siguiente" puntero. Esto da como resultado una estructura de árbol en la que 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 el acceso simultáneo 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 btree durante las operaciones normales. (Sin embargo, consulte varias estrategias para implementar la fusión de nodos y el código fuente en).

La patente estadounidense 5283894, concedida en 1994, parece mostrar una forma de utilizar un 'método de metaacceso' 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 en el caché de bloques. No se necesita reorganización para las eliminaciones y no hay 'siguiente' punteros en cada bloque como en Lehman y Yao.

Algoritmos paralelos

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

Contenido relacionado

Más resultados...