En informática , un árbol B es una estructura de datos de árbol autoequilibrada que mantiene los 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 adecuado para sistemas de almacenamiento que leen y escriben bloques de datos relativamente grandes, como discos. Se usa comúnmente en bases de datos y sistemas de archivos .
Árbol B | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | Árbol (estructura de datos) | ||||||||||||||||||||
Inventado | 1970 [1] | ||||||||||||||||||||
Inventado por | Rudolf Bayer , Edward M. McCreight | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
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 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] 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 , equilibrado , ancho , tupido y Bayer . [4] [5] [6] McCreight ha dicho que "cuanto más piensas en lo que significa B en á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:
- Cada nodo tiene como máximo m hijos.
- Cada nodo no hoja (excepto la raíz) tiene al menos ⌈ m / 2⌉ nodos secundarios.
- La raíz tiene al menos dos hijos si no es un nodo hoja.
- Un nodo no hoja con k hijos contiene k - 1 claves.
- Todas las hojas aparecen en el mismo nivel y no contienen información.
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 1 y un 2 . Todos los valores en el subárbol más a la izquierda serán menos de un 1 , todos los valores en el subárbol medio será de entre un 1 y un 2 , y todos los valores en el subárbol más a la derecha será mayor que un 2 .
- Nodos internos
- Los 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 niños y un mínimo de L niños. Por lo tanto, el número de elementos es siempre 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 se pueden unir dos nodos medio llenos para crear un nodo legal, y un nodo completo se puede dividir 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 hijos 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 de L -1 elementos en todo el árbol, la raíz será el único nodo del árbol sin hijos.
- Nodos de hoja
- En la terminología de Knuth, los nodos hoja no contienen información. Los nodos internos que están un nivel por encima de las hojas son lo que otros autores llamarían "hojas": estos nodos solo almacenan claves (como máximo m -1, y al menos m / 2-1 si no son la raíz) y punteros a nodos que no contienen información.
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 ocurre 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 hoja y utilizan diferentes tipos de nodos para los nodos hoja y los nodos internos. Los árboles B mantienen valores en todos los nodos del árbol, excepto en los nodos hoja.
Diferencias en terminología
La literatura sobre árboles B no es uniforme en su terminología. [7]
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. [8] señala 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 llaves o un máximo de 7 llaves. Knuth (1998) evita el problema definiendo el orden como el número máximo de hijos (que es uno más que el número máximo de claves). [9]
El término hoja también es inconsistente. Bayer y McCreight (1972) [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 solo pueden contener indicadores del registro de datos. Esas elecciones no son fundamentales para la idea de un árbol B. [11]
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, se pueden emplear llaves de longitud variable. [12]
Descripción informal
En los árboles B, los nodos internos ( no hoja ) 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 del número de nodos secundarios suelen ser fijos para una implementación en 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 claves . Las claves 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), debe tener 2 claves: y . Todos los valores en el subárbol más a la izquierda serán menores que, todos los valores en el subárbol medio estarán entre y , y todos los valores en el subárbol más a la derecha serán mayores que .
Por lo general, el número de llaves se elige para variar entre y , dónde es el número mínimo de claves, y es el grado mínimo o factor de ramificación del árbol. En la práctica, las claves ocupan la mayor parte del espacio en un nodo. El factor 2 garantizará que los nodos se puedan dividir o combinar. Si un nodo interno tiene claves, luego agregar una clave a ese nodo se puede lograr dividiendo el hipotético nodo clave en dos nodos clave y moviendo la clave que habría estado en el medio al nodo principal. Cada nodo dividido tiene el número mínimo de claves requerido. Del mismo modo, si un nodo interno y su vecino tienenclaves, entonces una clave puede eliminarse del nodo interno combinándola con su vecino. Eliminar la clave haría que el nodo interno tuvierallaves; unirse al vecino agregaríallaves más una llave más traída del padre del vecino. El resultado es un nodo completamente completo de llaves.
El número de ramas (o nodos secundarios) de un nodo será uno más que el número de claves almacenadas en el nodo. En un árbol B 2-3, los nodos internos almacenarán una clave (con dos nodos secundarios) o dos claves (con tres nodos secundarios). A veces, un árbol B se describe con los parámetros- o simplemente con el orden de ramificación más alto, .
Un árbol B se mantiene equilibrado después de la inserción dividiendo un posible nodo sobrellenado, de llaves, en dos -key hermanos e insertando la clave de valor medio en el padre. La profundidad solo aumenta cuando la raíz se divide, manteniendo el equilibrio. De manera similar, un árbol B se mantiene equilibrado después de la eliminación mediante la fusión o redistribución de claves entre hermanos para mantener el-clave mínima para nodos no raíz. Una fusión reduce el número de claves en el padre potencialmente obligándolo a fusionar o redistribuir claves con sus hermanos, y así sucesivamente. El único cambio de profundidad ocurre cuando la raíz tiene dos hijos, de y (transitoriamente) claves, en cuyo caso los dos hermanos y el padre se fusionan, reduciendo la profundidad en uno.
Esta profundidad aumentará lentamente a medida que se agreguen elementos al árbol, pero un aumento en la profundidad general es poco frecuente y hace que todos los nodos de las hojas estén un nodo más lejos de la raíz.
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 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 se encuentran en un almacenamiento secundario , como unidades de disco . Al maximizar el número de claves dentro de cada nodo interno , la altura del árbol disminuye y se reduce el número de accesos costosos a los nodos. Además, el reequilibrio del árbol 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–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 + y el árbol B * .
- En el árbol B + , las copias de las claves se almacenan en los nodos internos; las claves y registros se almacenan en hojas; además, un nodo hoja puede incluir un puntero al siguiente nodo hoja para acelerar el acceso secuencial. [2]
- 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 no raíz estén llenos al menos 2/3 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 al lado. Esta operación de derrame es menos costosa de hacer que dividir, porque solo requiere cambiar las claves entre los nodos existentes, no asignar memoria para uno nuevo. [14] Para la inserción, primero se comprueba si el nodo tiene algún espacio libre, 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 de un nodo), se debe verificar si el hermano correcto 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 de la manera más uniforme posible. Para este propósito, las claves m - 1 del nodo actual, la clave nueva insertada, una clave del nodo principal y las claves j del nodo hermano se ven como una matriz ordenada de claves m + j + 1 . La matriz se divide por la mitad, de modo que las claves ⌊ ( m + j + 1) / 2⌋ más bajas permanecen en el nodo actual, la siguiente clave (intermedia) se inserta en el padre y el resto va al hermano derecho. [14] (La clave recién insertada podría terminar en cualquiera de los tres lugares). La situación cuando el hermano derecho está lleno y el izquierdo no es análogo. [14] 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 principal. [14] Si el padre está lleno, la operación de derrame / división se propaga hacia el nodo raíz. [14] Sin embargo, eliminar nodos es algo más complejo que insertar.
- Los árboles B se pueden convertir en árboles de estadísticas de orden para permitir búsquedas rápidas del registro N en orden clave, o contar el número de registros entre dos registros y otras operaciones relacionadas. [15]
Uso del árbol B en bases de datos
Es hora de buscar un archivo ordenado
Por lo general, 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 2 N ⌉ . 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, las grandes bases de datos se han guardado 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 milisegundos o más, y el retardo 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 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. [16] Para simplificar, suponga que la lectura del disco tarda unos 10 milisegundos.
Entonces, ingenuamente, el tiempo para localizar un registro de 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 de 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 hacer ninguna lectura de disco; todas las comparaciones se encuentran 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 requiere 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, atravesando 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.
Una mejora significativa en el rendimiento se puede hacer con un árbol B de índice . 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. 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 sólo en ese bloque de la base de datos principal, a costa de una lectura más de disco. El índice contendría 10,000 entradas, por lo que se necesitarían como máximo 14 comparaciones. Como 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 nueve lecturas de disco.
El truco de crear un índice auxiliar se puede repetir para hacer un índice auxiliar al índice auxiliar. Eso haría un índice aux-aux 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 la 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 la búsqueda de 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 cambiado el problema de búsqueda de una búsqueda binaria que requiere aproximadamente log 2 N lecturas de disco a una que solo requiere 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 100 1,000,000 = 3 lecturas).
En la práctica, si se busca con frecuencia en la base de datos principal, el índice aux-aux y gran parte del índice aux pueden residir en una 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 las usan. [17]
Inserciones y eliminaciones
Si la base de datos no cambia, entonces compilar el índice es fácil de hacer y nunca es necesario cambiar el índice. Si hay cambios, la administració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 se puede marcar como eliminado. La base de datos permanece en orden. Si hay una gran cantidad de eliminaciones, la búsqueda y el almacenamiento se vuelven menos eficientes.
Las inserciones pueden ser muy lentas en un archivo secuencial ordenado porque se debe dejar espacio para el registro insertado. Insertar un registro antes del primer registro requiere desplazar todos los registros hacia abajo. Una operación de este tipo es demasiado cara 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 usar algunos bloques de disco fuera de secuencia.
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 ordenado para el desplazamiento 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 al menos medio llenos. Un árbol B puede manejar un número arbitrario de inserciones y eliminaciones.
Alturas en el mejor y peor caso
Sea h ≥ –1 la altura del árbol B clásico (consulte Á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 mejor altura de caso (es decir, la altura mínima) de un árbol B es:
Dejar ser el número mínimo de hijos que puede tener un nodo interno (no raíz). Para un árbol B ordinario,
Comer (1979) y Cormen et al. (2001) dan la altura del peor caso (la altura máxima) de un árbol B como [18]
Algoritmos
Buscar
La búsqueda es similar a la búsqueda en un árbol de búsqueda binaria. Comenzando en la raíz, el árbol se recorre de forma recursiva 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 padre. 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
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 de la cantidad máxima permitida de elementos, entonces hay espacio para el nuevo elemento. Inserte el nuevo elemento en el nodo, manteniendo ordenados los elementos del nodo.
- De lo contrario, el nodo está lleno, divídalo uniformemente en dos nodos para que:
- Se elige una sola mediana entre los elementos de la hoja y el nuevo elemento.
- 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, con la mediana actuando como un valor de separación.
- El valor de separación se inserta en el padre del nodo, lo que puede hacer 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 solo valor de 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. 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 lo tanto es un nodo legal, y el otro contiene un elemento más, y por lo tanto es 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 una sola pasada por el árbol desde la raíz hasta el nodo donde se llevará a cabo la inserción, dividiendo los nodos completos que se encuentren en el camino de forma preventiva. Esto evita la necesidad de recuperar los nodos principales en la memoria, lo que puede resultar caro si los nodos están 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 = 2 L en lugar de U = 2 L −1, lo que explica por qué algunos [ ¿cuál? ] los libros de texto imponen este requisito al definir árboles B.
Supresión
Hay dos estrategias populares para la eliminación de un árbol B.
- Busque y elimine el elemento, luego reestructura el árbol para conservar sus invariantes, O
- Haga una sola pasada por el árbol, pero antes de ingresar (visitar) un nodo, reestructura 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:
- El elemento de un nodo interno es un separador de sus nodos secundarios.
- Eliminar un elemento puede poner su nodo en el número mínimo de elementos y elementos secundarios
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 hoja, simplemente elimínelo del nodo.
- Si ocurre 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 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 del 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 los nodos de las hojas y cualquiera de ellos puede ser el nuevo separador de los dos subárboles. Descrito algorítmicamente a continuación:
- 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.
- El paso anterior eliminó un elemento (el nuevo separador) de un nodo hoja. Si ese nodo hoja ahora es deficiente (tiene menos de la cantidad requerida de nodos), 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 se equilibra. Si eliminar un elemento de un nodo lo ha reducido al tamaño mínimo, entonces algunos elementos deben redistribuirse 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 combinació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: [ cita requerida ]
- Si el hermano derecho del nodo deficiente existe y tiene más de la cantidad mínima de elementos, entonces gire a la izquierda
- Copie 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)
- 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)
- El árbol ahora está equilibrado
- De lo contrario, si el hermano izquierdo del nodo deficiente existe y tiene más de la cantidad mínima de elementos, entonces gire a la derecha
- Copie el separador del padre al inicio del nodo deficiente (el separador se mueve hacia abajo; el nodo deficiente ahora tiene el número mínimo de elementos)
- 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)
- El árbol ahora está equilibrado
- De lo contrario, si ambos hermanos inmediatos tienen solo el número mínimo de elementos, se fusionan con un hermano intercalando su separador separado de su padre
- 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)
- 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)
- Elimina 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 combinado en la nueva raíz (el árbol se vuelve menos profundo)
- De lo contrario, si el padre tiene menos de la cantidad requerida de elementos, reequilibre el padre
- Nota : Las operaciones de reequilibrio son diferentes para los árboles B + (p. Ej., La rotación es diferente porque el padre tiene una copia de la clave) y el árbol B * (p. Ej., 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. [19]
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 bastante 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 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 están 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 realizarán más inserciones en la mitad izquierda. Al realizar la carga masiva, aprovechamos esto y, en lugar de dividir los nodos excesivamente llenos de manera uniforme, los dividimos de la manera más desigual posible: deje el nodo izquierdo completamente lleno y cree un nodo derecho con claves cero y un hijo (en violación de la B- habitual) reglas del árbol).
Al final de la carga a granel, el árbol está compuesto casi en su totalidad por 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 tener menos de la mitad de su capacidad, para restablecer las reglas normales del árbol B, combine dichos nodos con sus hermanos izquierdos (completos garantizados) y divida las claves para producir dos nodos al menos a la mitad. 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 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 el bloque de archivosdirección en un bloque de disco (o quizás en un sector de culata de cilindro ) dirección.
Algunos sistemas operativos requieren que el usuario asigne el tamaño máximo del archivo cuando se crea el archivo. A continuación, 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 de 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.
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 tabla de asignación de archivos (FAT) simple . El 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 del disco del bloque de archivos, el sistema operativo (o la 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 la FAT tenía pocas entradas y cadenas de archivos relativamente cortas. En el sistema de archivos FAT12 (utilizado en los disquetes y los 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 usa FAT, puede ser necesario realizar lecturas de disco para conocer la ubicación del disco de un bloque de archivo que se va a leer o escribir.
TOPS-20 (y posiblemente TENEX ) utilizó un árbol de 0 a 2 niveles que tiene similitudes con un árbol B [ cita requerida ] . Un bloque de disco tenía 512 palabras de 36 bits. Si el archivo encaja en un bloque de 512 (2 9 ) palabras, el directorio de archivos apuntará a ese bloque de disco físico. Si el archivo encaja en 2 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 encaja en 2 27 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 27 palabras podría ubicarse en dos lecturas de disco y leer en la tercera.
El sistema de archivos HFS + de Apple , el NTFS de Microsoft , [20] AIX (jfs2) y algunos sistemas de archivos Linux , como 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. [21]
Actuación
Un árbol B crece más lento con la creciente cantidad de datos que la linealidad de una lista enlazada. En comparación con una lista de omisión, ambas estructuras tienen el mismo rendimiento, pero el árbol B escala mejor para el crecimiento de n . Un árbol T , para los sistemas de bases de datos de memoria principal , es similar pero más compacto.
Variaciones
Simultaneidad de acceso
Lehman y Yao [22] demostraron que todos los bloqueos de lectura podrían evitarse (y por lo tanto el acceso simultáneo se mejoraría enormemente) vinculando los bloques del árbol en cada nivel junto con un puntero "siguiente". Esto da como resultado una estructura de árbol en la que tanto las operaciones de inserción como las de búsqueda descienden de la raíz a la hoja. Los bloqueos de escritura solo son necesarios cuando se modifica un bloque de árbol. Esto maximiza la concurrencia de acceso 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 árbol b durante las operaciones normales. (Sin embargo, consulte [23] para conocer varias estrategias para implementar la fusión de nodos y el código fuente en [24] ).
La patente de los Estados Unidos 5283894, concedida en 1994, parece mostrar una forma de utilizar un "método de meta acceso" [25] 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 la caché de bloques. No se necesita reorganización para eliminaciones y no hay punteros 'siguientes' en cada bloque como en Lehman y Yao.
Algoritmos paralelos
Desde los árboles B son similares en estructura a árboles rojo-negro , algoritmos paralelos para árboles de color rojo-negro se pueden aplicar a los árboles B también.
Ver también
- Árbol B +
- Árbol R
- Árbol rojo-negro
- 2-3 árboles
- 2–3–4 árboles
Notas
- ^ Para FAT, lo que se llama un "bloque de disco" aquí es lo que la documentación de FAT llama un "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 clúster no tiene una diferencia significativa de un sector físico.
- ^ Dos de estos se reservaron para fines especiales, por lo que solo 4078 podrían representar bloques de disco (clústeres).
Referencias
- ^ a b Bayer, R .; McCreight, E. (julio de 1970). "Organización y mantenimiento de grandes índices ordenados" (PDF) . Actas del taller de 1970 ACM SIGFIDET (ahora SIGMOD) 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 .
- ^ a b c d Comer 1979 .
- ^ a b c Bayer y McCreight 1972 .
- ^ Comer 1979 , p. 123 nota al pie 1.
- ^ a b Weiner, Peter G. (30 de agosto de 2013). "4- Edward M McCreight" - vía Vimeo.
- ^ "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 .
- ^ Folk y Zoellick 1992 , p. 362.
- ^ Folk y Zoellick 1992 .
- ^ Knuth 1998 , p. 483.
- ^ Folk y Zoellick 1992 , p. 363.
- ↑ 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 realmente no importaba. Bayer y McCreight (1972) afirman: "Para este artículo, la información asociada no tiene más interés".
- ^ Folk y Zoellick 1992 , p. 379.
- ^ Knuth 1998 , p. 488.
- ^ a b c d e f Tomašević, Milo (2008). Algoritmos y estructuras de datos . Belgrado, Serbia: Akademska misao. págs. 274-275. ISBN 978-86-7466-328-8.
- ^ Árboles B contados , consultado el 25 de enero de 2010
- ^ Seagate Technology LLC, Manual del producto: Barracuda ES.2 Serial ATA, Rev. F., publicación 100468393, 2008 [1] , página 6
- ^ Kleppmann, Martin (2017), Designing Data-Intensive Applications , Sebastopol, California : O'Reilly Media , p. 80, ISBN 978-1-449-37332-0
- ^ Comer 1979 , p. 127; Cormen y col. 2001 , págs. 439–440
- ^ "Caché de árboles B ajenos" . Universidad Estatal de Nueva York (SUNY) en Stony Brook . Consultado el 17 de enero de 2011 .
- ^ Mark Russinovich . "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 .
- ^ Matthew Dillon (21 de junio de 2008). "El sistema de archivos HAMMER" (PDF) .
- ^ Lehman, Philip L .; Yao, s. Bing (1981). "Bloqueo eficiente para operaciones concurrentes en árboles B". Transacciones ACM en sistemas de bases de datos . 6 (4): 650–670. doi : 10.1145 / 319628.319663 . S2CID 10756181 .
- ^ http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf
- ^ "Descargas - btree de alta concurrencia - código de árbol B de alta concurrencia en C - Alojamiento de proyectos de GitHub" . Consultado el 27 de enero de 2014 .
- ^ "Método de acceso meta de índice de árbol B simultáneo sin bloqueo para nodos en caché" .
- General
- Bayer, R .; McCreight, E. (1972), "Organización y mantenimiento de índices ordenados grandes" (PDF) , Acta Informatica , 1 (3): 173–189, doi : 10.1007 / bf00288683 , S2CID 29859053
- Comer, Douglas (junio de 1979), "The Ubiquitous B-Tree", Computing Surveys , 11 (2): 123–137, doi : 10.1145 / 356770.356776 , ISSN 0360-0300 , S2CID 101673.
- Cormen, Thomas ; 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: B-Trees.
- Folk, Michael J .; Zoellick, Bill (1992), Estructuras de archivos (2.a ed.), Addison-Wesley, ISBN 0-201-55713-4
- Knuth, Donald (1998), Clasificación y búsqueda , El arte de la programación informática , Volumen 3 (Segunda ed.), Addison-Wesley, ISBN 0-201-89685-0
|volume=
tiene texto extra ( ayuda ). Sección 6.2.4: Árboles de múltiples vías, págs. 481–491. Además, las páginas 476–477 de la sección 6.2.3 (Árboles equilibrados) discuten 2–3 árboles.
Papeles originales
- Bayer, Rudolf ; McCreight, E. (julio de 1970), Organización y mantenimiento de índices ordenados grandes , Informe núm. 20 de ciencias de la información y matemáticas, Laboratorios de investigación científica de Boeing.
- Bayer, Rudolf (1971), Árboles B binarios para memoria virtual , Actas del Taller de 1971 ACM-SIGFIDET sobre descripción, acceso y control de datos, San Diego, California.
enlaces externos
- Conferencia de árbol B por David Scot Taylor, SJSU
- Visualización de B-Tree (haga clic en "init")
- Visualización animada del árbol B
- Árbol B y árbol UB en Scholarpedia Curador: Dr. Rudolf Bayer
- Árboles B: estructuras de datos de árboles equilibrados
- Diccionario de NIST de algoritmos y estructuras de datos: árbol B
- Tutorial de árbol B
- La implementación de InfinityDB BTree
- Caché ajeno B (+) - árboles
- Entrada del Diccionario de algoritmos y estructuras de datos para árbol B *
- Estructuras de datos abiertos - Sección 14.2 - Árboles B , Pat Morin
- Árboles B contados
- B-Tree .Net, una implementación moderna y virtualizada de RAM y disco
Carga a granel
- 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.
- "ECS 165B: Implementación del sistema de base de datos: Conferencia 6" (PDF) . Universidad de California, Davis . 9 de abril de 2010. p. 23.
- "INSERTAR A GRANEL (Transact-SQL) en SQL Server 2017" . Microsoft Docs. El 6 de septiembre de 2018.