- Hace poco, mientras leía Database Internals de Alex Petrov, me encontré con explicaciones sobre cómo se implementan los motores de almacenamiento de los DBMS, en especial sobre las optimizaciones de la estructura de datos B-Tree
- Cuando aprendí B-Tree en la universidad, lo entendí simplemente como un “BST mejor”, así que no me quedaba claro por qué se usaba en la práctica
- Al considerar el I/O de disco, la estructura B-Tree resulta adecuada para almacenar grandes volúmenes de datos y buscarlos rápidamente
- Este artículo presenta por qué se necesita B-Tree, cómo funciona y qué optimizaciones son posibles en una implementación real
- Entre sus características principales está reunir muchas claves en un solo nodo para reducir la cantidad de accesos al disco
Restricciones causadas por el disco
- Se asume una situación en la que no todos los datos caben en memoria
- El disco tiene la característica de leer y escribir en unidades de página
- El acceso a disco es muchísimo más lento que el acceso a memoria
- Por eso, la estructura de datos necesita organizar la información con las páginas como unidad central y realizar la mayor cantidad posible de comparaciones de claves con el mínimo de accesos a disco
- Si se guarda un BST tal cual en disco, los nodos quedan dispersos y aparece el problema de que la cantidad de accesos a disco aumenta tanto como la cantidad de búsquedas
- B-Tree agrupa varias claves en un nodo para que, con una sola lectura de disco, se puedan comparar varias claves
Páginas ranuradas
- Al ubicar datos en disco, se administran en unidades llamadas “páginas”
- Cada página tiene un encabezado, celdas con datos de longitud variable y un arreglo de punteros de desplazamiento que guarda la posición de esas celdas
- La estructura de página ranurada tiene la ventaja de mantener el orden incluso si el tamaño de las claves es variable, sin la carga de tener que reordenar los datos reales
- Al borrar o insertar claves, es mucho más eficiente reordenar solo los punteros que mover los datos reales
- Por ejemplo, SQLite usa una free list dentro de esta estructura de páginas para reutilizar el espacio de las celdas eliminadas
Búsqueda en B-Tree
- El algoritmo de búsqueda de un B-Tree es sencillo:
- Empezar en el nodo raíz
- Revisar las claves separadoras (Separator Key) del nodo actual y encontrar el nodo hijo donde probablemente esté la clave buscada
- Recorrer el árbol de forma recursiva
- Si se encuentra el nodo hoja que contiene la clave buscada, termina; si no, se concluye que no existe
- En los nodos internos puede haber solo claves separadoras en lugar de los datos reales, y lo habitual es que los datos reales se almacenen solo en los nodos hoja
- Para encontrar las claves eficientemente dentro de cada nodo mediante búsqueda binaria, las claves de cada nodo se mantienen ordenadas
Reducción de claves separadoras (Separator Key)
- Las claves separadoras de los nodos internos no tienen que contener la clave completa real; basta con que puedan distinguir rangos
- Por ejemplo, para separar 0xAAAAAA y 0xBBBBBB no es necesario guardar todo 0xBBBBBB; se puede distinguir con un prefijo más corto
- En bases de datos con claves largas, esta reducción puede ahorrar una cantidad importante de espacio de almacenamiento
- Además de reducir las claves separadoras, también hay estrategias para reducir de forma eficiente prefijos (prefix) y sufijos (suffix)
- Como hay muchos más nodos hoja, también existe la idea de que la compresión de prefijos contribuye más al rendimiento
Páginas de desbordamiento
- Cuando un nodo tiene demasiadas claves y ya no caben todas en una sola página, se usan páginas de desbordamiento
- En lugar de mover la clave completa a la página de desbordamiento, en el nodo se deja solo un prefijo corto y el resto se almacena por separado
- Así, al verificar la existencia de una clave o al hacer búsquedas por rango, primero se revisa solo el prefijo del nodo y solo se lee la página de desbordamiento cuando realmente hace falta
- Aunque se asignen páginas adicionales, este método reduce el costo total de búsqueda
Punteros a hermanos
- Hay implementaciones que guardan en cada nodo punteros a los nodos hermanos izquierdo y derecho
- Esto permite que, en consultas por rango, se pueda saltar directamente desde un nodo hoja a su hermano y recorrer rápidamente claves contiguas
- Si no hubiera punteros a hermanos, habría que volver a subir al nodo padre y bajar otra vez repetidamente, lo que aumenta el costo de I/O
- Como los rangos de claves entre nodos hermanos no se superponen, moverse por el puntero al hermano derecho garantiza ir al “siguiente rango de claves”
Variantes de B-Tree
- Además de B⁺-Tree, existen varias estructuras derivadas
- “Lazy B-Tree”, como el de WiredTiger, y Lazy-Adaptive Tree usan buffering de operaciones de escritura para mejorar el rendimiento
- FD-Tree es una estructura diseñada para las características de los SSD y considera restricciones físicas como la escritura por bloques
- Bw-Tree (Buzzword Tree) es una estructura de datos optimizada para alta concurrencia y acceso al árbol en memoria
Conclusión
- Entre el concepto abstracto de “B⁺-Tree” y una implementación real como el “formato de base de datos de SQLite” existen muchas optimizaciones y diferencias de detalle en la implementación
- Las optimizaciones no cambian la complejidad Big-O, pero sí afectan enormemente el rendimiento y la usabilidad de una base de datos en entornos reales
- Además de lo presentado aquí, cada sistema de almacenamiento necesita mucho ajuste fino específico
- Detrás de la frase “solo hace falta un poco de información adicional” se esconden complejidad de implementación y dificultad para depurar
- Como ejemplo de una representación más realista de la estructura B-Tree, resulta muy llamativo el diagrama de B-Tree de Designing Data Intensive Applications
1 comentarios
Comentarios en Hacker News
La estructura de la página está compuesta por encabezado, celdas y punteros de desplazamiento, y tiene la ventaja de poder almacenar datos de tamaño variable
Es un excelente artículo sobre árboles B que incluye animaciones
Hace unos años implementé un B-link Tree con recuperación concurrente basado en la investigación de Ibrahim Jaluta
Hice un explorador de páginas en disco de SQLite y eso me ayudó a entender mejor los árboles B
Falta contenido sobre B-link trees, concurrencia y bloqueos, aunque eso podría ser más información de la necesaria
Comentarios anteriores: Hacker News
Es un gran artículo que explica muy bien la importancia de los detalles
Es un buen recurso sobre la implementación de árboles B usando Golang
Soy un gran fan de este artículo y tenía una "comprensión vaga" similar a la del autor