# Concept

Un index permet d'optimiser la recherche dans une table sur une colonne. C'est l'amélioration de performance la plus classique.
Le SGBD peut faciliter la récupération d'enregistrements lorsqu'ils sont indexés, comme dans l'index d'un livre.

On pourrait être tenté de mettre des indexs sur toutes les colonnes, cependant ceux-ci demandent un certain travail au SGBD pour organiser les données, ce qui va avoir un impact à chaque opération d'écriture. Il faut alors sélectionner avec précaution les colonnes à indexer.

Il existe de nombreux types d'indexations mais l'analogie la plus facile à comprendre est l'arbre binaire de recherche (binary search tree):
Imaginons des enregistrements identifiés par des nombres entier. Ceux-ci peuvent être organisés sans tri:

12, 67, 29, 54, 80, 3, 48

Si on recherche l'élément n°80 en parcourant toute la liste du premier au dernier, il faudra 5 étapes pour retrouver le bon enregistrement.

En créant un arbre binaire de recherche, on va classer les enregistrements par ordre croissant et on démarrera la recherche au milieu de la liste: l'enregistrement n°48.

3, 12, 29, 48, 54, 67, 80

L'élément recherché (enregistrement n°80) est supérieur à celui trouvé (enregistrement n°48), on va donc recommencer en ne prenant que les éléments suivants:

54, 67, 80

L'enregistrement au centre de la liste restante est le n°67, il faut donc continuer en ne prenant que les suivants. Il ne reste plus que l'élément recherché.
Malgré le jeu de données très limité (7 enregistrements), nous sommes passés de 5 à 3 étapes pour retrouver un enregistrement.

# Utilisation d'un index

Partons d'une simple table d'utilisateurs:

CREATE TABLE utilisateur (
    id INT NOT NULL,
    pseudo VARCHAR (50) NOT NULL,
    PRIMARY KEY (id)
);

INSERT INTO utilisateur (id, pseudo) VALUES
(15, 'Antoine'),
(5, 'Julie'),
(43, 'Martin'),
(85, 'Laure'),
(54, 'Pedro'),
(94, 'Mathilde'),
(22, 'Charles'),
(61, 'Amanda'),
(74, 'Etienne'),
(64, 'Charline');

La définition d'une clé primaire constitue déjà une création implicite d'index, comme l'indique l'explication d'une requête de recherche par id:

EXPLAIN
SELECT *
FROM utilisateur
WHERE id = 64;

On peut voir que Postgres effectue un "index scan" et non un "sequential scan":

Index Scan using utilisateur_pkey on utilisateur (cost=0.15..8.17 rows=1 width=122)
Index Cond: (id = 64)

On crée ensuite un index sur la colonne pseudo:

CREATE INDEX idx_utilisateur_pseudo ON utilisateur (pseudo);

Lorsque le SGBD l'estimera nécessaire, il utilisera l'index pour optimiser l'exécution de certaines requêtes.

Note: l'utilisation de l'index n'est pas systématique si le SGBD estime qu'un "sequential scan" est plus performant.