Estructura de datos de árbol B y árbol B + en C ++

b tree b tree data structure c

Este tutorial de C ++ explica las estructuras de datos del árbol B y del árbol B +. Se utilizan para almacenar datos en discos cuando no se pueden almacenar todos los datos en la memoria principal:

B-tree es un árbol autoequilibrado, así como un árbol m-way especializado que se utiliza para el acceso al disco.

Cuando la cantidad de datos a almacenar es muy alta, no podemos almacenar todos los datos en la memoria principal. Por lo tanto, almacenamos datos en el disco. El acceso a los datos desde el disco lleva más tiempo en comparación con el acceso a la memoria principal.

Cuando el número de claves de los datos almacenados en discos es muy elevado, se suele acceder a los datos en forma de bloques. El tiempo para acceder a estos bloques es directamente proporcional a la altura del árbol.

=> Haga clic aquí para ver la serie de capacitación Absolute C ++.

Lo que vas a aprender:

• Árbol B en C ++
  • Operaciones básicas de B-Tree
    • # 1) Buscando
    • # 2) Inserción
    • # 3) Eliminación
  • Aplicaciones de los árboles B
• Árbol B + en C ++
  • Ventajas de los árboles B +
• Diferencia entre árbol B y árbol B +
• Conclusión
  • Lectura recomendada

Árbol B en C ++

El B-Tree es un árbol plano, es decir, la altura del árbol B se mantiene al mínimo. En cambio, se colocan tantas claves en cada nodo del árbol B. Al mantener la altura del árbol B al mínimo, el acceso es más rápido en comparación con otros árboles equilibrados como los árboles AVL.

A continuación se muestra un árbol B típico:

cómo agregar cosas a una matriz java

Generalmente, el tamaño del nodo en el árbol B se mantiene igual que el tamaño del bloque.

A continuación se enumeran algunas de las propiedades de B-Tree.

• Todas las hojas del árbol B están al mismo nivel.
• Un árbol B de orden m puede tener como máximo m-1 claves ym hijos.
• Cada nodo del árbol B tiene como máximo m hijos.
• El nodo raíz debe tener al menos dos nodos.
• Todos los nodos, excepto el nodo raíz y el nodo hoja, contienen m / 2 hijos.

A continuación, analizamos algunas de las operaciones básicas del árbol B.

Operaciones básicas de B-Tree

A continuación se muestran algunas de las operaciones básicas de B-Tree.

# 1) Buscando

La búsqueda en el árbol B es similar a la de BST. En el árbol anterior si queremos buscar el elemento 3, procederemos de la siguiente manera:

• Compare 3 con elementos raíz. Aquí, 3<6 and 3 <15. So we proceed to the left subtree.
• Compare 3 con 4 en el subárbol izquierdo. Como 3<4, we proceed to the left subtree of node 4.
• El siguiente nodo tiene dos claves, 2 y 3. 3> 2 mientras que 3 = 3. Entonces hemos encontrado la clave en este nodo. Regrese a la ubicación encontrada.

La búsqueda en el árbol B depende de la altura del árbol. Por lo general, se tarda O (log n) en buscar un elemento determinado.

# 2) Inserción

La inserción de un nuevo elemento en el árbol B se realiza en el nivel de los nodos hoja.

A continuación se muestra la secuencia de pasos (algoritmo) para insertar un nuevo elemento en el árbol B.

• Recorra el árbol B para encontrar una ubicación en los nodos de hoja para insertar el elemento.
• Si el nodo hoja contiene claves
• De lo contrario, si las claves del nodo hoja = m-1, entonces:
  • Inserte un elemento nuevo en un número creciente de elementos.
  • Tome la mediana de los nodos y divida el nodo en dos nodos.
  • Empuje la mediana a su nodo principal.
  • Si la clave del nodo principal = m-1, repita los pasos anteriores también para el nodo principal. Esto se hace hasta que encontremos el nodo hoja apropiado.
• Finalmente, inserte el elemento.

Hemos demostrado la inserción en el árbol B de la siguiente manera.

Insertemos el elemento 70 en el árbol que se muestra a continuación.

mejor VPN para streaming

El árbol dado tiene un grado mínimo 'm' = 3. Por lo tanto, cada nodo puede acomodar, 2 * m -1 = 5 claves dentro de él.

Ahora insertamos el elemento 70. Como podemos tener 5 claves en un nodo, comparamos el elemento 70 con el elemento raíz 30. Como 70> 30, insertaremos el elemento 70 en el subárbol derecho.

En el subárbol derecho, tenemos un nodo con las claves 40, 50, 60. Como cada nodo puede tener 5 claves, insertaremos el elemento 70 en este nodo.

Después de la inserción, el árbol B tiene el siguiente aspecto.

# 3) Eliminación

Al igual que la inserción, la eliminación de la clave también se realiza a nivel de nodos hoja. Pero a diferencia de la inserción, la eliminación es más complicada. La clave a eliminar puede ser un nodo hoja o un nodo interno.

Para eliminar una clave, seguimos la siguiente secuencia de pasos (algoritmo).

1. Localice el nodo hoja.

2. En caso de que el número de claves en un nodo> m / 2, elimine la clave dada del nodo.

3. En caso de que el nodo hoja no tenga claves m / 2, entonces necesitamos completar las claves tomando claves de los subárboles derecho o izquierdo para mantener el árbol B.

Seguimos estos pasos:

• Si el subárbol izquierdo contiene m / 2 elementos, empujamos su elemento más grande al nodo principal y luego movemos el elemento intermedio al lugar donde se eliminó la clave.
• Si el subárbol derecho contiene m / 2 elementos, empujamos su elemento más pequeño al nodo principal y luego movemos el elemento intermedio al lugar donde se eliminó la clave.

4. Si ningún nodo tiene m / 2 nodos, los pasos anteriores no se pueden realizar, por lo que creamos un nuevo nodo hoja uniendo dos nodos hoja y el elemento intermedio del nodo padre.

5. Si un padre no tiene m / 2 nodos, repetimos los pasos anteriores para el nodo padre en cuestión. Estos pasos se repiten hasta obtener un árbol B equilibrado.

A continuación se muestra una ilustración para eliminar un nodo del árbol B.

Considere el siguiente árbol B una vez más.

Supongamos que queremos eliminar la clave 60 del árbol B. Si revisamos el árbol B, podemos encontrar que la clave a eliminar está presente en el nodo hoja. Eliminamos la clave 60 de este nodo hoja.

Ahora el árbol se verá como se muestra a continuación:

Podemos notar que después de eliminar la clave 60, el nodo de la hoja del árbol B satisface las propiedades requeridas y no necesitamos hacer más modificaciones al árbol B.

Sin embargo, si tuviéramos que eliminar la clave 20, solo la clave 10 habría permanecido en el nodo de la hoja de la izquierda. En este caso, tendríamos que cambiar la raíz 30 al nodo hoja y mover la clave 40 a la raíz.

Por lo tanto, al eliminar una clave del árbol B, se debe tener cuidado y no se deben violar las propiedades del árbol B.

Recorrido en árbol B

El recorrido en el árbol B también es similar al recorrido en orden en BST. Comenzamos recursivamente desde la izquierda, luego llegamos a la raíz y avanzamos hacia el subárbol izquierdo.

Aplicaciones de los árboles B

• Los árboles B se utilizan para indexar los datos, especialmente en grandes bases de datos, ya que el acceso a los datos almacenados en grandes bases de datos en discos requiere mucho tiempo.
• La búsqueda de datos en conjuntos de datos sin clasificar más grandes lleva mucho tiempo, pero esto se puede mejorar significativamente con la indexación mediante el árbol B.

Árbol B + en C ++

El árbol B + es una extensión del árbol B. La diferencia en el árbol B + y el árbol B es que en el árbol B las claves y los registros se pueden almacenar como nodos internos y de hoja, mientras que en los árboles B +, los registros se almacenan como nodos de hoja y las claves se almacenan solo en nodos internos.

Los registros están vinculados entre sí en forma de lista vinculada. Esta disposición hace que las búsquedas de árboles B + sean más rápidas y eficientes. Los nodos internos del árbol B + se denominan nodos de índice.

Los árboles B + tienen dos órdenes, es decir, uno para los nodos internos y otro para los nodos de hoja o externos.

A continuación se muestra un ejemplo de árbol B +.

Como el árbol B + es una extensión del árbol B, las operaciones básicas que discutimos en el tema Árbol B aún se mantienen.

Al insertar y eliminar, debemos mantener intactas las propiedades básicas de los árboles B +. Sin embargo, la operación de eliminación en el árbol B + es comparativamente más fácil ya que los datos se almacenan solo en los nodos hoja y siempre se eliminarán de los nodos hoja.

Ventajas de los árboles B +

• Podemos buscar registros en un número igual de accesos al disco.
• En comparación con el árbol B, la altura del árbol B + es menor y permanece equilibrada.
• Usamos claves para indexar.
• Se puede acceder a los datos del árbol B + de forma secuencial o directa, ya que los nodos hoja se organizan en una lista vinculada.
• La búsqueda es más rápida ya que los datos se almacenan solo en los nodos hoja y como una lista vinculada.

Diferencia entre árbol B y árbol B +

Conclusión

En este tutorial, hemos discutido el árbol B y el árbol B + en detalle. Estas dos estructuras de datos se utilizan cuando hay una gran cantidad de datos y cuando todos los datos no se pueden almacenar en la memoria principal. Por lo tanto, para almacenar datos en discos, utilizamos el árbol B y el árbol B +.

La búsqueda del árbol B es un poco más lenta ya que los datos se almacenan en los nodos internos, así como en los nodos hoja. El árbol B + es una extensión del árbol B y los datos aquí se almacenan solo en los nodos hoja. Debido a este factor, la búsqueda en un árbol B + es más rápida y eficiente.

cómo declarar una cola en java

=> Visite aquí para ver la lista completa de tutoriales de C ++.

Lectura recomendada

• Estructura de datos de montón y árbol AVL en C ++
• Estructura de datos de lista vinculada en C ++ con ilustración
• Estructura de datos de cola en C ++ con ilustración
• Estructura de datos de pila en C ++ con ilustración
• Estructura de datos de lista enlazada circular en C ++ con ilustración
• Introducción a las estructuras de datos en C ++
• Estructura de datos de cola de prioridad en C ++ con ilustración
• Estructura de datos de lista doblemente enlazada en C ++ con ilustración