Diferencia entre el árbol B y el árbol B+

Árbol B: Un B-Tree se denomina árbol autoequilibrado porque sus nodos están ordenados en el orden transversal. En un árbol B, un nodo puede tener más de dos hijos. El logM N es la altura del árbol B (donde ‘M’ es el orden del árbol y N es el número de nodos). Y la altura se ajusta automáticamente en cada actualización. En el árbol B, los datos están ordenados, con el valor más bajo a la izquierda y el valor más alto a la derecha. Insertar los datos o la clave en un árbol B es más complejo que un árbol binario. El B-Tree debe cumplir varias condiciones:

  • Todos los nodos hoja del árbol B deben estar al mismo nivel.
  • Por encima de los nodos hoja del árbol B, no debe haber subárboles vacíos.
  • La altura del árbol B debe ser lo más baja posible.

Árbol B+ Un árbol B+ elimina la desventaja de un árbol B utilizado para la indexación al almacenar punteros de datos solo en los nodos de hoja del árbol. Por lo tanto, la estructura de los nodos de hoja de un árbol B+ es muy diferente de la estructura de los nodos internos del árbol B. Cabe señalar aquí que dado que los punteros de datos están presentes solo en los nodos de hoja, los nodos de hoja deben contener la valores clave todos almacenados junto con su directorio de datos correspondiente para el bloque de archivos de disco, para acceder a ellos. Además, los nodos hoja están vinculados para proporcionar un acceso ordenado a los registros. Los nodos hoja son, por tanto, el primer nivel del índice, y los nodos internos los demás niveles de un índice multinivel. Algunos de los valores clave de los nodos hoja también aparecen en los nodos internos, para actuar como un medio para controlar la búsqueda de registros.

Veamos la diferencia entre un árbol B y un árbol B+:

Base de comparaciónárbol Bárbol B+
PuntasTodos los nodos internos y las hojas tienen punteros de datos.Solo los nodos de hoja tienen punteros de datos
BúsquedaDado que no todas las claves están disponibles en la hoja, la búsqueda suele llevar más tiempo.Todas las claves están en los nodos hoja, por lo que la búsqueda es más rápida y precisa.
Teclas redundantesNo se guardan claves duplicadas en el árbol.Las claves duplicadas se mantienen y todos los nodos están presentes en la hoja.
InsertarLa interrupción lleva más tiempo y, a veces, es impredecible.La inserción es más fácil y los resultados son siempre los mismos.
supresiónBorrar el nodo interno es muy complicado y el árbol tiene que sufrir muchas transformaciones.Eliminar cualquier nodo es fácil porque todos los nodos se encuentran en la hoja.
Nodos de hojaLos nodos hoja no se almacenan como una lista enlazada estructurada.Los nodos hoja se almacenan como una lista enlazada estructurada.
AccesoEl acceso secuencial a los nodos no es posibleEl acceso secuencial es posible al igual que la lista enlazada
AlturaPara un cierto número de nodos hay más alturaLa altura es menor que el árbol B para el mismo número de nodos
SolicitudB-Trees utilizados en bases de datos, motores de búsquedaÁrboles B+ utilizados en indexación multinivel, indexación de bases de datos
Número de nodosEl número de nodos en cualquier nivel intermedio ‘l’ es 2yo.Cada nodo intermediario puede tener de n/2 a n hijos.
Mis notas personales
flecha_caer_arriba

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *