Accueil › SQL & bases de données › Comment fonctionne un index B-tree
Comment fonctionne un index B-tree
Les indexintermediaire
Un index B-tree est un arbre trié : au lieu de parcourir un million de lignes, la base descend quelques niveaux et trouve directement les entrées voulues.
CREATE INDEX commande_client_id_idx ON commande (client_id);
-- Sans index : Seq Scan, 1 000 000 lignes lues
-- Avec index : Index Scan, quelques pages lues
SELECT * FROM commande WHERE client_id = 42;
Trois idées à retenir avant toute optimisation.
Un index n'est pas toujours le bon choix. S'il faut ramener 40 % de la table, lire séquentiellement coûte moins cher que des centaines de milliers d'accès dispersés. C'est l'optimiseur qui tranche, en comparant des coûts estimés. Un Seq Scan n'est donc pas un échec en soi.
Le meilleur index est celui qui évite de lire la table. Si toutes les colonnes demandées figurent dans l'index, PostgreSQL fait un index-only scan :
CREATE INDEX ON commande (client_id, creee_le);
SELECT creee_le FROM commande WHERE client_id = 42; -- la table n'est pas lue
Chaque index se paie à l'écriture. Dix index, c'est dix arbres à maintenir à chaque INSERT. Un index qui ne sert jamais est un coût permanent — et ils sont plus nombreux qu'on ne croit.
ORDER BY et les préfixes de texte.Les termes à connaître
- Index B-tree
L'index par défaut : un arbre équilibré dont les feuilles contiennent les valeurs triées et un pointeur vers la ligne. Toute recherche coûte quelques sauts, quel que soit le volume.
- Parcours séquentiel (*seq scan*)
Lire toute la table, ligne par ligne. Souvent le meilleur choix quand la requête ramène une grande partie des lignes : la lecture séquentielle est bien plus rapide que des accès dispersés.
- Parcours d'index (*index scan*)
Descendre dans l'arbre pour trouver les entrées, puis lire les lignes correspondantes dans la table. Efficace quand la requête est sélective.
- Sélectivité
La proportion de lignes que ramène un filtre. Un filtre très sélectif (0,1 % des lignes) justifie un index ; un filtre qui ramène 40 % de la table, presque jamais.
- Index-only scan
Quand toutes les colonnes demandées sont dans l'index, la table n'est pas lue du tout. Le gain est considérable — à condition que la carte de visibilité soit à jour (donc que
VACUUMsoit passé).- Coût d'écriture
Chaque
INSERT,UPDATEouDELETEdoit maintenir tous les index de la table. Dix index, c'est dix arbres à mettre à jour à chaque écriture.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.