B+ Tree es una extensión de B Tree que permite operaciones eficientes de inserción, eliminación y búsqueda.
En el árbol B, las claves y los registros se pueden almacenar tanto en los nodos internos como en los de hoja. Mientras que, en el árbol B+, los registros (datos) solo se pueden almacenar en los nodos hoja, mientras que los nodos internos solo pueden almacenar los valores clave.
cadena.contiene java
Los nodos hoja de un árbol B+ están vinculados entre sí en forma de listas vinculadas individualmente para hacer que las consultas de búsqueda sean más eficientes.
B+ Tree se utilizan para almacenar una gran cantidad de datos que no se pueden almacenar en la memoria principal. Debido a que el tamaño de la memoria principal siempre es limitado, los nodos internos (claves para acceder a los registros) del árbol B+ se almacenan en la memoria principal, mientras que los nodos hoja se almacenan en la memoria secundaria.
Los nodos internos del árbol B+ a menudo se denominan nodos índice. En la siguiente figura se muestra un árbol B+ de orden 3.
Ventajas del árbol B+
- Los registros se pueden recuperar en un número igual de accesos al disco.
- La altura del árbol permanece equilibrada y menor en comparación con el árbol B.
- Podemos acceder a los datos almacenados en un árbol B+ tanto de forma secuencial como directa.
- Las claves se utilizan para la indexación.
- Consultas de búsqueda más rápidas ya que los datos se almacenan solo en los nodos hoja.
Árbol B VS Árbol B+
| SN | árbol B | Árbol B+ |
|---|---|---|
| 1 | Las claves de búsqueda no se pueden almacenar repetidamente. | Pueden estar presentes claves de búsqueda redundantes. |
| 2 | Los datos se pueden almacenar tanto en nodos hoja como en nodos internos. | Los datos sólo se pueden almacenar en los nodos hoja. |
| 3 | La búsqueda de algunos datos es un proceso más lento ya que los datos se pueden encontrar tanto en los nodos internos como en los nodos hoja. | La búsqueda es comparativamente más rápida ya que los datos sólo se pueden encontrar en los nodos hoja. |
| 4 | La eliminación de nodos internos es muy complicada y requiere mucho tiempo. | La eliminación nunca será un proceso complejo ya que el elemento siempre se eliminará de los nodos hoja. |
| 5 | Los nodos hoja no se pueden vincular entre sí. | Los nodos hoja están vinculados entre sí para hacer que las operaciones de búsqueda sean más eficientes. |
Inserción en árbol B+
Paso 1: Inserte el nuevo nodo como un nodo hoja
Paso 2: Si la hoja no tiene el espacio requerido, divida el nodo y copie el nodo del medio en el siguiente nodo de índice.
Paso 3: Si el nodo de índice no tiene el espacio requerido, divida el nodo y copie el elemento del medio en la siguiente página de índice.
Ejemplo :
Inserte el valor 195 en el árbol B+ de orden 5 que se muestra en la siguiente figura.
195 se insertará en el subárbol derecho de 120 después de 190. Insértelo en la posición deseada.
El nodo contiene más elementos que el máximo, es decir, 4; por lo tanto, divídalo y coloque el nodo mediano hasta el padre.
base de datos
Ahora, el nodo índice contiene 6 hijos y 5 claves, lo que viola las propiedades del árbol B+, por lo tanto, debemos dividirlo, como se muestra a continuación.
Eliminación en el árbol B+
Paso 1: Elimina la clave y los datos de las hojas.
Paso 2: Si el nodo hoja contiene menos del número mínimo de elementos, fusione el nodo con su hermano y elimine la clave entre ellos.
Paso 3: Si el nodo índice contiene menos del número mínimo de elementos, combine el nodo con el hermano y baje la tecla entre ellos.
Ejemplo
Elimine la clave 200 del árbol B+ que se muestra en la siguiente figura.
200 está presente en el subárbol derecho de 190, después de 195. elimínelo.
Fusione los dos nodos utilizando 195, 190, 154 y 129.
Ahora, el elemento 120 es el único elemento presente en el nodo que viola las propiedades del árbol B+. Por lo tanto, necesitamos fusionarlo usando 60, 78, 108 y 120.
Ahora, la altura del árbol B+ se reducirá en 1.
