Á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 7 de febrero de 2022; la verificación requiere 1 edición .

B⁺-tree es una estructura de datos basada en un B-tree , un árbol de búsqueda equilibrado con un número variable pero a menudo grande de elementos secundarios por nodo. Un árbol B⁺ consta de una raíz, nodos internos y hojas, la raíz puede ser una hoja o un nodo con dos o más hijos. $norte$

Inicialmente, la estructura estaba destinada a almacenar datos para una búsqueda eficiente en un entorno de almacenamiento orientado a bloques, en particular, para sistemas de archivos; La aplicación se debe al hecho de que, a diferencia de los árboles de búsqueda binarios, los árboles B⁺ tienen un factor de ramificación muy alto (el número de punteros de un nodo padre a los hijos suele ser del orden de 100 o más), lo que reduce el número de Operaciones de E/S que requieren buscar un elemento en el árbol.

Una variante del árbol B⁺, en la que todos los valores se almacenaban en nodos de hoja, se revisó sistemáticamente en 1979 [1] , y se señaló que IBM ha utilizado tales estructuras en la tecnología de acceso a archivos de mainframe VSAM desde al menos 1973.

La estructura se usa ampliamente en sistemas de archivos: NTFS , ReiserFS , NSS , XFS , JFS , ReFS y BFS usan este tipo de árbol para indexar metadatos; BeFS también usa árboles B⁺ para almacenar directorios. Los sistemas de administración de bases de datos relacionales como DB2 , Informix , Microsoft SQL Server , Oracle Database (desde la versión 8), Adaptive Server Enterprise y SQLite admiten este tipo de árbol para índices de tablas. Entre los DBMS NoSQL que trabajan con el modelo clave-valor, la estructura de datos se implementa para el acceso a datos en CouchDB , MongoDB (cuando se usa el subsistema de almacenamiento WiredTiger ) y Tokyo Cabinet .

Descripción

Un árbol B⁺ es un árbol de búsqueda de orden (o grado) balanceado que satisface las siguientes propiedades: $norte$ $yo,$

Cada nodo contiene al menos una clave; las claves en cada nodo están ordenadas, la raíz contiene claves from to , cualquier otro nodo contiene claves from to ; Las hojas no son una excepción a esta regla. Aquí , hay un parámetro de árbol que es al menos 2 (y normalmente toma valores de 50 a 2000 según el tamaño de la clave en relación con el tamaño de la página, que a su vez está determinado por el tamaño del registro de contenido). $una$ $2t-1$ ${\ estilo de texto t-1}$ ${\ estilo de texto 2t-1}$ ${\ estilo de texto t}$
Las hojas no tienen descendencia; para todos los demás nodos que contienen claves, el nodo dado contiene elementos secundarios. Donde: $K_{1},\puntos,K_{n},$ $(n+1)$
- el primer hijo y todos sus hijos contienen claves del intervalo $(-\infty,K_{1});$
- para el -ésimo hijo y todos sus hijos contienen claves del intervalo $2 \leqslant i \leqslant n$ $i$ ${\ estilo de visualización (K_{i-1},K_{i});}$
- $(n+1)$ -th hijo y todos sus hijos contienen claves del intervalo ${\ estilo de visualización (K_ {n}, \ infinito).}$
La profundidad de todas las hojas es la misma.
Las hojas tienen un enlace a un vecino que le permite recorrer rápidamente el árbol en orden ascendente de claves y enlaces a datos.

Edificio

La construcción de un árbol B⁺ puede requerir la reconstrucción de la estructura intermedia, esto se debe al hecho de que el número de claves en cada nodo (excepto la raíz) debe ser de a donde es el grado (u orden) del árbol. Cuando intenta insertar la tecla ( )-ésima en el nodo, es necesario separar este nodo; la tecla ( )-ésima, que se coloca en el nivel adyacente del árbol, actúa como la tecla separadora de las ramas formadas . Un caso especial es la división de la raíz, ya que en este caso aumenta el número de niveles del árbol. Una característica de dividir una hoja de un árbol B⁺ es que se divide en partes desiguales. Dividir un nodo interno o raíz da como resultado nodos con el mismo número de claves. Dividir una hoja puede causar una "reacción en cadena" de nodos divididos, que terminan en la raíz. $t$ ${\ estilo de visualización 2t,}$ $t$ $2t+1$ ${\ estilo de texto t+1}$ $k.$

Propiedades de la estructura

En un árbol B⁺, la independencia del programa de la estructura del registro de información se realiza fácilmente.
La búsqueda termina necesariamente en una hoja.
Borrar una clave tiene la ventaja de que el borrado siempre se produce desde la hoja.
Otras operaciones se realizan de manera similar a los árboles B.
Los árboles B⁺ requieren más memoria para representarse que los árboles B clásicos.
Los árboles B⁺ tienen la capacidad de acceder a las claves secuencialmente.

Operaciones básicas sobre una estructura

Buscar

La raíz del árbol B⁺ es el punto de partida para todo el rango de valores, en el que cada nodo interno es un subintervalo.

Por ejemplo, digamos que necesitamos encontrar el valor de una clave en un árbol B⁺. Para hacer esto, buscamos un nodo hoja que contenga el valor En cada nodo interno, necesitamos averiguar qué nodo secundario posterior seguir, el nodo interno del árbol B⁺ tiene como máximo hijos, donde cada uno de ellos representa un subintervalo separado. El nodo apropiado se selecciona buscando en los valores clave del nodo: $k$ $k.$ $t$

Función : buscar ( k ) return tree_search ( k , root ); Función : tree_search ( k , nodo ) si el nodo es una hoja , devuelve el nodo ; switch k do case k < k [ 0 ] return tree_search ( k , p [ 0 ]); case k [ i ] ≤ k < k [ i + 1 ] return tree_search ( k , p [ i + 1 ]); case k [ d ] ≤ k return tree_search ( k , p [ d + 1 ]);

(Este pseudocódigo asume que se ignoran los duplicados).

Agregando

Para agregar una nueva clave o una nueva entrada, primero debe encontrar el nodo donde desea agregarlos. En este caso, el algoritmo es:

Si el nodo no está completamente lleno (la cantidad de elementos después de la inserción no es más que ), agregue una clave (registro). ${\ estilo de visualización 2t-1,}$
De lo contrario, debe dividir el nodo:
- cree un nuevo nodo, luego mueva la mitad de los elementos del actual al nuevo;
- agregue la clave más pequeña del nuevo nodo y la dirección (el nodo) al padre;
- si el nodo principal está lleno, divídalo de manera similar:
  - agregue la clave central al nodo principal;
- repita hasta que el nodo principal necesite dividirse.
Si la raíz se divide, cree una nueva raíz con una clave y dos punteros (la clave que se agrega a la raíz se elimina de su nodo)

Los árboles B, a diferencia de los árboles B⁺, se expanden desde el lado de la raíz, no desde las hojas.

Eliminación

Para eliminar una clave o entrada, primero debe encontrar el nodo de hoja en el que reside. Algoritmo para eliminar de un nodo hoja:

Si el nodo está al menos medio lleno, el algoritmo termina;
Si el nodo tiene menos elementos, entonces:
- intente redistribuir elementos, es decir, agregue un elemento del "hermano" al nodo, un elemento con un ancestro común.
- si la redistribución falla, combine el nodo con el "hermano".
Si se produce una fusión, elimine la clave o la entrada que apunta al nodo remoto o su "hermano" del nodo principal.

La unión puede extenderse hasta la raíz, en cuyo caso la altura del árbol disminuye.

Complejidad computacional de las operaciones

La complejidad computacional de cada operación en el peor de los casos: donde es el orden del árbol o el factor de ramificación; es el número de elementos en el árbol de ramas en los nodos del árbol. $O(\log {\frac {t}{2n)))$ $t$ $norte$

Notas

↑ Douglas Comer. El omnipresente B-Tree // Encuestas informáticas de ACM. - 1979. - junio ( vol. 11 , n. 2 ). - pág. 121-137 . — ISSN 0360-0300 . Archivado desde el original el 17 de noviembre de 2015.

Literatura

Zubov V. S., Shevchenko I. V. Capítulo 6. Búsqueda en árboles no binarios - B-trees // Estructuras y métodos de procesamiento de datos. Taller en el entorno Delphi. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Generación de todos los árboles. Historia de la generación combinatoria // El arte de la programación = El arte de la programación informática. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Enlaces

Visualizador de árboles B⁺ - Visualización de árboles B+

Á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