Index B-tree — chercher sans lire tout

Sans index, trouver une ligne dans une table de 10 millions de lignes prend des secondes. Avec un index B-tree bien placé : 4 lectures disque.

Quand une base de données exécute SELECT * FROM users WHERE email = 'alice@example.com' sans index, elle lit chaque ligne de la table de haut en bas — c'est un sequential scan. Sur 10 millions de lignes, ça prend plusieurs secondes. Avec un index B-tree sur email, le moteur fait 4 ou 5 lectures disque pour trouver la ligne — quelques microsecondes.

Pourquoi le B-tree et pas le hachage ?

Un index de hachage trouve une valeur exacte en O(1) — plus rapide qu'un B-tree pour = ?. Mais il ne peut pas faire de range scans (BETWEEN, >, <, ORDER BY) ni de recherches sur des préfixes. Le B-tree, lui, stocke les clés triées — les ranges et les tris sont naturels.

Simule ci-dessous la recherche dans un B-tree de hauteur 3 :

Structure interne du B+ tree

Les SGBDR n'utilisent pas vraiment un B-tree — ils utilisent un B+ tree, une variante où toutes les données sont dans les feuilles.

Le terme "B-tree" est souvent utilisé, mais les SGBDR modernes (PostgreSQL, MySQL InnoDB, SQLite) utilisent en réalité un B+ tree. La différence est importante.

B-tree vs B+ tree

Opérations du B+ tree

Recherche — O(log n)

Depuis la racine, comparer la clé cherchée avec les clés de séparation du nœud courant. Descendre dans le sous-arbre approprié. Répéter jusqu'à atteindre une feuille. Nombre de lectures disque = hauteur de l'arbre (chaque nœud = 1 page disque).

Insertion — O(log n) amorti

Trouver la feuille cible (comme une recherche). Insérer la clé dans la feuille. Si la feuille est pleine (dépassement) : la scinder en deux et propager la clé médiane vers le parent. Cette scission peut se propager jusqu'à la racine. Si la racine éclate : créer une nouvelle racine → hauteur de l'arbre augmente de 1.

Range scan — O(log n + k)

Trouver la première feuille (log n lectures). Puis parcourir la liste chaînée des feuilles pour récupérer les k valeurs suivantes (k lectures supplémentaires). C'est pourquoi le B+ tree excelle sur les BETWEEN, ORDER BY, et les curseurs.

HOT — Heap Only Tuple (PostgreSQL)

PostgreSQL utilise le MVCC : chaque UPDATE crée une nouvelle version de la ligne. Si cette nouvelle version tient dans la même page que l'ancienne et que la colonne indexée n'a pas changé, PostgreSQL peut créer un HOT update : seul le heap (la table) est modifié, pas l'index. La chaîne HOT est traversée à la lecture. Résultat : les UPDATE fréquents sur des colonnes non-indexées n'entraînent pas de maintenance d'index.

Index clustered, covering, partial

Un index B-tree n'est pas qu'une seule chose — clustered, non-clustered, covering, partial, fonctionnel : chaque variante répond à un besoin précis.

Tous les index B-tree ne se ressemblent pas. La distinction la plus importante est entre index clustered et non-clustered, car elle détermine si une requête peut se satisfaire uniquement de l'index ou si elle doit aller chercher la ligne dans le heap.

Clustered index — l'index qui EST la table

Index covering — éliminer le saut vers le heap

Un index est dit covering pour une requête si toutes les colonnes requises par la requête sont présentes dans l'index lui-même. Le moteur peut répondre en lisant uniquement les feuilles de l'index — pas de heap access.

-- Requête : ID + email uniquement
SELECT id, email FROM users WHERE email = 'alice@example.com';

-- Index couvrant pour cette requête :
CREATE INDEX idx_users_email_id ON users(email) INCLUDE (id);

-- PostgreSQL : INCLUDE ajoute des colonnes dans les feuilles sans les inclure dans l'arbre.
-- → Index-only scan possible si email + id sont tous les deux dans l'index.

Index partiel — indexer un sous-ensemble

Un index partiel porte une clause WHERE : il n'indexe que les lignes qui satisfont cette condition. Plus petit, plus rapide à maintenir.

-- Indexer uniquement les commandes non livrées (10% de la table)
CREATE INDEX idx_orders_pending ON orders(created_at)
WHERE status = 'pending';

-- Utilisé uniquement si la requête contient : WHERE status = 'pending'
-- Beaucoup plus petit qu'un index sur toutes les commandes.

Index fonctionnel — indexer une expression

-- Recherche insensible à la casse
CREATE INDEX idx_users_email_lower ON users(LOWER(email));

-- Utilisé par :
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';

-- Sans cet index, LOWER(email) désactive tout index sur email brut.

Index composite et la règle du préfixe gauche

Un index sur (a, b, c) est utilisé seulement si la requête commence par a — c'est la règle du préfixe gauche, et elle dicte l'ordre des colonnes.

Un index composite (sur plusieurs colonnes) est plus puissant qu'un index simple — mais seulement si les colonnes sont dans le bon ordre. La règle du préfixe gauche détermine quelles requêtes peuvent utiliser l'index.

La règle du préfixe gauche

Colonnes d'égalité avant les colonnes de range

Quand une requête a des filtres d'égalité et des filtres de range (>, <, BETWEEN), mets les colonnes d'égalité en premier dans l'index :

-- Requête fréquente
SELECT * FROM orders WHERE customer_id = 42 AND created_at > '2024-01-01';

-- ✓ Bon ordre : égalité d'abord, range ensuite
CREATE INDEX idx_orders_customer_date ON orders(customer_id, created_at);

-- ✗ Mauvais ordre : range d'abord bloque customer_id
CREATE INDEX idx_orders_date_customer ON orders(created_at, customer_id);
-- → customer_id ne peut pas être utilisé après le range sur created_at

Index Skip Scan (PostgreSQL 17+ / MySQL 8+)

Certaines versions récentes des SGBDR implémentent un Index Skip Scan : quand la colonne gauche a une faible cardinalité (peu de valeurs distinctes), le moteur peut simuler plusieurs recherches dans l'index, une par valeur possible de la colonne gauche, même si la requête ne filtre pas sur elle.

-- Index sur (gender, age). Requête sans filtre sur gender :
SELECT * FROM users WHERE age = 30;

-- Skip scan : équivaut à (gender='M' AND age=30) UNION (gender='F' AND age=30)
-- Efficace si gender a 2–10 valeurs distinctes.

Sélectivité et cardinalité

Un index n'est utile que si sa sélectivité est élevée — indexer une colonne booléenne n'accélère rien.

Un index ne sert à rien si sa sélectivité est mauvaise. La sélectivité mesure la proportion de lignes retournées par un prédicat — une sélectivité élevée (peu de lignes) justifie un index ; une sélectivité faible (beaucoup de lignes) ne l'amortit pas.

Cardinalité

La cardinalité d'une colonne est son nombre de valeurs distinctes. Elle prédit directement la sélectivité d'un filtre d'égalité : sélectivité ≈ 1 / cardinalité.

Le seuil de bascule

Le planificateur de requête choisit entre un index scan et un sequential scan en comparant leurs coûts estimés. En simplifiant :

coût_index_scan = hauteur_arbre * random_page_cost + k * random_page_cost
coût_seq_scan   = nb_pages * seq_page_cost

// PostgreSQL : random_page_cost = 4.0, seq_page_cost = 1.0 (défauts pour HDD)
// Sur SSD, mettre random_page_cost = 1.1 pour favoriser les index scans
SET random_page_cost = 1.1;

Le seuil typique : au-delà de ~10–20% des lignes, le seq scan est moins coûteux qu'un index scan avec heap fetch. C'est pour ça qu'un index sur is_active est ignoré pour WHERE is_active = true si 80% des lignes sont actives.

Le problème N+1

Charger 100 articles puis faire 100 requêtes pour leurs commentaires : c'est le problème N+1, le piège classique des ORM.

Tu viens de déployer une fonctionnalité qui affiche une liste d'articles avec leurs auteurs. Les requêtes prennent 800ms. Tu regardes les logs SQL et tu vois ça :

SELECT * FROM articles LIMIT 20;       -- 1 requête
SELECT * FROM users WHERE id = 1;     -- requête #1
SELECT * FROM users WHERE id = 7;     -- requête #2
SELECT * FROM users WHERE id = 2;     -- requête #3
...                                    -- 20 requêtes supplémentaires

21 requêtes pour afficher 20 articles. C'est le problème N+1 : 1 requête pour charger N objets, puis 1 requête par objet pour charger sa relation.

Comment ça arrive avec un ORM

Les ORM utilisent par défaut le lazy loading : les relations ne sont chargées que lorsqu'on y accède. C'est pratique, mais désastreux dans une boucle :

// PHP / Doctrine — N+1 classique
$articles = $em->getRepository(Article::class)->findAll(); // 1 requête

foreach ($articles as $article) {
    // Accès à la relation → Doctrine lance une requête SQL supplémentaire
    echo $article->getAuthor()->getName(); // N requêtes
}

// JavaScript / TypeORM — même piège
const articles = await Article.findAll(); // 1 requête
for (const article of articles) {
    const author = await article.author;  // N requêtes
}

Détecter le N+1

Simule le N+1 ci-dessous — compare le nombre de requêtes :

Eager loading, batch loading, DataLoader

Trois familles de solutions pour éliminer le N+1 : joindre en SQL, charger en lot, ou dédupliquer en couche applicative.

Trois approches pour résoudre le N+1. Elles ne s'excluent pas — en pratique on les combine.

1. Eager loading — le JOIN en SQL

Charger les relations dans la même requête SQL via un JOIN. C'est la solution la plus directe et la plus performante pour les relations simples.

-- SQL direct : 1 seule requête
SELECT a.*, u.name FROM articles a
JOIN users u ON u.id = a.author_id
LIMIT 20;

// Doctrine : eager loading via addSelect
$articles = $em->createQueryBuilder()
    ->select('a', 'u')              // addSelect('u') charge la relation
    ->from(Article::class, 'a')
    ->join('a.author', 'u')
    ->setMaxResults(20)
    ->getQuery()
    ->getResult();

// Désormais $article->getAuthor() ne déclenche pas de requête

2. Batch loading — IN (...)

Charger les N objets d'abord, collecter les IDs de la relation, puis charger toutes les relations en une seule requête avec WHERE id IN (...). Deux requêtes au total.

// Étape 1 : charger les articles
$articles = $articleRepo->findAll();

// Étape 2 : collecter les IDs auteurs
$authorIds = array_unique(array_map(
    fn($a) => $a->getAuthorId(),
    $articles
));

// Étape 3 : charger tous les auteurs en une requête
$authors = $userRepo->findBy(['id' => $authorIds]);
$authorMap = array_column($authors, null, 'id');

// Étape 4 : associer manuellement
foreach ($articles as $article) {
    $author = $authorMap[$article->getAuthorId()];
}

3. DataLoader / Deferred loading

Le patron DataLoader (popularisé par GraphQL) accumule les demandes de chargement de relation pendant une phase "collect", puis les résout en une seule requête batch à la fin du cycle. C'est la version automatique du batch loading.

// JavaScript — graphql/dataloader
const userLoader = new DataLoader(async (ids) => {
    const users = await User.findAll({ where: { id: ids } });
    return ids.map(id => users.find(u => u.id === id));
});

// Chaque appel à load() est mis en attente
const author = await userLoader.load(article.authorId);
// À la fin du tick : 1 seule requête SQL avec tous les IDs accumulés

Doctrine — fetchJoin vs batch-size

// Option 1 : fetchJoin (recommandé pour *-to-one)
->join('a.author', 'u')

// Option 2 : fetch="EXTRA_LAZY" + batch loading automatique
// Dans l'entité :
#[ORM\OneToMany(fetch: 'EXTRA_LAZY')]

// Option 3 : @ORM\Column avec fetch="EAGER" pour le chargement automatique
#[ORM\ManyToOne(fetch: 'EAGER')]
// → chargé dans le même SELECT via JOIN automatique

Lire EXPLAIN ANALYZE

EXPLAIN ANALYZE est le déboggueur du moteur SQL — il montre quels nœuds d'exécution sont choisis, combien de temps chacun prend, et pourquoi.

EXPLAIN ANALYZE exécute réellement la requête et affiche le plan d'exécution avec les coûts estimés ET les temps réels. C'est l'outil indispensable pour comprendre pourquoi une requête est lente.

Lire un plan d'exécution

EXPLAIN ANALYZE
  SELECT * FROM orders WHERE customer_id = 42 AND status = 'pending';

------------------------------------------------------------------------
 Index Scan using idx_orders_customer_status on orders
     (cost=0.43..8.45 rows=3 width=128) (actual time=0.032..0.041 rows=3 loops=1)
   Index Cond: ((customer_id = 42) AND (status = 'pending'))
 Planning Time: 0.12 ms
 Execution Time: 0.08 ms

Les types de scans

Diagnostiquer un plan lent

-- Signaux d'alerte dans EXPLAIN ANALYZE :

-- 1. Écart rows estimé vs réel
-- (cost=... rows=1000) mais (actual rows=50000) → stats obsolètes
-- → Solution : ANALYZE table_name;

-- 2. Seq Scan sur une grande table avec filtre
-- Seq Scan on orders (cost=0.00..45000.00 rows=10 ...) (actual rows=10)
-- → Index aurait été 1000x plus rapide pour rows=10 / 10 millions total
-- → Solution : CREATE INDEX ON orders(colonne_filtrée);

-- 3. Index Scan avec Filter coûteux
-- Index Cond: (a = 1)  Filter: (b = 2)  Rows Removed by Filter: 9990
-- → L'index est utilisé sur a mais b est filtré après → envisager (a, b)

-- 4. Hash Join au lieu de Nested Loop
-- Hash Join implique souvent un manque d'index sur la clé de jointure
-- → CREATE INDEX ON orders(customer_id);

Anti-patterns d'indexation

Trop d'index ralentit les écritures. Trop peu fait exploser les lectures. Entre les deux, une poignée d'erreurs récurrentes.

Les index ne sont pas gratuits. Chaque index alourdit les opérations INSERT, UPDATE, et DELETE (le B-tree doit être maintenu), et consomme de l'espace disque. Un index mal placé peut même ralentir les requêtes qu'il est censé accélérer.

Anti-pattern 1 — Index sur une colonne de faible cardinalité

-- ✗ Inutile : is_deleted est un booléen (2 valeurs)
CREATE INDEX idx_users_is_deleted ON users(is_deleted);
-- Le planificateur ignorera cet index sauf si une valeur est très rare

-- ✓ Correct si la plupart des enregistrements ont is_deleted = false :
CREATE INDEX idx_users_active ON users(id) WHERE is_deleted = false;
-- Index partiel : indexe seulement les lignes non-supprimées

Anti-pattern 2 — Clé étrangère sans index

En PostgreSQL, les clés étrangères ne créent PAS automatiquement un index sur la colonne référençante. Oublier cet index peut causer des seq scans massifs lors des JOINs ou des suppressions en cascade.

-- ✗ Manque fréquent : orders.customer_id sans index
ALTER TABLE orders ADD CONSTRAINT fk_customer
    FOREIGN KEY (customer_id) REFERENCES customers(id);
-- → JOIN orders o ON o.customer_id = c.id : seq scan sur orders

-- ✓ Toujours créer l'index en même temps
CREATE INDEX idx_orders_customer_id ON orders(customer_id);

Anti-pattern 3 — Trop d'index sur une table OLTP

Chaque INSERT dans une table avec N index déclenche N insertions dans N B-trees. Une table de commandes avec 15 index verra ses insertions 10× plus lentes qu'avec 3 index.

Anti-pattern 4 — LIKE '%abc' (préfixe non ancré)

-- ✓ Peut utiliser un index B-tree (préfixe ancré à gauche)
WHERE name LIKE 'abc%'

-- ✗ Ne peut PAS utiliser un index B-tree
WHERE name LIKE '%abc'   -- préfixe inconnu
WHERE name LIKE '%abc%'  -- sous-chaîne

-- ✓ Solution pour la recherche full-text : index GIN sur tsvector
CREATE INDEX idx_articles_search ON articles USING gin(to_tsvector('french', content));
WHERE to_tsvector('french', content) @@ to_tsquery('french', 'postgresql');

Anti-pattern 5 — Appliquer une fonction sur la colonne indexée

-- ✗ Désactive l'index sur email
WHERE LOWER(email) = 'alice@example.com'  -- index sur email ignoré

-- ✓ Solution A : index fonctionnel
CREATE INDEX idx_users_email_lower ON users(LOWER(email));

-- ✓ Solution B : stocker la valeur normalisée dans la colonne
-- Normaliser à l'insertion, indexer la colonne directement

Synthèse — checklist d'optimisation

Diagnostiquer une requête lente, choisir l'index, éliminer le N+1 : la procédure complète.

La checklist pratique pour diagnostiquer une requête lente et décider si un index aiderait.

Étape 1 — Mesurer avant d'optimiser

-- Toujours commencer par mesurer :
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
  SELECT ...votre_requête...;

-- Questions à se poser sur le résultat :
-- 1. Y a-t-il un Seq Scan sur une grande table ? (> 100k lignes)
-- 2. Les rows estimées sont-elles très différentes des rows réelles ?
-- 3. Y a-t-il un Filter avec beaucoup de "Rows Removed" ?
-- 4. Y a-t-il des Hash Join qu'un Index Scan remplacerait avantageusement ?

Étape 2 — Choisir l'index

Étape 3 — Vérifier le N+1

Maintenabilité des index

-- Index inutilisés depuis le dernier RESET STATS :
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

-- Tables avec le plus de bloat d'index :
SELECT relname, n_dead_tup, n_live_tup
FROM pg_stat_user_tables
ORDER BY n_dead_tup DESC;

-- Créer un index sans verrouiller la table (OLTP) :
CREATE INDEX CONCURRENTLY idx_orders_status ON orders(status);