Formations — 1 037 leçons en français

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.

WHERE client_id = 42 1 … 100 … 200 racine 1 … 40 … 80 100 … 160 200 … 280 nœuds 40 41 42 43 44 45 46 … … 160 161 … … 280 281 … feuilles triées, chaînées entre elles la ligne dans la table (accès dispersé) Index-only scan si l'index contient déjà les colonnes demandées 3 ou 4 niveaux suffisent pour des millions de lignes : la profondeur croît de façon logarithmique.
Les feuilles sont triées et chaînées : c'est ce qui rend un B-tree utile non seulement pour l'égalité, mais aussi pour les intervalles, le 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 VACUUM soit passé).

Coût d'écriture

Chaque INSERT, UPDATE ou DELETE doit maintenir tous les index de la table. Dix index, c'est dix arbres à mettre à jour à chaque écriture.

Lire l'explication détaillée et faire le quiz →

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.