En el siguiente tutorial, aprenderemos sobre la estructura de datos del árbol B y consideraremos visualizarla.
Entonces empecemos.
¿Qué es un árbol B?
El árbol B es un tipo especial de árbol de búsqueda multidireccional , comúnmente conocido como el vía M árbol, que se equilibra. Debido a su estructura equilibrada, estos árboles se utilizan comúnmente para operar y administrar inmensas bases de datos y simplificar las búsquedas. En un árbol B, cada nodo puede tener como máximo n nodos secundarios. B Tree es un ejemplo de indexación multinivel en un sistema de gestión de bases de datos (DBMS). Los nodos hoja e interno tendrán referencias de registros. El árbol B se conoce como árbol almacenado equilibrado porque todos los nodos de las hojas están al mismo nivel.
El siguiente diagrama es un ejemplo de un árbol B:
solo mella
Figura 1. A B Árbol con orden 3
Comprender las reglas del árbol B
Las siguientes son las propiedades importantes de un árbol B:
- Todos los nodos de las hojas están al mismo nivel.
- La estructura de datos del árbol B se define mediante el término grado mínimo 'd'. El valor de 'd' depende del tamaño del bloque de disco.
- Cada nodo, excluyendo la raíz, debe constar de al menos d-1 claves. El nodo raíz puede constar de un mínimo de 1 clave.
- Todos los nodos (incluido el nodo raíz) pueden consistir como máximo en (2d-1) llaves.
- El número de hijos de un nodo es igual al suma del número de claves presentes en él y .
- Todas las claves de un nodo se ordenan en orden ascendente. El hijo entre dos claves, k1 y k2, consta de todas las claves que se encuentran entre k1 y k2, respectivamente.
- A diferencia del árbol de búsqueda binaria, la estructura de datos del árbol B crece y se reduce desde la raíz. Mientras que el árbol de búsqueda binaria crece y se contrae hacia abajo.
- Al igual que otros árboles de búsqueda binaria autoequilibrados, la complejidad temporal de la estructura de datos del árbol B para operaciones como búsqueda, inserción y eliminación es O(iniciar sesión?n) .
- La inserción de un nodo en el árbol B ocurre sólo en el nodo hoja.
Consideremos el siguiente ejemplo de un árbol B de orden mínimo 5.
Figura 2. A B Árbol de orden 5
Nota: El valor del pedido mínimo es mucho más que 5 en una práctica Árboles B.
En el diagrama anterior, podemos observar que todos los nodos hoja están en el mismo nivel y todos los nodos que no son hoja no tienen un subárbol vacío y constan de claves una menos que el número de sus hijos.
La formulación establecida de las reglas del Árbol B:
Cada árbol B depende de un número entero positivo constante conocido como MÍNIMO , que se utiliza para determinar la cantidad de elementos de datos que se pueden contener en un solo nodo.
Regla 1: La raíz puede tener tan solo un elemento de datos (o incluso ningún elemento de datos si tampoco tiene elementos secundarios); cada otro nodo tiene al menos MÍNIMO elementos de datos.
Regla 2: El número máximo de elementos de datos almacenados en un nodo es el doble del valor de MÍNIMO .
Regla 3: Los elementos de datos de cada nodo del árbol B se almacenan en una matriz parcialmente llena, ordenada desde el elemento de datos más pequeño (en el índice 0 ) al elemento de datos más grande (en la posición final utilizada de la matriz).
Regla 4: El número total de subárboles debajo de un nodo no hoja es siempre uno más que el número de elementos de datos en ese nodo.
- subárbol 0,subárbol 1,...
Regla 5: Con respecto a cualquier nodo que no sea hoja:
- Un elemento de datos en el índice es mayor que todos los elementos de datos en el número del subárbol i del nodo, y
- Un elemento de datos en el índice es menor que todos los elementos de datos en el número del subárbol yo+1 del nodo.
Regla 6: Cada hoja de un árbol B tiene la misma profundidad. Por lo tanto, garantiza que un árbol B prevenga el problema de un árbol desequilibrado.
Operaciones en una estructura de datos de árbol B
Para garantizar que ninguna de las propiedades de la estructura de datos del Árbol B sea violada durante las operaciones, el Árbol B puede dividirse o unirse. Las siguientes son algunas operaciones que podemos realizar en un árbol B:
- Buscando un elemento de datos en el árbol B
- Inserción de un elemento de datos en el árbol B.
- Eliminación de un elemento de datos en el árbol B
Operación de búsqueda en un árbol B
La búsqueda de un elemento en un árbol B es similar a la de un árbol de búsqueda binaria. Pero en lugar de tomar una decisión bidireccional (izquierda o derecha) como un árbol de búsqueda binaria, un árbol B toma una decisión m en cada nodo, donde m es el número de hijos del nodo.
Pasos para buscar un elemento de datos en un árbol B:
Paso 1: La búsqueda comienza desde el nodo raíz. Compare el elemento de búsqueda, k, con la raíz.
Paso 1.1: Si el nodo raíz consta del elemento k, la búsqueda estará completa.
Paso 1.2: Si el elemento k es menor que el primer valor en la raíz, nos moveremos al hijo más a la izquierda y buscaremos en el hijo de forma recursiva.
Paso 1.3.1: Si la raíz tiene solo dos hijos, nos moveremos al hijo más a la derecha y buscaremos recursivamente los nodos secundarios.
Paso 1.3.2: Si la raíz tiene más de dos claves, buscaremos el resto.
Paso 2: Si el elemento k no se encuentra después de recorrer todo el árbol, entonces el elemento de búsqueda no está presente en el árbol B.
Visualicemos los pasos anteriores con la ayuda de un ejemplo. Supongamos que queremos buscar una clave k=34 en el siguiente árbol B:
Figura 3.1. Un árbol B dado
- En primer lugar, comprobaremos si la clave k = 34 está en el nodo raíz. Como la clave no está en la raíz, pasaremos a sus nodos secundarios. También podemos observar que el nodo raíz tiene dos hijos; por lo tanto, compararemos el valor requerido entre las dos claves.
Figura 3.2. La clave k no está presente en la raíz. - Ahora que podemos notar que la clave k es mayor que el nodo raíz, es decir, 30, procederemos con el hijo derecho de la raíz.
Figura 3.3. La clave k > 30, pasar al niño derecho - Ahora compararemos la clave k con los valores presentes en el nodo, es decir, 40 y 50, respectivamente. Dado que la clave k es menor que la clave izquierda, es decir, 40, nos moveremos al hijo izquierdo del nodo.
Figura 3.4. la clave k<40, move to left child< li> - Dado que el valor en el hijo izquierdo de 40 es 34, que es el valor requerido, podemos concluir que se encuentra la clave y se completa la operación de búsqueda.
Figura 3.4. La clave k = 34, el hijo izquierdo de 40
Comparamos la clave con cuatro valores diferentes en el ejemplo anterior hasta que la encontramos. Por lo tanto, la complejidad temporal requerida para la operación de búsqueda en un árbol B es O(iniciar sesión?n) .
q4 meses
Operación de inserción en un árbol B
Al insertar un elemento de datos en un árbol B, primero debemos verificar si ese elemento ya está presente en el árbol o no. Si el elemento de datos se encuentra dentro del árbol B, entonces la operación de inserción no se produce. Sin embargo, si ese no es el caso, continuaremos con la inserción. Hay dos escenarios que se deben tener en cuenta al insertar un elemento en el nodo hoja:
Pasos para insertar un elemento de datos en un árbol B:
Paso 1: Comenzaremos calculando el número máximo de claves en el nodo según el orden del árbol B.
Paso 2: Si el árbol está vacío, se asigna un nodo raíz e insertaremos la clave que actúa como nodo raíz.
Paso 3: Ahora buscaremos el nodo correspondiente para su inserción.
Etapa 4: Si el nodo está lleno:
Paso 4.1: Insertaremos los elementos de datos en orden ascendente.
Paso 4.2: Si los elementos de datos son mayores que el número máximo de claves, dividiremos el nodo completo en la mediana.
Paso 4.3: Empujaremos la tecla mediana hacia arriba y dividiremos las teclas izquierda y derecha como hijos izquierdo y derecho.
Paso 5: Si el nodo no está lleno, lo insertaremos en orden ascendente.
Visualicemos los pasos anteriores con la ayuda de un ejemplo. Supongamos que debemos crear un árbol B de orden 4. Los elementos de datos necesarios para insertarse en el árbol B son 5,3,21,11,1,16,8,13,4 y 9 .
- Dado que m es igual a 3, el número máximo de claves para un nodo = m-1 = 3-1 = 2 .
- Empezaremos insertando 5 en el árbol vacío.
Figura 4.1. Insertando 5 - Ahora insertaremos 3 en el árbol. Como 3 es menor que 5, insertaremos 3 a la izquierda de 5 en el mismo nodo.
Figura 4.2. Insertando 3 - Ahora insertaremos 21 en el árbol y, como 21 es mayor que 5, se insertará a la derecha de 5 en el mismo nodo. Sin embargo, como sabemos que el número máximo de claves en el nodo es 2, una de estas claves se moverá a un nodo superior para poder dividirla. Por lo tanto, 5, el elemento de datos del medio, se moverá hacia arriba, y 3 y 21 se convertirán en sus nodos izquierdo y derecho, respectivamente.
Figura 4.3. Insertando 21 - Ahora es el momento de insertar el siguiente elemento de datos, es decir, 11, que es mayor que 5 pero menor que 21. Por lo tanto, 11 se insertará como clave a la izquierda del nodo que consta de 21 como clave.
Figura 4.4. Insertando 11 - De manera similar, insertaremos el siguiente elemento de datos 1 en el árbol y, como podemos observar, 1 es menor que 3; por lo tanto, se insertará como clave a la izquierda del nodo que consta de 3 como clave.
Figura 4.5. Insertando 1 - Ahora, insertaremos el elemento de datos 16 en el árbol, que es mayor que 11 pero menor que 21. Sin embargo, la cantidad de claves en ese nodo excede la cantidad máxima de claves. Por lo tanto, el nodo se dividirá, moviendo la tecla del medio a la raíz. Por lo tanto, 16 se insertará a la derecha del 5, dividiendo 11 y 21 en dos nodos separados.
Figura 4.6. Insertando 16 - El elemento de datos 8 se insertará como clave a la izquierda de 11.
Figura 4.7. Insertando 8 - Insertaremos 13 en el árbol, que es menor que 16 y mayor que 11. Por lo tanto, el elemento de datos 13 debe insertarse a la derecha del nodo que consta de 8 y 11. Sin embargo, dado que el número máximo de claves en el árbol puede solo sea 2, se producirá una división, moviendo el elemento de datos del medio 11 al nodo anterior y 8 y 13 a dos nodos separados. Ahora, el nodo anterior constará de 5, 11 y 16, lo que nuevamente excede el recuento máximo de claves. Por lo tanto, habrá otra división, haciendo que el elemento de datos 11 sea el nodo raíz con 5 y 16 como sus hijos.
Figura 4.8. Insertando 13 - Dado que el elemento de datos 4 es menor que 5 pero mayor que 3, se insertará a la derecha del nodo que consta de 1 y 3, lo que excederá nuevamente el recuento máximo de claves en un nodo. Por lo tanto, volverá a ocurrir un derrame, moviendo el 3 al nodo superior al lado del 5.
Figura 4.9. Insertando 4 - Por último, el elemento de datos 9, que es mayor que 8 pero menor que 11, se insertará a la derecha del nodo que consta de 8 como clave.
Figura 4.10. Insertando 9
En el ejemplo anterior, hemos realizado diferentes comparaciones. El primer valor se insertó directamente en el árbol; después de eso, cada valor debía compararse con los nodos disponibles en ese árbol. La complejidad temporal de la operación de inserción en un árbol B depende del número de nodos y.
Operación de eliminación en un árbol B
La eliminación de un elemento de datos en un árbol B contiene tres eventos principales:
- Buscando el nodo donde existe la clave a eliminar,
- Eliminando la clave, y
- Equilibrar el árbol, si es necesario.
Al eliminar un elemento del árbol, puede ocurrir una condición conocida como Underflow. El desbordamiento insuficiente ocurre cuando un nodo consta de menos del número mínimo de claves; debería aguantar.
Los siguientes son algunos términos que deben comprenderse antes de visualizar la operación de eliminación/eliminación:
Los siguientes son tres casos destacados de la operación de eliminación en un árbol B:
Caso 1: La eliminación/eliminación de la clave se encuentra en el nodo Hoja - Este caso se divide a su vez en dos casos diferentes:
1. La eliminación/eliminación de la clave no viola la propiedad del número mínimo de claves que debe contener un nodo.
Visualicemos este caso usando un ejemplo donde eliminaremos la clave 32 del siguiente árbol B.
Figura 4.1: Eliminar una clave de nodo hoja (32) del árbol B
Como podemos observar, eliminar 32 de este árbol no viola la propiedad anterior.
2. La eliminación/eliminación de la clave viola la propiedad del número mínimo de claves que debe contener un nodo. En este caso, debemos tomar prestada una clave de su nodo hermano más cercano en el orden de izquierda a derecha.
En primer lugar, visitaremos al hermano izquierdo más cercano. Si el nodo hermano izquierdo tiene más de un número mínimo de claves, tomará prestada una clave de este nodo.
De lo contrario, comprobaremos si queremos pedir prestado del nodo hermano derecho más cercano.
Visualicemos ahora este caso con la ayuda de un ejemplo en el que eliminaremos 31 del árbol B anterior. En este caso, tomaremos prestada una clave del nodo hermano izquierdo.
Figura 4.2: Eliminar una clave de nodo hoja (31) del árbol B
Si ambos nodos hermanos próximos ya constan de una cantidad mínima de claves, fusionaremos el nodo con el nodo hermano izquierdo o con el derecho. Este proceso de fusión se realiza a través del nodo principal.
Visualicemos nuevamente eliminando la clave 30 del árbol B anterior.
Figura 4.3: Eliminar una clave de nodo hoja (30) del árbol B
Caso 2: La eliminación/eliminación de la clave se encuentra en el nodo que no es hoja. Este caso se divide a su vez en diferentes casos:
1. El nodo interno/que no es hoja, que se elimina, se reemplaza por un predecesor en orden si el nodo secundario izquierdo tiene más que el número mínimo de claves.
Visualicemos este caso usando un ejemplo donde eliminaremos la clave 33 del Árbol B.
Figura 4.4: Eliminar una clave de nodo hoja (33) del árbol B
2. El nodo interno/que no es hoja, que se elimina, se reemplaza por un sucesor en orden si el nodo secundario derecho tiene más que el número mínimo de claves.
Si alguno de los hijos tiene una cantidad mínima de claves, fusionaremos los nodos secundarios izquierdo y derecho.
Visualicemos este caso eliminando la clave 30 del Árbol B.
Figura 4.5: Eliminar una clave de nodo hoja (30) del árbol B
Después de la fusión, si el nodo principal tiene menos del número mínimo de claves, se pueden buscar los hermanos, como en Caso 1 .
Caso 3: En el siguiente caso, la altura del árbol se reduce. Si la clave de destino se encuentra en un nodo interno y la eliminación de la clave genera menos claves en el nodo (que es menos que el mínimo necesario), entonces busque el predecesor en orden y el sucesor en orden. Si ambos hijos tienen un número mínimo de llaves, entonces no se puede pedir prestado. Esto lleva a Caso 2(3) , es decir, fusionar los nodos secundarios.
Volveremos a buscar al hermano para pedirle prestada una llave. Sin embargo, si el hermano también consta de una cantidad mínima de claves, fusionaremos el nodo con el hermano junto con el nodo padre y organizaremos los nodos secundarios según los requisitos (orden ascendente).
Visualicemos este caso con la ayuda de un ejemplo en el que eliminaremos el elemento de datos 10 del árbol B dado.
Figura 4.6: Eliminar una clave de nodo hoja (10) del árbol B
búsqueda lineal en java
La complejidad del tiempo en los ejemplos anteriores varía dependiendo de la ubicación desde donde se debe eliminar la clave. Por lo tanto, la complejidad temporal para la operación de eliminación en un árbol B es O(iniciar sesión?n) .
La conclusión
En este tutorial, aprendimos sobre el árbol B y visualizamos sus diferentes operaciones con diferentes ejemplos. También hemos comprendido algunas propiedades y reglas fundamentales del Árbol B.