Árbol B en Estructura de Datos: Búsqueda, Inserción, Eliminación

¿Qué es un árbol B?

Árbol B Es una estructura de datos autoequilibrada basada en un conjunto específico de reglas para buscar, insertar y eliminar datos de forma más rápida y eficiente en cuanto al uso de memoria. Para lograr esto, se siguen las siguientes reglas para crear un árbol B.

Un árbol B es un tipo especial de árbol en una estructura de datos. Este método fue introducido por primera vez en 1972 por McCreight y Bayer, quienes lo denominaron Árbol de Búsqueda de m vías con equilibrio de altura. Ayuda a mantener los datos ordenados y permite realizar diversas operaciones como inserción, búsqueda y eliminación en menos tiempo.

Reglas para el árbol B

Estas son las reglas importantes para crear un árbol B:

• Todas las hojas se crearán al mismo nivel.
• Un árbol B se determina por un número de grado, 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 claves que puede contener un nodo raíz, así como sus nodos hijos, se calcula mediante esta fórmula: m − 1. Por ejemplo:

  m = 4
  max keys: 4 − 1 = 3

• Cada nodo, excepto la raíz, debe contener un número mínimo de claves. [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?

Estas son las razones para utilizar un árbol B:

• 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 hijos) 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 tener en cuenta 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, al ser cargados en la memoria principal (o RAM), se denominan estructura de datos.
• En el caso de grandes cantidades de datos, la búsqueda de un solo registro en el disco requiere la lectura de 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 solucionar esto, se crean tablas de índices que guardan la referencia de los registros en función de los bloques en los que se encuentran. 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 un árbol B para mantenerping Los datos se ordenaron de forma autoequilibrada.

Buscar Operadisrupción

La operación de búsqueda es la operación más sencilla en un árbol B. Se aplica el siguiente algoritmo:

• Sea “k” la clave (el valor) que se va a buscar.
• Comience a buscar desde la raíz y recorra recursivamente hacia abajo.
• Si k es menor que el valor raíz, busque en el subárbol izquierdo; si k es mayor que el valor raíz, busque en 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 Operadisrupción

Dado que un árbol B 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.

En el ejemplo anterior:

• Busque la clave en la posición adecuada del nodo.
• Inserta la clave en el nodo de destino y comprueba las reglas.
• Tras la inserción, ¿el nodo tiene más o igual al número mínimo de claves, que es 1? En este caso, sí. Consulta la siguiente regla.
• Tras la inserción, ¿el nodo tiene más claves que el número máximo permitido, que es 3? En este caso, no. Esto significa que el árbol B no infringe ninguna regla y la inserción se ha completado.

En el ejemplo anterior:

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

En el ejemplo anterior:

• El nodo tiene menos claves que el máximo.
• El número 1 se inserta junto al 3, pero se incumple la regla del orden ascendente.
• Para solucionar esto, se ordenan las claves.

De manera similar, 13 y 2 se pueden insertar fácilmente en el nodo ya que cumplen la regla de "menor que el número máximo de claves" 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 del número máximo de claves.
• 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.

Eliminar Operadisrupció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:

• Ejecuta la operación de búsqueda y encuentra la clave objetivo en los nodos.
• Se aplican tres condiciones en función de la ubicación de la clave de destino, tal 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 de min claves. Eliminar esto no violará la propiedad del árbol B.
• Target está en el nodo hoja y tiene nodos clave mínimos. Eliminarlo violará la propiedad del árbol B.
• El nodo de destino puede tomar prestada una clave del nodo inmediatamente izquierdo o del nodo inmediatamente derecho (hermano).
• El hermano dirá sí si tiene más del número mínimo de claves.
• La clave se tomará prestada del nodo padre, el valor máximo se transferirá al padre, el valor máximo del nodo padre se transferirá al nodo de destino y el valor de destino se eliminará.
• Target está en el nodo hoja, pero ningún hermano tiene más del número mínimo de claves: buscar la clave, fusionar con los hermanos y el mínimo de los nodos padre, el total de claves ahora será mayor que el mínimo, y la clave objetivo se reemplazará con el mínimo de un nodo padre.

Si la clave de destino está en un nodo interno

• Elija un predecesor en orden o un sucesor en orden.
• En el caso de un predecesor en orden, se seleccionará la clave máxima de su subárbol izquierdo.
• En el caso de un 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 de 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 min claves, 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, tras la eliminación, el destino tiene menos de un mínimo de claves, el nodo de destino tomará prestado el valor máximo de su hermano a través del padre de este.
• El valor máximo del padre será tomado por el 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 la operación 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 hijos que puede tener un nodo es 3, y el número máximo es 5. Por otro lado, el número mínimo y máximo de claves que puede tener un nodo es 2 y 4, respectivamente.

En el ejemplo anterior:

• El nodo de destino tiene la clave de destino que se va a eliminar.
• El nodo de destino tiene más claves que el mínimo requerido.
• Simplemente elimina la clave.

En el ejemplo anterior:

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

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

• El nodo de destino tomará prestada una clave de un 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 (ver 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 de un 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 ejemplo siguiente, el nodo de destino no tiene ningún nodo hermano que pueda proporcionarle su clave. Por lo tanto, es necesario fusionarlo. Consulte el procedimiento para eliminar dicha clave:

• Fusiona el nodo de destino con cualquiera de sus hermanos inmediatos junto con la clave principal.
• Se selecciona la clave del nodo padre que se encuentra entre los dos nodos que se fusionan.
• Elimine la clave de destino del nodo fusionado.

Eliminar Operación Pseudo Code

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.

Preguntas Frecuentes