B-Tree
Un árbol B es un árbol de búsqueda multicamino autobalanceado donde cada nodo guarda varias claves y punteros a hijos, garantizando búsquedas O(log N) con un fan-out casi O(1).
Propósito
Comprender la estructura de datos central de los índices de bases de datos y analizar su rendimiento de lectura/escritura y el llenado de páginas.
Mecanismo
Un árbol B de orden m tiene como máximo m hijos por nodo y al menos ceil(m/2). Las inserciones se dividen y los borrados se fusionan para mantener el equilibrio; todas las hojas están a la misma profundidad. El tamaño del nodo se alinea con la E/S de página de la base de datos (p. ej., 16 KB), y el fan-out alto mantiene el árbol bajo (3-4 niveles indexan TB).
Casos de uso
- Estructuras de datos de índice
- Interior de las bases de datos
- Optimización del almacenamiento