B-Tree es un árbol multi-way auto-balanceado diseñado para sistemas de almacenamiento en bloque (discos, bases de datos). Cada nodo puede tener muchos hijos (branching factor t), reduciendo la altura del árbol y minimizando accesos a disco.

Es la estructura estándar para database indexing y filesystems.

Propiedades

Con grado mínimo t ≥ 2:

• Cada nodo (excepto raíz) tiene al menos t-1 keys y al menos t children.
• Cada nodo (excepto raíz y hojas) tiene a lo sumo 2t-1 keys y 2t children.
• Todas las hojas están al mismo nivel.

Estructura de Nodo

Cada nodo contiene:

• keys[0..k-1]: valores ordenados.
• children[0..k]: punteros a subárboles.
• leaf: booleano indicando si es hoja.

Split

Cuando un nodo se llena con 2t-1 keys y debes insertar uno nuevo, divides el nodo en dos:

1. Crea nuevo nodo.
2. Mueve t-1 keys del medio al nuevo nodo.
3. La key del medio sube al padre.
4. Si el padre se llena, recursivamente split hacia arriba.

Merge

Cuando un nodo tiene solo t-1 keys (mínimo) y pierde un key (por delete), puedes fusionar con un sibling:

1. Toma key del padre y añade al nodo.
2. Fusiona con sibling.
3. Si el padre queda con < t-1 keys, recursivamente merge hacia arriba.

Comparación con BST

B+ Tree

Variante donde:

• Los datos (registros) están solo en las hojas.
• Los nodos internos solo tienen keys para guiar la búsqueda.
• Las hojas están enlazadas (range scan eficiente).

Aplicaciones

• Databases — MySQL InnoDB, PostgreSQL indexes usan B+ trees.
• Filesystems — NTFS, HFS+, ext4 usan B-trees para directorios.
• LDAP — directorios jerárquicos.
• Enseñanza — introduce I/O-efficient data structures.

Trayectoria de Práctica

1. Investiga B-Tree con t=3; traza insert y split.
2. Investiga B+ Tree: ¿por qué las hojas enlazadas mejoran range queries?
3. ¿Por qué B-Tree es mejor que BST en disco?
4. Investiga LSM-tree: ¿cómo optimiza writes?
5. Investiga fractal tree: ¿qué ventaja tiene over B+ tree?