¿Cuáles son las diferencias entre los árboles B y los árboles B+?

Resuelto simplfuzz asked hace 15 años • 0 respuestas

En un árbol b puede almacenar claves y datos en los nodos interno y hoja , pero en un árbol b+ debe almacenar los datos solo en los nodos hoja .

¿Existe alguna ventaja de hacer lo anterior en un árbol b+?

¿Por qué no utilizar árboles b en lugar de árboles b+ en todas partes, ya que intuitivamente parecen mucho más rápidos?

Quiero decir, ¿por qué necesitas replicar la clave (datos) en un árbol b+?

simplfuzz avatar May 16 '09 01:05 simplfuzz
Aceptado

La siguiente imagen ayuda a mostrar las diferencias entre los árboles B+ y los árboles B.

Ventajas de los árboles B+:

  • Debido a que los árboles B+ no tienen datos asociados con nodos interiores, pueden caber más claves en una página de memoria. Por lo tanto, se necesitarán menos errores de caché para poder acceder a los datos que se encuentran en un nodo hoja.
  • Los nodos de hoja de los árboles B+ están vinculados, por lo que realizar un escaneo completo de todos los objetos en un árbol requiere solo un paso lineal a través de todos los nodos de hoja. El árbol AB, por otro lado, requeriría atravesar todos los niveles del árbol. Este recorrido de árbol completo probablemente implicará más errores de caché que el recorrido lineal de hojas B+.

Ventaja de los árboles B:

  • Debido a que los árboles B contienen datos con cada clave, los nodos a los que se accede con frecuencia pueden estar más cerca de la raíz y, por lo tanto, se puede acceder a ellos más rápidamente.

Árbol B y B+

Rose Perrone avatar Aug 17 '2012 23:08 Rose Perrone

La principal ventaja de los árboles B+ sobre los árboles B es que le permiten incluir más punteros a otros nodos eliminando punteros a datos, aumentando así la distribución en abanico y potencialmente disminuyendo la profundidad del árbol.

La desventaja es que no hay salidas anticipadas cuando es posible que haya encontrado una coincidencia en un nodo interno. Pero dado que ambas estructuras de datos tienen enormes distribuciones, la gran mayoría de sus coincidencias se realizarán en nodos hoja de todos modos, lo que hace que, en promedio, el árbol B+ sea más eficiente.

Vic E avatar May 15 '2009 19:05 Vic E