Árbol B

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de febrero de 2015; las comprobaciones requieren 46 ediciones .

B-tree (pronunciado en ruso como B-tree ) es una estructura de datos , un árbol de búsqueda. Desde el punto de vista de la representación lógica externa , un árbol equilibrado y muy ramificado . A menudo se utiliza para almacenar datos en la memoria externa.

El uso de árboles B fue propuesto por primera vez por R. Bayer y E. McCreight en 1970 .

Equilibrado significa que las longitudes de dos caminos cualesquiera desde la raíz hasta las hojas difieren en no más de uno.

La ramificación de un árbol es la propiedad de cada nodo del árbol para referirse a un gran número de nodos descendientes.

Desde el punto de vista de la organización física, el árbol B se representa como una estructura multilista de páginas de memoria, es decir, cada nodo del árbol corresponde a un bloque de memoria (página). Las páginas interiores y las hojas suelen tener una estructura diferente.

Aplicación

La estructura de árbol B se utiliza para organizar índices en muchos DBMS modernos .

Un árbol B se puede usar para estructurar (indexar) información en un disco duro (generalmente metadatos). El tiempo de acceso a un bloque arbitrario en un disco duro es muy largo (del orden de milisegundos), ya que está determinado por la velocidad de rotación del disco y el movimiento del cabezal. Por lo tanto, es importante reducir la cantidad de nodos escaneados en cada operación. Usar una búsqueda de lista cada vez para encontrar un bloque aleatorio podría llevar a un número excesivo de accesos al disco debido a la necesidad de pasar secuencialmente por todos sus elementos que preceden al dado, mientras que la búsqueda en el árbol B, debido a las propiedades de equilibrio y alta ramificación, puede reducir significativamente el número de tales operaciones.

La implementación relativamente simple de algoritmos y la existencia de bibliotecas listas para usar (incluidas las de C ) para trabajar con la estructura de árbol B hacen que dicha organización de memoria sea popular en una amplia variedad de programas que trabajan con grandes cantidades de datos.

Estructura y principios de construcción

Un árbol B es un árbol que cumple las siguientes propiedades:

Las claves de cada nodo suelen estar ordenadas para facilitar el acceso. La raíz contiene de 1 a 2t-1 claves. Cualquier otro nodo contiene de t-1 a 2t-1 claves. Las hojas no son una excepción a esta regla. Aquí t es un parámetro de árbol que es al menos 2 (y generalmente toma valores de 50 a 2000 [1] ).
Las hojas no tienen descendencia. Cualquier otro nodo que contenga claves , …, contiene hijos. Donde $K_1$ $K_n$ $n+1$
1. El primer hijo y todos sus hijos contienen claves del intervalo $(-\infty, K_1)$
2. Para , el hijo i-ésimo y todos sus hijos contienen claves del intervalo $2\le i\len$ $(K_{i-1}, K_i)$
3. $(n+1)$ -th hijo y todos sus hijos contienen claves del intervalo $(K_n,\infty)$
La profundidad de todas las hojas es la misma.

La propiedad 2 se puede establecer de otra manera: cada nodo del árbol B, excepto las hojas, se puede considerar como una lista ordenada en la que se alternan las claves y los punteros a los niños.

Buscar

Si la clave está contenida en la raíz, se encuentra. De lo contrario, determinamos el intervalo y vamos al descendiente correspondiente. Repetimos.

Agregar una clave

Llamaremos al árbol de descendientes de un determinado nodo un subárbol formado por este nodo y sus descendientes.

Primero, definamos una función que agregue la clave K al árbol hijo del nodo x. Después de ejecutar la función, en todos los nodos pasados, excepto, quizás, en el propio nodo x, habrá menos de , pero no menos de , claves. $2t-1$ $t-1$

Si x no es una hoja,
1. Determinamos el intervalo donde debe estar K. Sea y el hijo correspondiente.
2. Agregue recursivamente K al árbol descendiente de y.
3. Si el nodo y está lleno, es decir, contiene claves, lo partimos en dos. El nodo recibe la primera de las claves y y la primera de sus hijos, y el nodo recibe la última de las claves y y el último de sus hijos. La mediana de las claves del nodo y va al nodo x, y el puntero a y en el nodo x se reemplaza por punteros a los nodos y . $2t-1$ $y_1$ $t-1$ $t$ $y_2$ $t-1$ $t$ $y_1$ $y_2$
Si x es una hoja, simplemente agregue la clave K allí.

Ahora definamos agregar la clave K a todo el árbol. La letra R representa el nodo raíz.

Agregue K al árbol descendiente de R.
Si R ahora contiene claves, divídalo en dos. El nodo recibe la primera de las claves R y la primera de sus hijos, y el nodo recibe la última de las claves R y el último de sus hijos. La mediana de las claves del nodo R cae en el nodo recién creado, que se convierte en el nodo raíz. Los nodos se convierten en sus hijos . $2t-1$ $R_{1}$ $t-1$ $t$ $R_{2}$ $t-1$ $t$ $R_{1}$ $R_{2}$

Quitar una clave

Si la raíz también es una hoja, es decir, solo hay un nodo en el árbol, simplemente eliminamos la clave de este nodo. De lo contrario, primero encontramos el nodo que contiene la clave, recordando la ruta hacia él. Que este nodo sea . $X$

Si - hoja, elimine la clave de allí. Si quedan al menos al menos claves en el nodo , nos detenemos allí. De lo contrario, observamos la cantidad de claves en dos nodos hermanos vecinos. Si hay un nodo derecho vecino, y tiene al menos claves, agregamos a la clave separadora entre él y el nodo derecho vecino, y en lugar de esta clave colocamos la primera clave del nodo derecho vecino, después de lo cual nos detenemos . Si este no es el caso, pero hay un nodo izquierdo vecino, y tiene al menos claves, agregamos a la clave separadora entre este y el nodo izquierdo vecino, y en lugar de esta clave ponemos la última clave del nodo vecino nodo izquierdo, después de lo cual nos detenemos. Finalmente, si la tecla izquierda falla, fusionamos el nodo con el nodo derecho o izquierdo vecino y movemos la tecla que previamente separaba estos dos nodos al nodo fusionado. En este caso, solo las claves pueden permanecer en el nodo principal . Luego, si no es un root, realizamos un procedimiento similar con él. Si, como resultado, hemos llegado a la raíz y quedan de 1 a claves en ella, no es necesario hacer nada, porque la raíz puede tener menos claves. Si no queda una sola clave en la raíz, excluimos el nodo raíz y hacemos que su único hijo sea la nueva raíz del árbol. $X$ $X$ $t-1$ $t$ $X$ $t$ $X$ $X$ $t-2$ $t-1$ $t-1$

Si no es una hoja, y K es su clave -ésima, elimine la clave más a la derecha del subárbol de descendientes del -ésimo descendiente o, por el contrario, la clave más a la izquierda del subárbol de descendientes del -ésimo descendiente . Después de eso, reemplazamos la tecla K con la tecla remota. La eliminación de la clave se produce como se describe en el párrafo anterior. $X$ $i$ $i$ $X$ $yo+1$ $X$

Principales ventajas

En todos los casos, el uso útil del espacio de almacenamiento secundario es superior al 50%. Con el aumento de la utilización de la memoria, no hay disminución en la calidad del servicio.
El acceso aleatorio al registro se implementa a través de un pequeño número de suboperaciones (referencias a bloques físicos).
En promedio, las operaciones de inclusión y eliminación de registros se implementan con bastante eficiencia; manteniendo el orden natural de las claves para el procesamiento secuencial, así como el equilibrio adecuado del árbol para garantizar un muestreo aleatorio rápido.
La ordenación inmutable por clave permite un procesamiento por lotes eficiente.

La principal desventaja de los árboles B es que no tienen un medio eficiente para recuperar datos (es decir, un método de recorrido de árboles) ordenados por una propiedad distinta a la clave elegida.

Véase también

Primera búsqueda en profundidad
Primera búsqueda en amplitud
Árboles equilibrados (autoequilibrados):

árbol AVL
árbol matriz
Árbol perfectamente equilibrado
árbol en expansión
árboles B+
2-3-árbol
R-árbol
árbol B*
árbol rojo-negro

Lista de estructuras de datos (árboles)

Notas

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Capítulo 18. B-Trees // Algoritmos: Construcción y Análisis = Introducción a los Algoritmos. - 2ª ed. - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Literatura

Levitin A. V. Capítulo 7. Compromiso espacio-tiempo: árboles B // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 331-339. — 576 pág. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Capítulo 18. B-Trees // Algoritmos: Construcción y Análisis = Introducción a los Algoritmos. - 2ª ed. - M .: Williams , 2006. - S. 515-536. — ISBN 0-07-013151-1 .

Enlaces

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión