database - tag - b-tree base de datos
Diferencias entre árboles B y árboles B+ (14)
- En un árbol B, busque las claves y los datos almacenados en nodos internos o de hoja. Pero en B + -tree data store solo nodos hoja.
- La búsqueda de datos en un árbol B + es muy fácil porque todos los datos se encuentran en nodos de hoja. La búsqueda de un árbol B requiere un recorrido completo.
- En un árbol B, los datos se pueden encontrar en nodos de 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 de hoja. La eliminación de los nodos de la hoja es fácil.
- La inserción en el árbol B es más complicada que el árbol B +.
- Los árboles B + almacenan la clave de búsqueda redundante, pero el árbol B no tiene valor redundante.
- En un árbol B +, los datos de los nodos hoja se ordenan como una lista enlazada secuencial, pero en el árbol B el nodo hoja no se puede almacenar utilizando una lista enlazada. Muchas implementaciones de sistemas de bases de datos prefieren la simplicidad estructural de un árbol B +.
En un árbol B puede almacenar claves y datos en los nodos internos y de hoja , pero en un árbol b + debe almacenar los datos solo en los nodos de 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é necesita replicar la clave (datos) en un árbol b +?
**
El principal inconveniente de B-Tree es la dificultad de atravesar las teclas de forma secuencial. El árbol B + conserva la propiedad de acceso aleatorio rápido del árbol B, al mismo tiempo que permite un acceso secuencial rápido
** ref: Estructuras de datos utilizando C // Autor: Aaro M Tenenbaum
Adegoke A, Amit
Supongo que un punto crucial que les falta a ustedes es la diferencia entre los datos y los indicadores, 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 simplemente otro indicador de 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 teclas y puntero a los nodos secundarios.
En el nodo interno del árbol B +, mantenga las claves y los punteros al nodo secundario, mientras que el nodo de hoja mantenga las claves y los punteros a los datos asociados. Esto permite un mayor número de claves para un tamaño dado de nodo. 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 mucho más arriba, así que ahorraré mi esfuerzo de escritura.
Ejemplo de los conceptos del sistema de base de datos 5
B + -tree
árbol B correspondiente
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 recuperar del almacenamiento externo en un solo disco, procesados para encontrar la ubicación del destino. Si ha sido un árbol B, se requiere una lectura del disco para todos y cada uno de los procesos de toma de decisiones. Espero haber dejado claro mi punto! :)
La distinción principal entre el árbol B y el árbol B + es que el árbol B elimina el almacenamiento redundante de los valores de las claves 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 Sin embargo, como la clave de búsqueda que aparece en los nodos sin hojas 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 sin hojas. Son ventajas de espacio para el árbol B, ya que la repetición no se produce y se puede utilizar para índices grandes.
La principal ventaja de los árboles B + sobre los árboles B es que le permiten empaquetar más punteros a otros nodos eliminando los punteros a los datos, lo que aumenta el fanout y posiblemente reduce la profundidad del árbol.
La desventaja es que no hay salidas anticipadas cuando podría haber encontrado una coincidencia en un nodo interno. Pero como ambas estructuras de datos tienen fanouts enormes, la gran mayoría de tus coincidencias estarán en nodos de hoja de todos modos, haciendo que el árbol B + sea más eficiente en promedio.
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 los nodos interiores, pueden caber más teclas 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 de 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 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.
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 el principio de mi cabeza):
fanout alto / profundidad baja: eso significa que debe obtener menos bloques para llegar a los datos. Con los datos entremezclados con los punteros, cada lectura recibe 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 hace que sea fácil de analizar, depurar e incluso reconstruir.
la alta densidad de claves significa que los nodos superiores están casi seguramente en la memoria caché, en muchos casos todos los nodos internos se almacenan rápidamente en caché, por lo que solo el acceso a los datos debe ir al disco.
Los árboles B + son mucho más fáciles y de mayor rendimiento para realizar un escaneo completo, como en cada dato que indexa el árbol, ya que los nodos terminales forman una lista enlazada. Para realizar un escaneo completo con un árbol B, debe hacer un recorrido completo del árbol para encontrar todos los datos.
Por otro lado, los B-Trees pueden ser más rápidos cuando realiza una búsqueda (en busca de una pieza específica de datos por clave), especialmente cuando el árbol reside en la RAM u otro almacenamiento sin bloque. Dado que puede elevar los nodos de uso común en el árbol, se requieren menos comparaciones para obtener los datos.
Tome un ejemplo: tiene una tabla con datos enormes por fila. Eso significa que cada instancia del objeto es grande.
Si usa el árbol B aquí, la mayor parte del tiempo lo 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 + Árboles separan las claves de los datos.
Pero si el tamaño de sus datos es menor, entonces puede almacenarlos con la clave, que es lo que hace el árbol B.
Un árbol B + es un árbol equilibrado en el que cada ruta desde la raíz del árbol a una hoja es de la misma longitud, y cada nodo no hoja del árbol tiene entre [n / 2] y [n] hijos, donde n es fijado para un árbol en particular. Contiene páginas de índice y páginas de datos. Los árboles binarios solo tienen dos hijos por nodo principal, los árboles B + pueden tener un número variable de hijos para cada nodo principal
Un posible uso de los árboles B + es que es adecuado para situaciones en las que el árbol crece tan grande que no cabe en la memoria disponible. Por lo tanto, generalmente se espera que se hagan varias E / S.
Ocurre a menudo que se utiliza un árbol B + incluso cuando de hecho cabe en la memoria, y luego su administrador de caché puede mantenerlo allí de forma permanente. Pero este es un caso especial, no el general, y la política de almacenamiento en caché es un mantenimiento separado del árbol B + como tal.
Además, en un árbol B +, las páginas de la hoja están vinculadas entre sí en una lista enlazada (o lista doblemente enlazada), 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 usa.