Les index – B-tree et Hash

Bonne lecture et bon apprentissage !
Junior TSAFACK – 20/08/2026
⏱️ Temps de lecture estimé : 10 minutes

---

Les index sont l’un des outils les plus puissants pour améliorer les performances d’une base de données. Ils permettent d’accélérer les recherches en évitant des parcours complets de tables (full table scan). PostgreSQL propose plusieurs types d’index : B-tree (par défaut), Hash, GiST, GIN, BRIN et d’autres via extensions. Ce cours se concentre sur les deux plus courants : B-tree et Hash.

---

Pourquoi utiliser un index ?

Sans index, une requête SELECT * FROM table WHERE id = 1555555 doit parcourir toutes les lignes de la table pour trouver la bonne. Avec un index, PostgreSQL utilise une structure de données optimisée pour accéder directement à la ligne recherchée.

Les bénéfices

• Vitesse de lecture : les requêtes de recherche deviennent quasi instantanées.
• Gain sur les jointures : les clés étrangères indexées accélèrent les JOIN.
• Tri et regroupement : un index peut éviter un tri explicite (ORDER BY).

Les inconvénients

• Espace disque : un index occupe de la place (parfois plus que la table elle-même).
• Ralentissement en écriture : chaque INSERT, UPDATE ou DELETE doit mettre à jour l’index.
• Maintenance : les index peuvent se fragmenter et nécessiter un REINDEX.

💡 Règle d’or : Un index est utile quand on recherche peu de lignes dans une grande table. Il est inutile sur une table de quelques centaines de lignes, ou si la requête retourne plus de 10 % des lignes.

---

Les types d’index dans PostgreSQL

PostgreSQL propose plusieurs types d’index, chacun adapté à des cas d’usage spécifiques：

Type	Cas d’usage principal	Opérateurs supportés
B-tree	Égalité, inégalité, tri, plages	=, <, <=, >, >=, BETWEEN, LIKE (sans wildcard au début)
Hash	Égalité stricte uniquement	=
GiST	Données géospatiales, plein texte, recherche par similarité	<<, &<, &>, >>, @>, <@, &&
GIN	Recherche plein texte, tableaux, JSON	@>, ?, `?
BRIN	Très grandes tables avec données naturellement ordonnées	=, <, <=, >, >=

💡 Bon à savoir : Par défaut, PostgreSQL crée un index B-tree si vous ne spécifiez pas USING.

---

1. L’index B-tree

Principe de fonctionnement

Le B-tree (Balanced Tree) est une structure de données en arbre équilibré. Il a été inventé par Rudolf Bayer, qui travaillait chez Boeing.

Principe :

• L’arbre est inversé : la racine est en haut, les feuilles en bas.
• Chaque nœud contient des clés (valeurs) et des pointeurs vers les nœuds enfants.
• La recherche s’effectue en logarithmique (O(log n)), ce qui est extrêmement rapide même pour des millions de lignes.

Exemple d’arbre B-tree (valeurs 1 à 10) :

                        +---------------+
                        | 4     | 9     |   ← Nœud racine
                        +---------------+
                       /         |         \
                      /          |          \
            +---------+    +-------------+    +-------+
            | 1 | 3   |    | 5 | 6 | 8   |    | 10   |
            +---------+    +-------------+    +-------+
               /   \            /   \
              /     \          /     \
          +----+  +----+    +----+  +----+
          | 2  |  |    |    | 7  |  |    |
          +----+  +----+    +----+  +----+

Pour chercher la valeur 7 :

1. À la racine, 7 > 4 et 7 < 9 → on va au nœud du milieu.
2. Dans le nœud du milieu, 7 > 5 et 7 < 8 → on va à la feuille de droite.
3. On trouve 7.

Complexité : O(log n). Pour 1 million de lignes, il suffit d’environ 20 comparaisons.

Création d’un index B-tree

La syntaxe est simple :

CREATE INDEX idx_nom ON table (colonne);

Ou de manière explicite :

CREATE INDEX idx_nom ON table USING BTREE (colonne);

Exemple pratique

Créons une table de 2 millions de lignes et testons l’impact d’un index B-tree.

-- Créer une table
CREATE TABLE test_btree (id INT);

-- Insérer 2 millions de lignes
INSERT INTO test_btree SELECT * FROM generate_series(1, 2000000);

-- Activer l'affichage des temps
\timing

-- Requête sans index
SELECT * FROM test_btree WHERE id = 1555555;
-- Temps : environ 200-300 ms (varie selon le matériel)

-- Analyser le plan d'exécution
EXPLAIN ANALYZE SELECT * FROM test_btree WHERE id = 1555555;
-- Résultat : Seq Scan sur test_btree (parcours séquentiel de la table)

Création de l’index :

CREATE INDEX idx_test_btree_id ON test_btree (id);
-- Temps : environ 1-2 secondes

-- Requête avec index
SELECT * FROM test_btree WHERE id = 1555555;
-- Temps : environ 0.1 ms (2000 fois plus rapide !)

-- Analyser le plan d'exécution
EXPLAIN ANALYZE SELECT * FROM test_btree WHERE id = 1555555;
-- Résultat : Index Scan using idx_test_btree_id sur test_btree

Comparaison des performances :

Type de recherche	Temps d’exécution	Plan d’exécution
Sans index	~250 ms	Seq Scan (parcours séquentiel)
Avec index B-tree	~0.1 ms	Index Scan

💡 Bon à savoir : La commande EXPLAIN ANALYZE exécute réellement la requête et affiche le plan d’exécution avec les temps réels. C’est l’outil indispensable pour diagnostiquer les performances.

Cas d’usage du B-tree

Les index B-tree sont polyvalents et adaptés à de nombreux scénarios :

• Recherche par égalité : WHERE id = 123
• Recherche par plage : WHERE prix BETWEEN 100 AND 200
• Recherche par inégalité : WHERE date > '2024-01-01'
• Tri : ORDER BY nom ASC (l’index évite un tri explicite)
• Recherche par préfixe : WHERE nom LIKE 'Dupont%' (mais pas %Dupont)

Index multi-colonnes (B-tree)

Un index peut porter sur plusieurs colonnes. L’ordre des colonnes est important.

-- Index sur deux colonnes
CREATE INDEX idx_clients_nom_ville ON clients (nom, ville);

-- Requêtes qui utilisent l'index
SELECT * FROM clients WHERE nom = 'Dupont' AND ville = 'Paris';  -- ✅ Utilise l'index
SELECT * FROM clients WHERE nom = 'Dupont';                      -- ✅ Utilise l'index (première colonne)
SELECT * FROM clients WHERE ville = 'Paris';                     -- ❌ N'utilise PAS l'index (seule la 2e colonne)

💡 Règle : Un index multi-colonnes est utilisé si la requête filtre sur la première colonne de l’index. Il peut aussi être utilisé sur les colonnes suivantes si la première est présente.

---

2. L’index Hash

Principe de fonctionnement

L’index Hash utilise une fonction de hachage qui transforme la valeur de la colonne en un entier (hash code). Cet entier détermine l’emplacement du pointeur vers la ligne correspondante.

Principe :

1. La colonne est passée dans une fonction de hachage.
2. Le résultat (un entier) est utilisé comme clé dans une table de hachage.
3. La table de hachage stocke les pointeurs vers les lignes de la table.

Exemple :

Table :
+-------+--------+
| Nom   | Valeur |
+-------+--------+
| Paul  | rouge  |
| Jean  | vert   |
| René  | bleu   |
+-------+--------+

Hachage :
hash('Paul') = 2
hash('Jean') = 3
hash('René') = 1

Index Hash :
+-------+----------+
| Clé   | Pointeur |
+-------+----------+
| 1     | René     |
| 2     | Paul     |
| 3     | Jean     |
+-------+----------+

Recherche de Paul :

1. Calcul du hash : hash('Paul') = 2
2. Recherche de la clé 2 dans l’index → pointeur vers Paul
3. Récupération de la ligne → rouge

Complexité : O(1) en moyenne (temps constant), ce qui est encore plus rapide que le B-tree pour les recherches par égalité.

Création d’un index Hash

CREATE INDEX idx_nom ON table USING HASH (colonne);

Exemple pratique

-- Créer une table
CREATE TABLE test_hash (id INT);

-- Insérer 2 millions de lignes
INSERT INTO test_hash SELECT * FROM generate_series(1, 2000000);

-- Créer un index Hash
CREATE INDEX idx_test_hash_id ON test_hash USING HASH (id);

-- Requête avec index Hash
EXPLAIN ANALYZE SELECT * FROM test_hash WHERE id = 1555555;
-- Résultat : Index Scan using idx_test_hash_id sur test_hash

Cas d’usage du Hash

Les index Hash sont spécialisés et ne supportent que l’opérateur =.

✅ Quand utiliser un Hash :

• Recherches exactes uniquement (WHERE colonne = valeur)
• Colonnes avec beaucoup de valeurs distinctes (forte cardinalité)
• Tables très volumineuses où les requêtes par égalité sont fréquentes
• Pas besoin de tri ou de recherche par plage

❌ Quand NE PAS utiliser un Hash :

• Recherches par plage (BETWEEN, >, <)
• Tris (ORDER BY)
• Recherches par motif (LIKE)
• Colonnes avec peu de valeurs distinctes (faible cardinalité)

Comparaison B-tree vs Hash

Critère	B-tree	Hash
Opérateurs supportés	=, <, <=, >, >=, BETWEEN, LIKE (préfixe)	= uniquement
Performance (égalité)	Très bonne (O(log n))	Excellente (O(1))
Performance (plage)	Excellente	Impossible
Tri (ORDER BY)	Supporté (évite un tri)	Non supporté
Taille	Variable, dépend des données	Généralement plus petit
Maintenance	Peut se fragmenter	Moins de fragmentation
Disponibilité	Disponible depuis toujours	WAL-logging depuis PostgreSQL 10 (fiable)

💡 Bon à savoir : Avant PostgreSQL 10, les index Hash n’étaient pas journalisés (non WAL-logged) et pouvaient être corrompus en cas de crash. Depuis la version 10, ils sont fiables et peuvent être utilisés en production.

---

Index sur expressions

PostgreSQL permet de créer des index sur des expressions (calculs) plutôt que sur une simple colonne.

-- Index sur la concaténation de deux colonnes (Hash)
CREATE INDEX idx_employes_nom_complet ON employes USING HASH ((prenom || ' ' || nom));

-- Requête qui utilise l'index
SELECT * FROM employes WHERE (prenom || ' ' || nom) = 'Jean Dupont';

-- Index sur une expression avec B-tree
CREATE INDEX idx_commande_annee ON commandes (EXTRACT(YEAR FROM date_commande));

-- Requête
SELECT * FROM commandes WHERE EXTRACT(YEAR FROM date_commande) = 2024;

---

Index partiels (Partial Index)

Un index partiel ne couvre qu’une partie des lignes d’une table, via une clause WHERE. Cela permet de réduire la taille de l’index et d’améliorer les performances.

-- Index uniquement sur les clients actifs
CREATE INDEX idx_clients_actifs_email ON clients (email) WHERE actif = true;

-- Requête qui utilise l'index partiel
SELECT * FROM clients WHERE actif = true AND email = '[email protected]';

---

Index uniques

Un index unique garantit l’unicité des valeurs dans la colonne (ou le groupe de colonnes). C’est la base des contraintes UNIQUE et PRIMARY KEY.

-- Index unique
CREATE UNIQUE INDEX idx_clients_email ON clients (email);

-- Tentative d'insertion d'un doublon
INSERT INTO clients (email) VALUES ('[email protected]');  -- ❌ Erreur : violation d'unicité

---

Index et NULL

Par défaut, les index B-tree incluent les valeurs NULL (regroupées en fin d’index). Les index Hash n’incluent pas les NULL.

-- Les NULL sont inclus dans l'index B-tree
CREATE INDEX idx_test_null ON test (colonne);
SELECT * FROM test WHERE colonne IS NULL;  -- ✅ Utilise l'index B-tree

---

Quand utiliser quel index ?

Scénario	Index recommandé
Recherches par égalité, plage, tri	B-tree (par défaut)
Recherches par égalité uniquement, très grande table	Hash
Recherche plein texte	GIN
Données géospatiales	GiST
Très grande table, données ordonnées (ex : dates)	BRIN
Colonne avec peu de valeurs distinctes	BRIN ou pas d’index

---

Synthèse des commandes

Action	Commande
Créer un index B-tree	CREATE INDEX idx ON table (col);
Créer un index Hash	CREATE INDEX idx ON table USING HASH (col);
Créer un index multi-colonnes	CREATE INDEX idx ON table (col1, col2);
Créer un index unique	CREATE UNIQUE INDEX idx ON table (col);
Créer un index partiel	CREATE INDEX idx ON table (col) WHERE condition;
Créer un index sur expression	CREATE INDEX idx ON table (EXPRESSION);
Supprimer un index	DROP INDEX idx;
Réindexer	REINDEX INDEX idx;
Analyser une requête	EXPLAIN ANALYZE SELECT ...;

---

Prochain chapitre

Vous maîtrisez maintenant les index B-tree et Hash. Dans le prochain cours, nous explorerons les autres types d’index : GIN, GiST et BRIN, et nous verrons comment choisir le bon index pour chaque situation.

👉 Cours 6 : Les index spécialisés – GIN, GiST et BRIN

---

Junior TSAFACK – 20/08/2026