B ÁRBOL en la estructura de datos: Buscar, insertar, eliminar Ejemplo de operación

¿Qué es un árbol B?

B Tree es una estructura de datos autoequilibrada basada en un conjunto específico de reglas para buscar, insertar y eliminar los datos de una manera más rápida y eficiente en la memoria. Para lograr esto, se siguen las siguientes reglas para crear un Árbol B.

Un B-Tree es un tipo especial de árbol en una estructura de datos. En 1972, este método fue introducido por primera vez por McCreight, y Bayer lo nombró Árbol de búsqueda de m-way con equilibrio de altura. Le ayuda a conservar los datos ordenados y permite varias operaciones como inserción, búsqueda y eliminación en menos tiempo.

En este tutorial de B-Tree, aprenderá:

• ¿Qué es un árbol B?
• Por qué utilizar B-Tree
• Historia del árbol B
• Operación de búsqueda
• Insertar operación
• Eliminar operación

Reglas para B-Tree

Aquí, hay reglas importantes para crear B_Tree

• Todas las hojas se crearán al mismo nivel.
• B-Tree está determinado por un número de grados, que también se denomina "orden" (especificado por un actor externo, como un programador), denominado

  m

  adelante. El valor de

  m

  depende del tamaño del bloque en el disco en el que se ubican principalmente los datos.
• El subárbol izquierdo del nodo tendrá valores menores que el lado derecho del subárbol. Esto significa que los nodos también se ordenan en orden ascendente de izquierda a derecha.
• El número máximo de nodos secundarios que puede contener un nodo raíz y sus nodos secundarios se calcula mediante esta fórmula:

  m - 1

  Por ejemplo:

  m = 4max keys: 4 - 1 = 3

• Cada nodo, excepto el root, debe contener claves mínimas de

  [m/2]-1

  Por ejemplo:

  m = 4min keys: 4/2-1 = 1

• El número máximo de nodos secundarios que puede tener un nodo es igual a su grado, que es

  m

• El mínimo de hijos que puede tener un nodo es la mitad del orden, que es m / 2 (se toma el valor máximo).
• Todas las claves de un nodo se ordenan en orden creciente.

Por qué utilizar B-Tree

Aquí están las razones para usar B-Tree

• Reduce el número de lecturas realizadas en el disco.
• Los árboles B se pueden optimizar fácilmente para ajustar su tamaño (es decir, la cantidad de nodos secundarios) de acuerdo con el tamaño del disco
• Es una técnica especialmente diseñada para manejar una gran cantidad de datos.
• Es un algoritmo útil para bases de datos y sistemas de archivos.
• Una buena opción para optar cuando se trata de leer y escribir grandes bloques de datos.

Historia del árbol B

• Los datos se almacenan en el disco en bloques, estos datos, cuando se llevan a la memoria principal (o RAM) se denominan estructura de datos.
• En el caso de grandes cantidades de datos, la búsqueda de un registro en el disco requiere leer todo el disco; esto aumenta el tiempo y el consumo de memoria principal debido a la alta frecuencia de acceso al disco y al tamaño de los datos.
• Para superar esto, se crean tablas de índice que guardan la referencia de registro de los registros en función de los bloques en los que residen. Esto reduce drásticamente el tiempo y el consumo de memoria.
• Dado que tenemos una gran cantidad de datos, podemos crear tablas de índices de varios niveles.
• El índice multinivel se puede diseñar utilizando B Tree para mantener los datos ordenados de manera autoequilibrada.

Operación de búsqueda

La operación de búsqueda es la operación más simple en B Tree.

Se aplica el siguiente algoritmo:

• Deje que la clave (el valor) se busque por "k".
• Empiece a buscar desde la raíz y recorra recursivamente hacia abajo.
• Si k es menor que el valor raíz, busque el subárbol izquierdo, si k es mayor que el valor raíz, busque el subárbol derecho.
• Si el nodo tiene el k encontrado, simplemente devuelva el nodo.
• Si la k no se encuentra en el nodo, recorra hasta el niño con una clave mayor.
• Si k no se encuentra en el árbol, devolvemos NULL.

Insertar operación

Dado que B Tree es un árbol de autoequilibrio, no puede forzar la inserción de una llave en cualquier nodo.

Se aplica el siguiente algoritmo:

• Ejecute la operación de búsqueda y encuentre el lugar apropiado de inserción.
• Inserte la nueva clave en la ubicación adecuada, pero si el nodo ya tiene un número máximo de claves:
• El nodo, junto con una clave recién insertada, se dividirá del elemento del medio.
• El elemento del medio se convertirá en el padre de los otros dos nodos hijos.
• Los nodos deben reorganizar las claves en orden ascendente.

SUGERENCIA

Lo siguiente no es cierto sobre el algoritmo de inserción: Dado que el nodo está lleno, se dividirá y luego se insertará un nuevo valor

En el ejemplo anterior:

• Busque la posición adecuada en el nodo para la clave
• Inserte la clave en el nodo de destino y verifique las reglas
• Después de la inserción, ¿el nodo tiene más que igual a un número mínimo de claves, que es 1? En este caso, sí lo hace. Revisa la siguiente regla.
• Después de la inserción, ¿el nodo tiene más de un número máximo de claves, que es 3? En este caso, no, no es así. Esto significa que el árbol B no infringe ninguna regla y la inserción está completa.

En el ejemplo anterior:

• El nodo ha alcanzado el número máximo de claves.
• El nodo se dividirá y la tecla del medio se convertirá en el nodo raíz de los dos nodos restantes.
• En el caso de un número par de claves, el nodo del medio se seleccionará por sesgo hacia la izquierda o hacia la derecha.

En el ejemplo anterior:

• El nodo tiene menos del máximo de claves
• Se inserta 1 junto a 3, pero se infringe la regla de orden ascendente
• Para solucionar este problema, las claves se ordenan

De manera similar, 13 y 2 se pueden insertar fácilmente en el nodo ya que cumplen la regla de claves inferiores al máximo para los nodos.

En el ejemplo anterior:

• El nodo tiene claves iguales a claves máximas.
• La clave se inserta en el nodo de destino, pero viola la regla de claves máximas.
• El nodo de destino está dividido y la tecla central por sesgo a la izquierda es ahora el padre de los nuevos nodos secundarios.
• Los nuevos nodos están dispuestos en orden ascendente.

Del mismo modo, según las reglas y los casos anteriores, el resto de los valores se pueden insertar fácilmente en el árbol B.

Eliminar operación

La operación de eliminación tiene más reglas que las operaciones de inserción y búsqueda.

Se aplica el siguiente algoritmo:

• Ejecute la operación de búsqueda y encuentre la clave de destino en los nodos.
• Se aplican tres condiciones según la ubicación de la clave de destino, como se explica en las siguientes secciones

Si la clave de destino está en el nodo hoja

• El destino está en el nodo hoja, más de claves mínimas.
  • Eliminar esto no violará la propiedad de B Tree
• El objetivo está en el nodo hoja, tiene nodos clave mínimos
  • Eliminar esto violará la propiedad de B Tree
  • El nodo de destino puede tomar prestada la clave del nodo izquierdo inmediato o del nodo derecho inmediato (hermano)
  • El hermano dirá que sí si tiene más del número mínimo de llaves
  • La clave se tomará prestada del nodo principal, el valor máximo se transferirá a un nodo principal, el valor máximo del nodo principal se transferirá al nodo de destino y se eliminará el valor de destino
• El destino está en el nodo hoja, pero ningún hermano tiene más de un número mínimo de claves
  • Buscar clave
  • Fusionar con hermanos y el mínimo de nodos principales
  • El total de claves será ahora más de min
  • La clave de destino se reemplazará con el mínimo de un nodo principal

Si la clave de destino está en un nodo interno

• Elija, predecesor en orden o sucesor en orden
• En caso de que el predecesor en orden, se seleccionará la clave máxima de su subárbol izquierdo
• En caso de sucesor en orden, se seleccionará la clave mínima de su subárbol derecho
• Si el predecesor en orden de la clave de destino tiene más que las claves mínimas, solo entonces puede reemplazar la clave de destino con el máximo del predecesor en orden
• Si el predecesor en orden de la clave de destino no tiene más de claves mínimas, busque la clave mínima del sucesor en orden.
• Si el predecesor y el sucesor en orden de la clave de destino tienen claves inferiores a mín, entonces combine el predecesor y el sucesor.

Si la clave de destino está en un nodo raíz

• Reemplazar con el elemento máximo del subárbol predecesor en orden
• Si, después de la eliminación, el objetivo tiene menos de claves mínimas, entonces el nodo objetivo tomará prestado el valor máximo de su hermano a través del padre del hermano.
• El valor máximo del padre lo tomará un objetivo, pero con los nodos del valor máximo del hermano.

Ahora, entendamos la operación de eliminación con un ejemplo.

El diagrama anterior muestra diferentes casos de operación de eliminación en un B-Tree. Este B-Tree es de orden 5, lo que significa que el número mínimo de nodos secundarios que puede tener cualquier nodo es 3, y el número máximo de nodos secundarios que cualquier nodo puede tener es 5. Mientras que el número mínimo y máximo de claves de cualquier nodo pueden tener son 2 y 4, respectivamente.

En el ejemplo anterior:

• El nodo de destino tiene la clave de destino para eliminar
• El nodo de destino tiene claves más que claves mínimas
• Simplemente elimine la clave

En el ejemplo anterior:

• El nodo de destino tiene claves iguales a claves mínimas, por lo que no puede eliminarlo directamente ya que violará las condiciones

Ahora, el siguiente diagrama explica cómo eliminar esta clave:

• El nodo de destino tomará prestada una clave del hermano inmediato, en este caso, el predecesor en orden (hermano izquierdo) porque no tiene ningún sucesor en orden (hermano derecho)
• El valor máximo del predecesor en orden se transferirá al padre y el padre transferirá el valor máximo al nodo de destino (consulte el diagrama a continuación)

El siguiente ejemplo ilustra cómo eliminar una clave que necesita un valor de su sucesor en orden.

• El nodo de destino tomará prestada una clave del hermano inmediato, en este caso, el sucesor en orden (hermano derecho) porque su predecesor en orden (hermano izquierdo) tiene claves iguales a las claves mínimas.
• El valor mínimo del sucesor en orden se transferirá al padre y el padre transferirá el valor máximo al nodo de destino.

En el siguiente ejemplo, el nodo de destino no tiene ningún hermano que pueda dar su clave al nodo de destino. Por lo tanto, se requiere la fusión.

Consulte el procedimiento para eliminar dicha clave:

• Fusionar el nodo de destino con cualquiera de sus hermanos inmediatos junto con la clave principal
  • La clave del nodo principal se selecciona para que los hermanos entre los dos nodos fusionados
• Eliminar la clave de destino del nodo combinado

Eliminar el pseudo código de la operación

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Salida :

El elemento más grande se elimina del B-Tree.

Resumen:

• B Tree es una estructura de datos autoequilibrada para una mejor búsqueda, inserción y eliminación de datos del disco.
• B El árbol está regulado por el grado especificado
• B Las claves y los nodos del árbol están dispuestos en orden ascendente.
• La operación de búsqueda de B Tree es la más simple, que siempre comienza desde la raíz y comienza a verificar si la clave de destino es mayor o menor que el valor del nodo.
• La operación de inserción del árbol B es bastante detallada, que primero encuentra una posición apropiada de inserción para la clave de destino, la inserta, evalúa la validez del árbol B en diferentes casos y luego reestructura los nodos del árbol B en consecuencia.
• La operación de eliminación de B Tree busca primero la clave de destino que se eliminará, la elimina, evalúa la validez en función de varios casos, como las claves mínima y máxima del nodo de destino, los hermanos y el padre.