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

293

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 .

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

¿Por qué no usar b-trees en lugar de b + trees 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 +?

database data-structures simplfuzz
fuente
37
Creo que lo que dicen es "B-Tree" vs. B + -Tree. Significan un guión, no un signo menos.
stu

Respuestas:

421

La imagen a continuación 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 los nodos interiores, pueden caber más claves en una página de memoria. Por lo tanto, requerirá menos errores de caché para 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 hacer 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 un recorrido de cada nivel en el árbol. Este recorrido de árbol completo probablemente implicará más errores de caché que el recorrido lineal de las 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.

B y B + árbol

Rose Perrone
fuente
2
¿Existe alguna restricción en el número de entradas en el nodo hoja?
TLE
38
@TLE Buena pregunta! Si. Un disco duro accede a un mínimo de una página de memoria a la vez, por lo que queremos ajustar todos los punteros en una sola página de memoria. Queremos requerir solo una lectura de disco por acceso de hoja, por lo que no queremos asignar más de un tamaño de página de punteros a una hoja. Si llenamos una hoja con un tamaño de página de punteros, y luego queremos agregar otro puntero a esta hoja, creamos dos hijos de este nodo y le damos la mitad de los punteros de la hoja a cada niño nuevo. Por supuesto, puede haber algunas modificaciones para garantizar que la altura del árbol se mantenga al mínimo. ¿Esto ayuda?
Rose Perrone
el último puntero de cada nodo hoja del árbol B debe apuntar al siguiente nodo hoja, ¿verdad?
camino
8
Lamento mucho haber topado un hilo tan viejo, pero el comentario de @ Babyburger sobre cómo el comentario de camino era correcto no es realmente cierto; un B-Tree, de hecho, no tiene nodos hoja conectados. A B +, claro.
Jason
Gracias por la excelente respuesta, ¿qué es un caso de uso cuando se necesitaría un escaneo completo de los objetos en un árbol B / B + en un contexto de base de datos? Dado que se usa principalmente para la indexación, las búsquedas casi nunca necesitarían escanear todo el árbol a la derecha y, en su lugar, atravesar la ruta del índice, ¿es correcto?
Siddhartha
113

La principal ventaja de los árboles B + sobre los árboles B es que le permiten agrupar más punteros a otros nodos al eliminar los punteros a los datos, lo que aumenta el despliegue y potencialmente disminuye la profundidad del árbol.

La desventaja es que no hay salidas tempranas cuando podría haber encontrado una coincidencia en un nodo interno. Pero dado que ambas estructuras de datos tienen grandes despliegues, la gran mayoría de sus coincidencias estarán en nodos hoja de todos modos, lo que hace que, en promedio, el árbol B + sea más eficiente.

Vicio
fuente
1
Prefiero la respuesta de Jeff, porque enfatiza la diferencia de eficiencia al hacer un escaneo completo.
Rose Perrone
Estoy realmente confundido porque atravesar un árbol b usando un recorrido en orden leerá todos los valores en orden ordenado en el tiempo O (n). Si cada nodo de árbol tiene un tamaño óptimo para el tamaño de página física, parece que las cosas no se vuelven más óptimas. Por el contrario, el costo para llegar al primer valor (el más pequeño) en un árbol b + es O (log n) y luego recorrer cada hoja es O (n), por lo que el costo total es O (log n + n). Esto es más trabajo y más lecturas de disco, lo que tiene sentido porque el árbol tiene todos estos datos adicionales. No lo entiendo
Eric
¿Cuál sería otra palabra para 'fanout' en la oración anterior?
Jorge Bucaran
3
@JorgeBucaran fanout = número de bordes que salen de un nodo
bantmen
33

Los árboles B + son mucho más fáciles y de mayor rendimiento para hacer un escaneo completo, como en la observación de cada dato que indexa el árbol, ya que los nodos terminales forman una lista vinculada. Para hacer un escaneo completo con un B-Tree, debe hacer un recorrido completo del árbol para encontrar todos los datos.

B-Trees, por otro lado, puede ser más rápido cuando realiza una búsqueda (buscando un dato específico por clave), especialmente cuando el árbol reside en la RAM u otro almacenamiento sin bloques. Como puede elevar los nodos de uso común en el árbol, se requieren menos comparaciones para llegar a los datos.

Jeff Mc
fuente
1
¿Estaría de acuerdo en que un árbol B + se usaría para situaciones en las que puede haber una lectura secuencial en todos los datos para poder pasar por las hojas? Mientras que el árbol B sería ideal para situaciones de acceso aleatorio?
JDPeckham
31
  1. En un árbol B, las claves de búsqueda y los datos se almacenan en nodos internos u hoja. Pero en un árbol B +, los datos se almacenan solo en nodos hoja.
  2. El escaneo completo de un árbol B + es muy fácil porque todos los datos se encuentran en nodos hoja. El escaneo completo de un árbol B requiere un recorrido completo.
  3. En un árbol B, los datos se pueden encontrar en nodos hoja o nodos internos. La eliminación de nodos internos es muy complicada. En un árbol B +, los datos solo se encuentran en los nodos hoja. La eliminación de nodos de hoja es fácil.
  4. La inserción en el árbol B es más complicada que el árbol B +.
  5. Los árboles B + almacenan claves de búsqueda redundantes, pero el árbol B no tiene un valor redundante.
  6. En un árbol B +, los datos del nodo hoja se ordenan como una lista enlazada secuencial pero en un árbol B el nodo hoja no se puede almacenar usando una lista enlazada. Las implementaciones de muchos sistemas de bases de datos prefieren la simplicidad estructural de un árbol B +.
androidcodehunter
fuente
15

Ejemplo de conceptos del sistema de base de datos 5to

B + -tree B + árbol

árbol B correspondiente Btree

camino
fuente
55
No creo que un B-Tree tenga enlaces a los hijos del nodo. Por ejemplo, formar el Clearview bucketa Mianus Bucket. No tendría mucho sentido hacer eso de todos modos porque entre los dos tienes lo Downtown bucketque se debe buscar en caso de que quieras hacer un Escaneo de índice en un árbol B (requiere retroceso). ¿De dónde has sacado esto?
Evan Carroll
1
Base de datos del sistema @EvanCarroll conceptos quinto, tal vez usted tiene que confirmar con el autor :)
Camino
11

Definir "mucho más rápido". Asintóticamente son casi lo mismo. Las diferencias radican en cómo hacen uso del almacenamiento secundario. Los artículos de Wikipedia sobre árboles B y árboles B + parecen bastante confiables.

Charlie Martin
fuente
2
Estoy de acuerdo con Charlie Dado que un nodo de un B-Tree representa una página o bloque de memoria secundaria, el paso de un nodo a otro requiere un cambio de página lento.
11

Adegoke A, Amit

Supongo que un punto crucial que le falta a la gente es la diferencia entre los datos y los punteros como se explica en esta sección.

Puntero: puntero a otros nodos.

Datos: - En el contexto de los índices de la base de datos, los datos son solo otro puntero a los datos reales (fila) que residen en otro lugar.

Por lo tanto, en el caso del árbol B, cada nodo tiene tres claves de información, punteros a los datos asociados con las claves y puntero a los nodos secundarios.

En el árbol interno B +, mantenga las claves y los punteros en el nodo secundario, mientras que el nodo hoja mantiene las claves y los punteros en los datos asociados. Esto permite más número de clave para un tamaño de nodo dado. El tamaño del nodo está determinado principalmente por el tamaño del bloque.

La ventaja de tener más clave por nodo se explica más arriba, por lo que ahorraré mi esfuerzo de escritura.

Saket
fuente
10

Los árboles B + son especialmente buenos en el almacenamiento basado en bloques (por ejemplo: disco duro). Con esto en mente, obtienes varias ventajas, por ejemplo (desde la parte superior de mi cabeza):

  • alto abanico / baja profundidad: eso significa que debe obtener menos bloques para acceder a los datos. Con los datos entremezclados con los punteros, cada lectura obtiene menos punteros, por lo que necesita más búsquedas para llegar a los datos.

  • almacenamiento de bloques simple y consistente: un nodo interno tiene N punteros, nada más, un nodo hoja tiene datos, nada más. eso facilita analizar, depurar e incluso reconstruir.

  • La alta densidad de claves significa que los nodos superiores están casi seguramente en caché, en muchos casos todos los nodos internos se almacenan en caché rápidamente, por lo que solo el acceso a datos debe ir al disco.

Javier
fuente
2
principalmente para árboles en memoria; pero hay otras opciones populares, como árboles rojo-negros, listas de omisión, etc.
Javier
Los árboles B también están diseñados para un almacenamiento eficiente basado en bloques, lo que limita el número asintótico de accesos de nodos. De lo contrario, si usa un medio de almacenamiento similar a la memoria con acceso aleatorio, se puede usar un árbol binario de equilibrio automático como un árbol rojo-negro para lograr mejores resultados.
dionyziz 01 de
su primer punto no debería decir "menos busca" en lugar de "más busca". Menor profundidad -> menos busca
Jesse
1
@Jesse: alto fanout => baja profundidad => menos búsquedas, pero mezclar datos y punteros significa menos punteros => bajo fanout => más profundidad => más búsquedas
Javier
1
@AdegokeA: un árbol B + tiene dos tipos de nodos: nodos internos con solo teclas y punteros, sin datos; y nodos hoja, con datos y sin punteros. que permite la cantidad máxima de claves en cada nodo interno. Si almacena datos en un nodo interno, puede ajustar menos punteros y su árbol se hace más alto.
Javier
5

En B + Tree, dado que solo los punteros se almacenan en los nodos internos, su tamaño se vuelve significativamente más pequeño que los nodos internos del árbol B (que almacenan ambos datos + clave). Por lo tanto, los índices del árbol B + se pueden obtener del almacenamiento externo en una sola lectura de disco, procesada para encontrar la ubicación del destino. Si ha sido un árbol B, se requiere una lectura de disco para todos y cada uno de los procesos de toma de decisiones. Espero haber aclarado mi punto! :)

VS7
fuente
4

** **

El principal inconveniente de B-Tree es la dificultad de atravesar las teclas secuencialmente. El árbol B + retiene la propiedad de acceso aleatorio rápido del árbol B al tiempo que permite un acceso secuencial rápido

** ref: Estructuras de datos usando C // Autor: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+sequentially&source=bl&ots=pGcPQSEJMS&sig= F9MY7zEXYAMVKl_Sg4W-0LTRor8 & hl = en & sa = X & ei = nD5AUbeeH4zwrQe12oCYAQ & ved = 0CDsQ6AEwAg # v = onepage & q = drawback% 20of% 20B-Tree% 20is% 20%% 20%% 20%% 20%% 20%% 20%% 20%

Kapil Kumar
fuente
1
Esta debería haber sido la respuesta correcta. En resumen: localidad de referencia.
Theodore Zographos
2

Tome un ejemplo: tiene una tabla con grandes datos por fila. Eso significa que cada instancia del objeto es grande.

Si usa el árbol B aquí, la mayor parte del tiempo se dedica a escanear las páginas con datos, lo que no sirve de nada. En las bases de datos, esa es la razón de usar B + Trees para evitar escanear datos de objetos.

B + Los árboles separan las claves de los datos.

Pero si el tamaño de sus datos es menor, puede almacenarlos con la clave, que es lo que hace el árbol B.

Amit
fuente
1
"Si usa el árbol B aquí, la mayor parte del tiempo se pasa escaneando las páginas con datos", no es necesario. Los nodos del árbol B solo pueden mantener "punteros" a los datos en el disco, no a los datos en sí.
TT_
2

La distinción principal entre el árbol B y el árbol B + es que el árbol B elimina el almacenamiento redundante de valores de clave de búsqueda. Dado que las claves de búsqueda no se repiten en el árbol B, es posible que no podamos almacenar el índice utilizando menos nodos de árbol que en el índice del árbol B + correspondiente. Sin embargo, dado que la clave de búsqueda que aparece en los nodos no hoja no aparece en ningún otro lugar en el árbol B, nos vemos obligados a incluir un campo de puntero adicional para cada clave de búsqueda en un nodo no hoja. Son ventajas de espacio para el árbol B, ya que la repetición no ocurre y puede usarse para índices grandes.

María
fuente
1
Interesante, los pensamientos sobre la repetición son únicos entre las respuestas aquí y tienen más sentido que el recorrido en orden de b + tree sea más eficiente que el recorrido en orden de un b-tree. Por lo que puedo decir, eso no es del todo correcto, o no toda la historia, ya que en orden el recorrido de un árbol b es O (n) y encontrar el nodo más pequeño en un árbol b + es O (log n) y luego atravesar cada hoja es O (n) además de eso. Sin embargo, si estaba indexando algo con un pequeño rango de valores, como un campo booleano, el árbol b + tiene mucho más sentido que un árbol b debido a su manejo duplicado.
Eric
1

Un árbol B + es un árbol equilibrado en el que cada camino desde la raíz del árbol hasta una hoja es de la misma longitud, y cada nodo no hoja del árbol tiene entre [n / 2] y [n] hijos, donde n es arreglado para un árbol en particular. Contiene páginas de índice y páginas de datos. Los árboles binarios solo tienen dos hijos por nodo padre, los árboles B + pueden tener un número variable de hijos por cada nodo padre

Vivek Rakholiya
fuente
1
Solo por claridad, los árboles B no son árboles binarios. De hecho, los árboles B y los árboles B + están más cerca uno del otro en la construcción y el uso que los árboles binarios. Los artículos wiki pueden ayudar a aclarar las definiciones: árbol B + , árbol B y árbol binario
uutsav
1

Un posible uso de los árboles B + es que es adecuado para situaciones en las que el árbol crece tanto que no cabe en la memoria disponible. Por lo tanto, generalmente esperaría estar haciendo múltiples E / S.
A menudo sucede que se usa un árbol B + incluso cuando de hecho cabe en la memoria, y luego su administrador de caché podría mantenerlo allí permanentemente. Pero este es un caso especial, no general, y la política de almacenamiento en caché es independiente del mantenimiento del árbol B + como tal.

Además, en un árbol B +, las páginas de hoja están vinculadas entre sí en una lista vinculada (o lista doblemente vinculada), que optimiza los recorridos (para búsquedas de rango, clasificación, etc.). Entonces, el número de punteros es una función del algoritmo específico que se utiliza.

programador de pila
fuente
Esto es en respuesta a la pregunta de que ¿por qué no utilizar los árboles B + B en lugar de árboles por todas partes :)
pila programador de
3
Pero usted solo describió un lado, hasta donde sabemos, con su respuesta b-trees podría funcionar exactamente de la misma manera. El OP le pidió que explicara las diferencias y usted solo habló de una y no de la otra. ¡No puedes tener un diagrama de Venn con un círculo!
Malfist