Un árbol B + es una estructura de datos utilizada a menudo en la implementación de índices de bases de datos. Cada nodo del árbol contiene una lista ordenada de claves y punteros para nodos de nivel inferior en el árbol. Se puede pensar que estos punteros están entre cada una de las teclas. Para buscar o insertar un elemento en el árbol, uno carga el nodo raíz, encuentra las claves adyacentes entre las que se encuentra el valor buscado y sigue el puntero correspondiente al siguiente nodo en el árbol. La recurrencia eventualmente conduce al valor deseado o a la conclusión de que el valor no está presente.
Los árboles B + utilizan algunas técnicas inteligentes de equilibrio para asegurarse de que todas las hojas estén siempre en el mismo nivel del árbol, que cada nodo esté siempre al menos medio lleno (redondeado) de teclas y (por lo tanto) que la altura del árbol siempre es como máximo techo (log (n) / log (k / 2)) (más o menos una constante, no recuerdo exactamente) donde n es el número de valores en el árbol yk es el número máximo de claves en cada bloque Esto significa que solo es necesario un pequeño número de recorridos de puntero para buscar un valor si el número de claves en un nodo es grande. Esto es crucial en una base de datos porque el árbol B + está en el disco. Leer un solo bloque lleva tanto tiempo como leer un bloque parcial, y un bloque puede contener una gran cantidad de teclas / punteros (128-1024 más o menos).
Finalmente, todas las hojas del árbol B + contienen un puntero “próximo hermano” para una iteración rápida a través de un bloque contiguo de valores. Esto permite consultas de rango extremadamente eficientes (encuentre el bloque que contiene el primer valor y atraviese a los hermanos hasta encontrar el último valor). Es especialmente eficiente si la implementación garantiza que los bloques de hojas son contiguos en el disco, aunque esto es un desafío hasta donde yo sé.
- ¿Qué es un píxel? ¿Cómo se puede medir en métrica?
- Cómo representar una característica incierta en Machine Learning
- ¿Qué son las redes neuronales en informática?
- ¿Cuál es la complejidad temporal de una búsqueda de una matriz asociativa (diccionario) en Python? ¿Cómo crece la velocidad de búsqueda con el número de pares clave-valor?
- ¿Cómo se puede crear una aplicación gratis?
Los árboles B + también se pueden usar fuera del disco, pero en general un árbol de búsqueda binario equilibrado o una lista de omisión o algo debería proporcionar un mejor rendimiento en la memoria, donde el seguimiento del puntero no es más costoso que encontrar el puntero correcto para seguir.
