B+ TREE: Buscar, insertar y eliminar OperaSupuestos de Alcance

¿Qué es un árbol B+?

A Árbol B+ Se utiliza principalmente para implementar la indexación dinámica en múltiples niveles. En comparación con un árbol B, el árbol B+ almacena los punteros de datos únicamente en los nodos hoja, lo que hace que el proceso de búsqueda sea más preciso y rápido.

Reglas para el árbol B+

Aquí están las reglas esenciales para un árbol B+.

• Las hojas se utilizan para almacenar registros de datos.
• Los registros se almacenan en los nodos internos del árbol.
• Si el valor de una clave de destino es menor que el del nodo interno, se sigue el puntero que se encuentra justo a su izquierda.
• Si el valor de una clave de destino es mayor o igual que el del nodo interno, entonces se sigue el puntero que se encuentra justo a su derecha.
• La raíz tiene un mínimo de dos hijos.

¿Por qué utilizar el árbol B+?

Estas son las razones para utilizar un árbol B+:

• Las claves se utilizan principalmente para facilitar la búsqueda, dirigiendo al usuario a la hoja correcta.
• Un árbol B+ utiliza un "factor de relleno" para gestionar el aumento y la disminución en un árbol.
• En los árboles B+, se pueden colocar fácilmente numerosas claves en la página de 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 de todos los elementos requiere solo una pasada lineal porque todos los nodos hoja de un árbol B+ están conectados entre sí.

Árbol B+ versus árbol B

Estas son las principales diferencias entre un árbol B+ y un árbol B.

Buscar Operadisrupción

En un árbol B+, la búsqueda es uno de los procedimientos más fáciles de ejecutar y proporciona resultados rápidos y precisos.

Se aplica el siguiente algoritmo de búsqueda:

• Para encontrar el registro requerido, debe ejecutar el búsqueda binaria en los registros disponibles en el Árbol.
• En caso de una coincidencia exacta con la clave de búsqueda, se devuelve al usuario el registro correspondiente.
• En caso de que la clave exacta no se encuentre en la búsqueda 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.

Buscar OperaAlgoritmo de ción

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
       The accurate result is returned and displayed to the user
   Else, if the node being searched is the current and the exact key is not found by the algorithm
       Display the statement "Recordset cannot be found."

Salida: El conjunto de registros coincidentes con la clave exacta se muestra al usuario; de lo contrario, se le muestra un intento fallido.

recuadro Operadisrupción

El siguiente algoritmo es aplicable para la operación de inserción:

• El 50 por ciento de los elementos de los nodos se trasladan a una nueva hoja para su almacenamiento.
• El nodo padre de la nueva hoja está vinculado con precisión mediante el valor mínimo de la clave 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 clave central se asocia con el nodo de nivel superior de esa hoja.
• Hasta que no se encuentre el nodo de nivel superior, continúe repitiendo el proceso explicado en los pasos anteriores.

recuadro OperaAlgoritmo de ción

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. 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 tree.
   b. 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 ejemplo del árbol B+ anterior se explica en los pasos siguientes:

• En primer lugar, tenemos 3 nodos, y los tres primeros elementos, que son 1, 4 y 6, se añaden en las ubicaciones apropiadas de los nodos.
• El siguiente valor en la serie de datos es 12, que debe formar parte del árbol.
• Para lograr esto, divide el nodo y agrega 6 como elemento puntero.
• Ahora, se crea una jerarquía derecha de un árbol y los valores de datos restantes se ajustan en consecuencia mediante keeping Tenga en cuenta las reglas aplicables de valores iguales o mayores que los nodos clave-valor de la derecha.

Eliminar Operadisrupció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 se aplica al eliminar un elemento del árbol B+:

• En primer lugar, debemos localizar una entrada hoja en el árbol que contenga la clave y el puntero, y luego eliminar la entrada hoja del árbol si cumple las condiciones exactas para la eliminación del registro.
• En caso de que el nodo hoja cumpla con el requisito de estar medio lleno, la operación se completa; de lo contrario, el nodo hoja tiene entradas mínimas y no se puede eliminar.
• Los demás nodos vinculados a la derecha y a la izquierda pueden eliminar cualquier entrada y luego moverla a la hoja. Si no se cumplen estos criterios, deben combinar el nodo hoja con su nodo vinculado en la jerarquía del árbol.
• Al fusionarse un nodo hoja con sus vecinos a la derecha o a la izquierda, se eliminan las entradas de valores en el nodo hoja o en el vecino vinculado que apuntan al nodo de nivel superior.

El ejemplo anterior ilustra el procedimiento para eliminar un elemento de un árbol B+ de un orden específico.

• En primer lugar, en el árbol se identifican las ubicaciones exactas del elemento que se va a eliminar.
• En este caso, el elemento que se va a eliminar solo se puede identificar con precisión a nivel de hoja y no en su posición de í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 localizar las instancias de 31 en el Índice y la Hoja.
• Podemos observar que el nodo 31 está disponible tanto en el nodo índice como en el nodo hoja. Por lo tanto, lo eliminamos de ambas instancias.
• Pero tenemos que rellenar el índice que apunta al 42. Ahora buscaremos al hijo derecho menor que 25, tomaremos el valor mínimo y lo colocaremos como índice. Así, como el 42 es el único valor presente, se convertirá en el índice.

Eliminar OperaAlgoritmo de ción

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  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 node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

Salida: Se elimina la clave “K” y se toman prestadas claves de los nodos hermanos para ajustar los valores en n y sus nodos padres si es necesario.

Preguntas Frecuentes