CHAPITRE 8 : B+ ARBRES, BASES DE DONNÉES ET SYSTÈMES DE FICHIERS

Presque aucune base de données n'utilise le B-arbre tel qu'on vient de l'étudier. Toutes emploient une variante : le B+ arbre : qui corrige deux défauts précis. Les comprendre, c'est comprendre pourquoi un CREATE INDEX accélère certaines requêtes et pas d'autres.

Les deux défauts du B-arbre classique

Premier défaut : les parcours d'intervalle sont pénibles. Pour lister toutes les clés entre deux bornes, il faut remonter chez le père puis redescendre à chaque changement de feuille. Sur une requête du type WHERE date BETWEEN … AND …, c'est désastreux.

Second défaut : les nœuds internes portent des données. Chaque clé d'un nœud interne traîne son enregistrement, ce qui réduit le nombre de clés par page, ce qui augmente la hauteur.

Les deux idées du B+ arbre

Ce que cela change

La recherche d'une clé isolée est légèrement moins bonne, puisqu'on ne peut plus s'arrêter dans un nœud interne. En échange, l'arbre est plus plat et les parcours deviennent triviaux. Pour une base de données, le marché est excellent.

Un B+ arbre, c'est un index au-dessus d'une liste triée.

Lire un plan de requête

Cette structure explique directement le comportement des bases de données.

-- rapide : descente dans l'index, 3 a 4 acces disque
SELECT * FROM clients WHERE id = 4218;

-- rapide : une descente, puis un parcours de la liste chainee
SELECT * FROM commandes WHERE date BETWEEN '2026-01-01' AND '2026-03-31';

-- rapide : l'index est deja trie, aucun tri a faire
SELECT * FROM clients ORDER BY nom LIMIT 20;

-- LENT : l'index est trie sur nom, pas sur ce qui suit le %
SELECT * FROM clients WHERE nom LIKE '%dupont';

La dernière requête est le cas d'école. Un index trié sur nom permet de trouver tout ce qui commence par une chaîne, puisque c'est un intervalle. Mais tout ce qui finit par une chaîne ne forme aucun intervalle : l'index ne sert à rien, et la base parcourt toute la table.

Index composés

Un index peut porter sur plusieurs colonnes à la fois : les clés sont alors comparées dans l'ordre lexicographique.

CREATE INDEX idx ON commandes (client_id, date);

-- utilise l'index pleinement
WHERE client_id = 42 AND date > '2026-01-01'

-- utilise l'index partiellement (seulement client_id)
WHERE client_id = 42

-- n'utilise PAS l'index : la premiere colonne manque
WHERE date > '2026-01-01'

La raison est géométrique : les clés sont triées d'abord par client_id, puis par date. Sans contrainte sur la première colonne, les lignes cherchées sont éparpillées dans tout l'index. C'est exactement comme chercher tous les mots dont la deuxième lettre est un K dans un dictionnaire.

Où l'on en trouve

Un système de fichiers fait le même travail qu'un index : retrouver un fichier par son nom dans un répertoire qui en contient des centaines de milliers, avec le moins d'accès disque possible. Le problème est identique, la solution aussi.

Et les autres structures ?

La table de hachage bat le B+ arbre sur la recherche d'égalité pure, c'est du O(1). Mais elle ne sait faire aucun parcours trié, aucun intervalle, aucun ORDER BY. Pour un index de base de données, cela la disqualifie dans la plupart des usages.

Les LSM-trees, eux, sont le concurrent sérieux du moment (LevelDB, RocksDB, Cassandra) : ils écrivent séquentiellement plutôt que de modifier des pages en place, ce qui convient mieux aux SSD et aux charges d'écriture intensives. Ils lisent en revanche moins bien.

log_200(10^8 / 2) = log(5x10^7) / log(200)
                   = 7,70 / 2,30
                   = 3,35  ->  4 niveaux

1000 / 270 = 3,7  ->  4 feuilles