Un B-tree est un arbre de recherche auto-équilibrant où chaque nœud contient de nombreuses clés et a de nombreux enfants (haut fanout). Cela garde l'arbre peu profond, minimisant le nombre de lectures disque — c'est exactement ce dont les bases de données et les systèmes de fichiers ont besoin.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
Dans un B+ tree, toutes les valeurs vivent dans les feuilles et les feuilles sont liées, donc les scans de plage parcourent une liste chaînée de feuilles — idéal pour les requêtes comme WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Opération | Temps | Lectures disque |
|---|---|---|
| recherche | O(log n) | O(hauteur) |
| insertion / suppression | O(log n) | O(hauteur) |
| scan de plage | O(log n + k) | feuilles séquentielles |
L'accès au disque et au SSD est des ordres de grandeur plus lent que la mémoire, donc la métrique qui compte est le nombre d'I/O, pas les comparaisons.
Le haut fanout réduit drastiquement les I/O en gardant l'arbre seulement quelques niveaux de profondeur.
C'est pourquoi presque tous les index de base de données relationnelle (et beaucoup de systèmes de fichiers) sont construits sur les B+ trees plutôt que sur les arbres de recherche binaires.