Indexation

DéfinitionIndex

Un index est une structure de données qui permet d'accélérer les recherches dans une table en associant à une clé d'index (la liste des attributs indexés) l'emplacement physique de l'enregistrement sur le disque.

Les accès effectuées sur un index peuvent donc se faire sur des structures optimisées pour la recherche (liste triée, B-tree...) au lieu de se faire par parcours séquentiel et intégral des enregistrements.

Exemple

Exemple de construction d'un B-tree

MéthodeCas d'usage des index de type B-Tree

Les index doivent être utilisés sur les tables qui sont fréquemment soumises à des recherches. Ils sont d'autant plus pertinents que les requêtes sélectionnent un petit nombre d'enregistrements (moins de 25% par exemple).

Les index doivent être utilisés sur les attributs :

  • souvent mobilisés dans une restriction (donc une jointure)

  • très discriminés (c'est à dire pour lesquels peu d'enregistrements ont les mêmes valeurs)

  • rarement modifiés

AttentionInconvénients des index

  • Les index diminuent les performances en mise à jour (puisqu'il faut mettre à jour les index en même temps que les données).

  • Les index ajoutent du volume à la base de données et leur volume peut devenir non négligeable.

SyntaxeCréer un index en SQL

1
CREATE INDEX nom_index ON nom_table (NomColonneClé1, NomColonneClé2, ...);

RemarqueIndex implicites

La plupart des SGBD[1] créent un index pour chaque clé (primaire ou candidate). En effet la vérification de la contrainte d'unicité à chaque mise à jour des données justifie à elle seule la présence de l'index.

AttentionAttributs indexés utilisés dans des fonctions

Lorsque les attributs sont utilisés dans des restrictions ou des tris par l'intermédiaire de fonctions, l'index n'est généralement pas pris en compte. L'opération ne sera alors pas optimisée. Ainsi par exemple dans le code suivant, le restriction sur X ne sera pas optimisée même s'il existe un index sur X.

1
SELECT *
2
FROM T
3
WHERE ABS(X) > 100

Cette non prise en compte de l'index est logique dans la mesure où, on le voit sur l'exemple précédent, une fois l'attribut soumis à une fonction, le classement dans l'index n'a plus forcément de sens (l'ordre des X, n'est pas l'ordre des valeurs absolues de X).

Lorsqu'un soucis d'optimisation se pose, on cherchera alors à sortir les attributs indexés des fonctions.

Notons que certains SGBD, tels qu'Oracle à partir de la version 8i, offrent des instructions d'indexation sur les fonctions qui permettent une gestion de l'optimisation dans ce cas particulier SQL2 SQL3, applications à Oracle[2].