Principes de fonctionnement des index : structure de données et algorithmes de recherche

Aujourd'hui, on va plonger un peu plus dans l'architecture des index et voir comment ça marche vraiment sous le capot. Parce que comprendre comment un index est foutu, ça aide non seulement à piger pourquoi les requêtes vont plus vite, mais aussi à choisir les bons index pour chaque cas.

Quand on parle de la structure d'un index, c'est la façon dont les données sont organisées à l'intérieur de l'index pour permettre une recherche rapide. Imagine un placard avec des documents. Si les docs sont juste empilés en vrac, pour trouver le bon, c'est galère. Mais si le placard est rangé par ordre alphabétique, la recherche devient carrément plus simple. Les index, c'est pareil : ils rangent les données pour que tu puisses trouver ce que tu veux super vite.

Structure de l’index B-TREE

B-TREE (balanced tree — arbre équilibré) c’est le type d’index le plus utilisé dans PostgreSQL. En gros, c’est une structure en arbre où les données sont organisées en nœuds, et la recherche se fait en naviguant de la racine de l’arbre jusqu’aux feuilles.

À quoi ça ressemble :

         Racine
          /       |       \
      Noeud 1    Noeud 2    Noeud 3
     /   \       |       /   \
Feuille1 Feuille2   Feuille3  Feuille4 Feuille5

Chaque nœud contient des valeurs-clés qui servent à orienter la recherche. Par exemple, si le nœud racine contient les valeurs [10, 20, 30], alors :

• Toutes les données inférieures à 10 sont dans Feuille 1.
• Toutes les données entre 10 et 20 — dans Feuille 2, etc.

Avantages de l’index B-TREE :

• Recherche rapide des données : la complexité de recherche est O(log n), donc bien plus rapide qu’une recherche linéaire.
• Parfait pour les recherches sur des intervalles (genre, trouver toutes les valeurs entre 10 et 50).

Exemple : imagine qu’on a une table students avec une colonne age. Quand on crée un index B-TREE sur cette colonne :

CREATE INDEX age_idx ON students (age);

PostgreSQL crée un arbre équilibré pour les valeurs d’âge, ce qui permet de trouver rapidement les étudiants d’un certain âge ou d’une tranche d’âges.

Algorithme de recherche dans un B-TREE

Quand tu fais une requête, PostgreSQL utilise l’index pour chercher les données comme ça :

1. Il détermine la clé de recherche (par exemple, âge 25).
2. Il commence à la racine.
3. Il compare la clé avec les intervalles de valeurs du nœud et va dans le nœud enfant correspondant.
4. Il répète l’étape 3 jusqu’à arriver à une feuille.
5. Il renvoie les données de la feuille qui correspondent à la clé.

Exemple de requête :

SELECT * FROM students WHERE age = 25;

L’index réduit le nombre de données à scanner, ce qui rend la recherche super rapide.

Algorithmes de recherche et performance

Les index accélèrent la recherche en réduisant le nombre de lignes à parcourir. Sans index, PostgreSQL scanne toute la table (ça s’appelle un scan séquentiel, ou Seq Scan). Avec un index, il fait un scan par index (Index Scan), ce qui est bien plus rapide.

Comparaison entre scan séquentiel et scan par index

• Scan séquentiel (Seq Scan) :

  • PostgreSQL lit chaque ligne de la table, vérifie les conditions de la requête et renvoie les lignes qui matchent.
  • Utilisé s’il n’y a pas d’index ou si la requête touche presque toutes les lignes de la table.

• Scan par index (Index Scan) :

  • PostgreSQL utilise l’index pour trouver les lignes correspondantes, puis va chercher les données dans la table juste pour celles-là.
  • Beaucoup plus rapide sur les grosses tables si la requête ne concerne qu’un petit échantillon de données.

Exemple : sans index, recherche des âges

SELECT * FROM students WHERE age = 25;

le résultat peut demander de lire 1 million de lignes. Avec un index B-TREE, le système, par exemple, ne lit que 100 lignes.

Impact de la structure de l’index sur la performance

Les index sont plus rapides parce qu’ils réduisent la quantité de données à scanner. Par exemple, si la table a des millions de lignes, l’index les organise pour que la requête n’ait à lire que quelques nœuds au lieu de toute la table.

C’est super important de comprendre la structure de l’index. Savoir comment les index marchent, ça aide à piger pourquoi certaines requêtes sont lentes et comment les accélérer.

En plus, il faut savoir quels index utiliser. Pour les recherches sur des intervalles, B-TREE est top. Pour les arrays ou JSONB — GIN. Un mauvais choix d’index peut ralentir la base.

Exemples concrets

Voyons comment les index nous aident au quotidien.

Index pour le tri

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Avec un index B-TREE, PostgreSQL peut renvoyer les données triées direct depuis l’index, sans tri supplémentaire.

Index pour les intervalles

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

L’index B-TREE permet de trouver rapidement les lignes qui sont dans la plage demandée.

Questions fréquentes et pièges à éviter

Pourquoi il ne faut pas toujours utiliser des index ? Les index prennent de la place sur le disque et ralentissent les opérations d’insertion, de mise à jour et de suppression, parce qu’il faut mettre à jour la structure de l’index. Donc il vaut mieux créer des index seulement sur les colonnes souvent utilisées.

Quand les index ne servent à rien ? Pour les requêtes qui touchent la majeure partie de la table (genre WHERE true), PostgreSQL va préférer le Seq Scan, parce que lire les nœuds de l’index n’apporte rien.