Un B-tree (árbol B) es una estructura de datos de árbol de búsqueda auto-balanceado que generaliza el concepto de un árbol binario de búsqueda, permitiendo que cada nodo tenga más de dos hijos. Su característica principal es que todos los nodos hoja se encuentran en el mismo nivel de profundidad, y los nodos internos pueden tener un número variable de hijos dentro de un rango predefinido (orden del árbol). Esto minimiza la altura del árbol, lo que es crucial para reducir el número de operaciones de I/O al acceder a datos almacenados en disco o SSD, donde el costo de acceso secuencial es significativamente menor que el acceso aleatorio. Los B-trees garantizan que las operaciones de búsqueda, inserción y eliminación se realicen en tiempo O(log N), donde N es el número de elementos.
Los B-trees son fundamentales en la implementación de sistemas de gestión de bases de datos (DBMS) y sistemas de archivos debido a su eficiencia en el manejo de grandes volúmenes de datos persistentes. Ejemplos concretos incluyen: los índices de la mayoría de las bases de datos relacionales como PostgreSQL (usando B-trees por defecto para índices primarios y secundarios), MySQL (especialmente con el motor InnoDB), Oracle Database y SQL Server. También son la base de muchos sistemas de archivos, como NTFS de Microsoft, HFS+ de Apple y algunos sistemas de archivos de Linux como XFS y Btrfs (aunque Btrfs usa B-trees modificados, conocidos como B-trees copy-on-write o B-trees COW).
Para un arquitecto de sistemas, comprender los B-trees es crucial para diseñar soluciones de almacenamiento y bases de datos eficientes. La elección de B-trees para indexación impacta directamente el rendimiento de las consultas, especialmente en cargas de trabajo OLTP con muchas operaciones de lectura y escritura. Los trade-offs incluyen el espacio en disco adicional requerido para los índices y el costo de mantener el árbol balanceado durante las inserciones y eliminaciones. Un arquitecto debe considerar el orden del B-tree (número máximo de hijos por nodo) en relación con el tamaño de bloque del disco para optimizar las operaciones de I/O. Además, el conocimiento de B-trees es esencial para evaluar alternativas como "Log-Structured Merge-trees" (LSM-trees) en bases de datos NoSQL, entendiendo sus diferentes perfiles de rendimiento y durabilidad.