B TREE en estructura de datos: buscar, insertar, eliminar Operaejemplo de ción

Reglas para el árbol B

Aquí hay reglas importantes para crear B_Tree.

• Todas las hojas se crearán al mismo nivel.
• El árbol B 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 del disco en el que se encuentran 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 = 4
  max keys: 4 – 1 = 3
  

• Cada nodo, excepto raíz, debe contener claves mínimas de

  [m/2]-1

  Por ejemplo:

  m = 4
  min 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 pedido, 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í hay 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, el número de nodos secundarios) según 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 a la hora 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 datos de gran tamaño, buscar un registro en el disco requiere leer el disco entero; 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 los registros en función de los bloques en los que residen. Esto reduce drásticamente el tiempo y el consumo de memoria.
• Como tenemos una gran cantidad de datos, podemos crear tablas de índice de varios niveles.
• Se puede diseñar un índice multinivel utilizando el árbol B para mantener los datos ordenados de forma autoequilibrada.

Buscar Operadesarrollo

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 con "k".
• Comience 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 la k encontrada, simplemente devuelva el nodo.
• Si k no se encuentra en el nodo, descienda hasta el niño con una clave mayor.
• Si k no se encuentra en el árbol, devolvemos NULL.

recuadro Operadesarrollo

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

Se aplica el siguiente algoritmo:

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

TIP	Lo siguiente no es cierto acerca del 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 apropiada 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 un número mínimo de claves, que es 1? En este caso sí, lo es. Comprueba la siguiente regla.
• Después de la inserción, ¿el nodo tiene más del 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 clave del medio se convertirá en el nodo raíz de los dos nodos restantes.
• En caso de que el número de claves sea par, el nodo medio se seleccionará mediante polarización izquierda o derecha.

En el ejemplo anterior:

• El nodo tiene menos de claves máximas.
• Se inserta 1 junto a 3, pero se viola la regla del orden ascendente
• Para solucionar este problema, las claves están ordenadas.

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

En el ejemplo anterior:

• El nodo tiene claves iguales a las claves máximas.
• La clave se inserta en el nodo de destino, pero viola la regla de claves máximas.
• El nodo de destino se divide y la clave del medio con polarización izquierda ahora es el padre de los nuevos nodos secundarios.
• Los nuevos nodos están dispuestos en orden ascendente.

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

Borrar Operadesarrollo

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

• Target está en el nodo hoja, más que las claves mínimas.
• Eliminar esto no violará la propiedad de B Tree
• Target está en el nodo hoja, tiene mínimos nodos clave
• Eliminar esto violará la propiedad de B Tree
• Target El nodo puede tomar prestada la clave del nodo izquierdo inmediato o del nodo derecho inmediato (hermano)
• El hermano dirá si si tiene más del número mínimo de claves
• 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 objetivo y se eliminará el valor objetivo.
• Target está en el nodo hoja, pero ningún hermano tiene más que un número mínimo de claves
• buscar clave
• Fusionarse con hermanos y el mínimo de nodos principales
• El total de claves ahora será superior al mínimo
• 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 entre predecesor o sucesor en orden
• En caso de que el predecesor esté 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 que 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 menos de claves mínimas, entonces fusione 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 de destino 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 operaciones de eliminación en un árbol B. Este árbol B 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 puede tener cualquier nodo es 5. Mientras que el número mínimo y máximo de claves que puede tener cualquier nodo 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 más claves que las claves mínimas.
• Simplemente elimine la clave

En el ejemplo anterior:

• El nodo de destino tiene claves iguales a las 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 proporcionar su clave al nodo de destino. Por lo tanto, es necesaria 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
• Se selecciona la clave del nodo principal para que los hermanos se encuentren entre los dos nodos fusionados.
• Eliminar la clave de destino del nodo fusionado

Borrar OperaPseudocódigo de ción

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        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 árbol B.

Resumen

• B Tree es una estructura de datos autoequilibrada para una mejor búsqueda, inserción y eliminación de datos del disco.
• El árbol B está regulado por el grado especificado.
• B Las claves y los nodos del árbol están organizados en orden ascendente.
• La operación de búsqueda de B Tree es la más simple, siempre comienza desde la raíz y empieza 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: primero encuentra una posición de inserción adecuada para la clave de destino, la inserta, evalúa la validez del árbol B frente a diferentes casos y luego reestructura los nodos del árbol B en consecuencia.
• La operación de eliminación de B Tree primero busca la clave de destino que se va a eliminar, la elimina y 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.