¿Qué es un árbol B +?
Un árbol B + se utiliza principalmente para implementar la indexación dinámica en múltiples niveles. En comparación con el árbol B, el árbol B + almacena los punteros de datos solo en los nodos hoja del árbol, lo que hace que la búsqueda sea más precisa y rápida.
En este tutorial de B + Tree, aprenderá:
- ¿Qué es un árbol B +?
- Reglas para B + Tree
- Por qué utilizar B + Tree
- Árbol B + vs.Árbol B
- Operación de búsqueda
- Insertar operación
- Eliminar operación
Reglas para B + Tree
Estas son las reglas esenciales para B + Tree.
- Las hojas se utilizan para almacenar registros de datos.
- Se almacena en los nodos internos del Árbol.
- Si el valor de una clave de destino es menor que el nodo interno, se sigue el punto justo a su lado izquierdo.
- Si el valor de una clave de destino es mayor o igual que el nodo interno, se sigue el punto justo a su lado derecho.
- La raíz tiene un mínimo de dos hijos.
Por qué utilizar B + Tree
Aquí están las razones para usar B + Tree:
- Las claves se utilizan principalmente para ayudar en la búsqueda dirigiéndose a la hoja adecuada.
- B + Tree utiliza un "factor de relleno" para gestionar el aumento y la disminución de un árbol.
- En los árboles B +, numerosas claves se pueden colocar fácilmente en la página de la memoria porque no tienen los datos asociados con los nodos interiores. Por lo tanto, accederá rápidamente a los datos del árbol que se encuentran en el nodo hoja.
- Un escaneo completo completo de todos los elementos es un árbol que necesita solo una pasada lineal porque todos los nodos de hojas de un árbol B + están vinculados entre sí.
Árbol B + vs.Árbol B
Aquí están las principales diferencias entre B + Tree vs.B Tree
| B + Árbol | Árbol B |
| Las claves de búsqueda se pueden repetir. | Las claves de búsqueda no pueden ser redundantes. |
| Los datos solo se guardan en los nodos hoja. | Tanto los nodos hoja como los nodos internos pueden almacenar datos |
| Los datos almacenados en el nodo hoja hacen que la búsqueda sea más precisa y rápida. | La búsqueda es lenta debido a los datos almacenados en Leaf y en los nodos internos. |
| La eliminación no es difícil ya que un elemento solo se elimina de un nodo hoja. | La eliminación de elementos es un proceso complicado y que requiere mucho tiempo. |
| Los nodos hoja enlazados hacen que la búsqueda sea eficiente y rápida. | No puede vincular nodos hoja. |
Operación de búsqueda
En B + Tree, una búsqueda es uno de los procedimientos más fáciles de ejecutar y obtener resultados rápidos y precisos.
Se aplica el siguiente algoritmo de búsqueda:
- Para encontrar el registro requerido, debe ejecutar la búsqueda binaria en los registros disponibles en el árbol.
- En caso de una coincidencia exacta con la clave de búsqueda, el registro correspondiente se devuelve al usuario.
- En caso de que la búsqueda no encuentre la clave exacta en el nodo principal, actual o hoja, se muestra al usuario un "mensaje no encontrado".
- El proceso de búsqueda se puede volver a ejecutar para obtener resultados mejores y más precisos.
Algoritmo de operación de búsqueda
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Salida :
El registro coincidente establecido con la clave exacta se muestra al usuario; de lo contrario, se muestra al usuario un intento fallido.
Insertar operación
El siguiente algoritmo es aplicable para la operación de inserción:
- El 50 por ciento de los elementos en los nodos se mueven a una nueva hoja para su almacenamiento.
- El padre de la nueva hoja está vinculado con precisión con el valor de clave mínimo y una nueva ubicación en el árbol.
- Divida el nodo principal en más ubicaciones en caso de que se utilice por completo.
- Ahora, para obtener mejores resultados, la tecla central está asociada con el nodo de nivel superior de esa hoja.
- Hasta que no se encuentre el nodo de nivel superior, siga iterando el proceso explicado en los pasos anteriores.
Insertar algoritmo de operación
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
Salida :
El algoritmo determinará el elemento y lo insertará con éxito en el nodo hoja requerido.
El ejemplo de muestra del árbol B + anterior se explica en los pasos siguientes:
- En primer lugar, tenemos 3 nodos y los primeros 3 elementos, que son 1, 4 y 6, se agregan en las ubicaciones adecuadas de los nodos.
- El siguiente valor de la serie de datos es 12 que debe formar parte del árbol.
- Para lograr esto, divida el nodo, agregue 6 como elemento puntero.
- Ahora, se crea una jerarquía a la derecha de un árbol y los valores de datos restantes se ajustan en consecuencia teniendo en cuenta las reglas aplicables de valores iguales o superiores a los nodos clave-valor de la derecha.
Eliminar operación
La complejidad del procedimiento de eliminación en el árbol B + supera la de la funcionalidad de inserción y búsqueda.
El siguiente algoritmo es aplicable al eliminar un elemento del árbol B +:
- En primer lugar, necesitamos ubicar una entrada de hoja en el árbol que contiene la tecla y el puntero. , elimine la entrada de la hoja del árbol si la hoja cumple las condiciones exactas de eliminación de registros.
- En caso de que el nodo hoja solo cumpla con el factor satisfactorio de estar medio lleno, entonces la operación se completa; de lo contrario, el nodo Hoja tiene entradas mínimas y no se puede eliminar.
- Los otros nodos vinculados a la derecha e izquierda pueden desocupar cualquier entrada y luego moverlas a la Hoja. Si no se cumplen estos criterios, deben combinar el nodo hoja y su nodo vinculado en la jerarquía del árbol.
- Tras la fusión del nodo hoja con sus vecinos a la derecha o izquierda, se eliminan las entradas de valores en el nodo hoja o vecino vinculado que apunta al nodo de nivel superior.
El ejemplo anterior ilustra el procedimiento para eliminar un elemento del árbol B + de un orden específico.
- En primer lugar, las ubicaciones exactas del elemento que se eliminará se identifican en el árbol.
- Aquí, el elemento que se eliminará solo se puede identificar con precisión a nivel de hoja y no en la ubicación del índice. Por lo tanto, el elemento se puede eliminar sin afectar las reglas de eliminación, que es el valor de la clave mínima.
- En el ejemplo anterior, tenemos que eliminar 31 del árbol.
- Necesitamos ubicar las instancias de 31 en Index y Leaf.
- Podemos ver que 31 está disponible tanto en el nivel de nodo de índice como de hoja. Por lo tanto, lo eliminamos de ambas instancias.
- Pero tenemos que llenar el índice que apunta a 42. Ahora miraremos al niño correcto menor de 25 años, tomaremos el valor mínimo y lo colocaremos como índice. Entonces, siendo 42 el único valor presente, se convertirá en el índice.
Eliminar algoritmo de operación
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Salida :
La clave "K" se elimina y las claves se toman prestadas de los hermanos para ajustar los valores en ny sus nodos principales si es necesario.
Resumen:
- B + Tree es una estructura de datos autoequilibrada para ejecutar procedimientos de búsqueda, inserción y eliminación precisos y rápidos en los datos.
- Podemos recuperar fácilmente datos completos o parciales porque pasar por la estructura del árbol vinculado lo hace eficiente.
- La estructura del árbol B + crece y se reduce con un aumento / disminución en el número de registros almacenados.
- El almacenamiento de datos en los nodos hoja y la posterior ramificación de los nodos internos evidentemente acorta la altura del árbol, lo que reduce las operaciones de entrada y salida del disco, consumiendo en última instancia mucho menos espacio en los dispositivos de almacenamiento.