Árbol B+

Al igual que otros árboles, los árboles B+ se pueden representar como una colección de tres tipos de nodos: raíz , interno (también llamado interior) y hoja . En los árboles B+, se mantienen las siguientes propiedades para estos nodos:

• Si${\textstyle k_{i}}$existe en cualquier nodo de un árbol B+, entonces k _{i -1} existe en ese nodo donde${\displaystyle i\geq 1}$.
• Todos los nodos hoja tienen el mismo número de ancestros (es decir, todos están a la misma profundidad).

Las propiedades de puntero de los nodos se resumen en las tablas siguientes:

• K : Número máximo de claves de búsqueda potenciales para cada nodo en un árbol B+. (Este valor es constante en todo el árbol).
• p _i : El puntero en el índice de nodo basado en cero i .
• k _i : La clave de búsqueda en el índice de nodo basado en cero i .

Los límites de los nodos se resumen en la tabla siguiente: ^{[ 4 ] [ 5 ]}

Por definición, cada valor contenido en el árbol B+ es una clave contenida en un único nodo hoja. Cada clave debe ser directamente comparable con todas las demás, lo que forma un orden total . ^{[ 6 ]} Esto permite que cada nodo hoja mantenga todas sus claves ordenadas en todo momento, lo que a su vez permite que cada nodo interno construya una colección ordenada de intervalos que representan la extensión contigua de los valores contenidos en una hoja dada. Los nodos internos superiores en el árbol pueden entonces construir sus propios intervalos, que agregan recursivamente los intervalos contenidos en sus propios nodos internos hijos. Finalmente, la raíz de un árbol B+ representa todo el rango de valores en el árbol, donde cada nodo interno representa un subintervalo.

Para que se conserve esta información de intervalo recursivo, los nodos internos deben contener adicionalmente${\displaystyle m-1}$copias de las claves${\displaystyle l_{i}}$para${\displaystyle i\in [1,m-1]}$representa el elemento más pequeño dentro del intervalo cubierto por el hijo con índice i (que puede ser un nodo interno o una hoja). Donde m representa el número real de hijos para un nodo interno dado.

Estamos buscando un valor k en el árbol B+. Esto significa que, comenzando desde la raíz, estamos buscando la hoja que pueda contener el valor k . En cada nodo, determinamos qué nodo interno debemos seguir. Un nodo interno del árbol B+ tiene como máximo${\displaystyle m\leq b}$ hijos, donde cada uno de ellos representa un subintervalo diferente. Seleccionamos el hijo correspondiente mediante una búsqueda lineal de las m entradas, luego, cuando finalmente llegamos a una hoja, hacemos una búsqueda lineal de sus n elementos para la clave deseada. Debido a que solo recorremos una rama de todos los hijos en cada peldaño del árbol, logramos${\displaystyle O(\log N)}$tiempo de ejecución, donde N es el número total de claves almacenadas en las hojas del árbol B+. ^{[ 4 ]}

función search( k , root ) es let leaf = leaf_search(k, root) for leaf_key in leaf.keys(): if k = leaf_key: return true return false

La función leaf_search( k , node ) es si node es una hoja: devuelve node. let p = node.children() let l = node.left_sided_intervals() assert${\displaystyle |p|=|l|+1}$sea ​​m = p.len() para i desde 1 hasta m - 1: si${\displaystyle k\leq l[i]}$: devolver leaf_search(k, p[i]) devolver leaf_search(k, p[m])

Tenga en cuenta que este pseudocódigo utiliza indexación de matrices basada en 1.

• Realiza una búsqueda para determinar en qué nodo debe ir el nuevo registro.
• Si el nodo no está lleno (como máximo)${\displaystyle b-1}$entradas después de la inserción), agregue el registro.
• De lo contrario, antes de insertar el nuevo registro
  • Divide el nodo.
    • El nodo original tiene${\displaystyle \lceil (K+1)/2\rceil}$elementos
    • nuevo nodo tiene${\displaystyle \lfloor (K+1)/2\rfloor }$elementos
  • Copiar${\displaystyle \lceil (K+1)/2\rceil}$-la clave al padre, e insertar el nuevo nodo en el padre.
  • Repita el proceso hasta encontrar un padre que no necesite dividirse.
  • Inserta el nuevo registro en el nuevo nodo.
• Si la raíz se divide, trátela como si tuviera un padre vacío y divídala como se describe anteriormente.

Los árboles B+ crecen en la raíz y no en las hojas. ^{[ 1 ]}

A partir de un conjunto de registros de datos, queremos crear un índice de árbol B+ en un campo clave. Un enfoque consiste en insertar cada registro en un árbol vacío. Sin embargo, esto resulta bastante costoso, ya que cada entrada requiere comenzar desde la raíz y descender hasta la página hoja correspondiente. Una alternativa eficiente es utilizar la carga masiva.

• El primer paso consiste en ordenar las entradas de datos según una clave de búsqueda en orden ascendente.
• Asignamos una página vacía para que sirva como raíz e insertamos en ella un puntero a la primera página de entradas.
• Cuando la raíz está llena, la dividimos y creamos una nueva página raíz.
• Continúe insertando entradas en la página de índice más a la derecha, justo encima del nivel de hoja, hasta que todas las entradas estén indexadas.

Nota:

• Cuando se llena la página de índice situada más a la derecha del nivel de hoja, esta se divide;
• Esta acción puede, a su vez, provocar una división de la página de índice más a la derecha, acercándola un paso más a la raíz;
• Las divisiones solo ocurren en el camino más a la derecha desde la raíz hasta el nivel de la hoja. ^{[ 9 ]}

El objetivo del algoritmo de eliminación es suprimir el nodo de entrada deseado de la estructura de árbol. Llamamos recursivamente al algoritmo de eliminación en el nodo correspondiente hasta que no se encuentre ningún nodo. En cada llamada a la función, recorremos la estructura utilizando el índice para navegar hasta encontrar el nodo, lo eliminamos y luego volvemos a la raíz.

En la entrada L que deseamos eliminar:

• Si L está al menos medio lleno, listo.
• Si L tiene solo d-1 entradas, intente redistribuir, tomando prestado de un nodo hermano (nodo adyacente con el mismo padre que L).
  Tras la redistribución de dos nodos hermanos, el nodo padre debe actualizarse para reflejar este cambio. La clave de índice que apunta al segundo hermano debe tomar el valor más pequeño de ese nodo para convertirse en la clave de índice.
• Si la redistribución falla, se fusionan L y su nodo hermano. Tras la fusión, el nodo padre se actualiza eliminando la clave de índice que apunta a la entrada eliminada. En otras palabras, si se produjo la fusión, se debe eliminar la entrada (que apunta a L o a su nodo hermano) del nodo padre de L.

Nota: la fusión podría propagarse a la raíz, lo que significa una altura decreciente. ^{[ 10 ]}

Los sistemas de archivos ReiserFS , NSS , XFS , JFS , ReFS y BFS utilizan este tipo de árbol para la indexación de metadatos; BFS también utiliza árboles B+ para almacenar directorios. NTFS utiliza árboles B+ para la indexación de directorios y metadatos relacionados con la seguridad. EXT4 utiliza árboles de extensión (una estructura de datos de árbol B+ modificada) para la indexación de extensiones de archivos. ^{[ 12 ]} APFS utiliza árboles B+ para almacenar asignaciones de identificadores de objetos del sistema de archivos a sus ubicaciones en el disco, y para almacenar registros del sistema de archivos (incluidos directorios), aunque los nodos hoja de estos árboles carecen de punteros hermanos. ^{[ 13 ]}

Los sistemas de gestión de bases de datos relacionales como IBM Db2 , ^{[ 11 ]} Informix , ^{[ 11 ]} Microsoft SQL Server , ^{[ 11 ]} Oracle 8 , ^{[ 11 ]} Sybase ASE , ^{[ 11 ]} y SQLite ^{[ 14 ]} admiten este tipo de árbol para los índices de las tablas, aunque cada uno de estos sistemas implementa la estructura básica del árbol B+ con variaciones y extensiones. Muchos sistemas de gestión de bases de datos NoSQL como CouchDB ^{[ 15 ] [ a ]} y Tokyo Cabinet ^{[ 16 ]} también admiten este tipo de árbol para el acceso y almacenamiento de datos.

Encontrar objetos en una base de datos de alta dimensión que sean comparables a un objeto de consulta específico es uno de los procedimientos más utilizados, aunque costoso, en este tipo de sistemas. En tales situaciones, encontrar el vecino más cercano mediante un árbol B+ resulta productivo. ^{[ 17 ]}