Index (base de données)

En informatique, dans les bases de données, un index est une structure de données utilisée et entretenue par le système de gestion de base de données (SGBD) pour lui permettre de retrouver rapidement les données. L'utilisation d'un index simplifie et accélère les opérations de recherche, de tri, de jointure ou d'aggrégation effectuées par le SGBD.

l’index placé sur une table va permettre au SGBD d'accéder très rapidement aux enregistrements, selon la valeur d'un ou plusieurs champs.

Types d'index

• La structure la plus courante pour les indexes est l'arbre B (B-tree). En stockant les différentes valeurs du champ dans un arbre binaire, le SGBD pourra hiérarchiser les enregistrements d'après un champ dont la plage de valeurs est infinie (ou presque).
• Un autre type d'index est l'Index Bitmap. Il consiste en une simple table indiquant, pour chaque valeur possible du champ, la liste des enregistrements ayant cette valeur pour ce champ.

Cependant, pour être efficace, il nécessite que le SGBD puisse accéder directement à une valeur donnée. Il n'est donc applicable que sur les colonnes pour lesquelles le nombre de valeurs est limité et ordonné.

• On trouve également des index par table de hachage. L'inconvénient majeur d'un tel index est de ne permettre que les sélections par égalité, puisqu'il ne conserve pas la notion d'ordre. Si n est le nombre d'enregistrements d'une table, l'utilisation d'une table de hachage équilibrée peut permettre de réduire le nombre d'enregistrements à parcourir à , la racine carrée de n (la table étant alors composée de valeurs de hachage accédant chacune à enregistrements).

La même remarque sur l'efficacité existe pour l'index bitmap : le SGBD doit pouvoir accéder directement à une valeur de hachage donnée, sans avoir à parcourir la liste des valeurs de hachage possibles.

Rôle de l'index

Lors de la phase d'optimisation de la requête, le SGBD va déterminer le ou les index à utiliser afin d'en accélérer l'exécution.

Sélection (clause WHERE)

 SELECT *
 FROM table
 WHERE champ < 10

Sans index sur champ, la seule manière dont dispose le SGBD pour déterminer les enregistrements vérifiant la condition champ < 10 est de tester cette condition pour chaque enregistrement de la table.

Un index placé sur champ pourra être parcouru par le SGBD sur les valeurs inférieures à 10 (excepté dans une table de hachage, les valeurs sont ordonnées).

Jointures

 SELECT *
 FROM table1, table2
 WHERE table1.champ = table2.champ

Sans index, le SGBD est obligé de parcourir les deux tables pour faire la jointure (en pratique, il va charger quasiment les 2 tables en mémoire).

Avec un index sur table1.champ, le SGBD peut parcourir table2 et, pour chaque enregistrement, chercher les enregistrements de table1 qui correspondent.

Agrégation

La structure de l'index permet également de faciliter les tris et agrégations.

 SELECT *
 FROM table
 ORDER BY champ

Si table est indexée sur champ, il sera plus facile pour le SGBD de récupérer chaque enregistrement en suivant l'index, que de parcourir la table et la trier en mémoire (à chaque exécution de la requête)

 SELECT MIN(champ)
 FROM table
 ORDER BY champ

Si table est indexée sur champ, la valeur cherchée est la première entrée de l'index.

Construction de l'index

Un index peut :

• porter sur la valeur d'un champ, ou bien sur une fonction déterministe (dont la valeur de sortie ne dépend que de ses paramètres) sur la valeur d'un ou plusieurs champs.
• posséder une ou plusieurs dimensions (on parle alors d'index multi-colonnes).

Exemple

Imaginons une table Déclaration possédant les champs suivants

 N° sécu          // N° de sécurité sociale.
 Annee_naissance  // Année de naissance du contribuable
 Revenu           // Revenu 
 Frais Reel       // montant des frais réels

Pour l'exemple :

• le premier chiffre du n° de sécu désigne le sexe de l'individu
• Le revenu imposable est calculé :
  • soit en soustrayant les Frais réels au Revenu (si ceux-ci sont renseignés)
  • soit en effectuant un abattement forfaitaire de 10% sur le Revenu

On pourra par exemple créer (le langage utilisé est totalement fictif) :

• un index sur (N° sécu)

Exemple de requête utilisant l'index : Contribuable ayant N° sécu = 123456

• un index sur (Annee_naissance, Revenu)

Exemple de requête utilisant l'index : Contribuables nés avant 1980, avec un Revenu entre 20 000 et 30 000

Exemple de requête utilisant l'index : Revenu maximal selon l'année de naissance

• un index sur ( GAUCHE(N° sécu, 2) )
• un index bi-colonnes ( GAUCHE(N° sécu, 2), SI(Frais_Reel > 0 ALORS Revenu - Frais_Reel SINON Revenu*0.9) )

:qui permettra par exemple de renvoyer directement (sans avoir à faire de parcours, autre que celui de l'index) les femmes ayant un revenu imposable compris entre 10000 et 40000.

Ceci n'est qu'un exemple pour illustrer les possibilités d'index; en pratique, sur cet exemple :

• on préfèrera stocker le sexe plutôt que de décomposer le champ (notion d'atomicité)
• on utilisera une vue pour obtenir la valeur d'un champ calculé, et on indexera la vue (pour les SGBD qui le permettent)

Impacts sur les performances en modification

Lors de l'insertion ou de la mise à jour d'un enregistrement de la base, il y a une légère dégradation des performances : le SGBD doit en effet mettre à jour les index pour qu'ils continuent à refléter l'état des enregistrements. Pour cette raison, on s'attachera, lors de la conception d'une base de données, à définir uniquement les index qui seront utilisés par le système. Ceux-ci ne seront d'ailleurs bien repérés que par une analyse du système (et notamment des mécanismes d'interrogation de la base) en vue de son optimisation.

Autres formes d'indexation

D'autres types de structure offrent des fonctionnalités d'indexation :

• Tables clusterisées
• Vue matérialisée

Remarque sur les index multi-colonnes

Dans le cas d'un index multi-colonnes, le SGBD peut "décider" de l'utiliser partiellement, dans l'ordre des colonnes de l'index. En d'autres termes, un index sur des colonnes (c1,c2,c3,c4) peut être utilisé comme un index (c1,c2,c3), (c1,c2) ou (c1).

Liens externes

• Comment MySQL utilise les index

Voir aussi

Article connexe

• Index.dat (des fichiers qui permettent aux logiciels de Microsoft d'accéder rapidement à des informations enregistrées précédemment)

v · Bases de données
Principe mis en œuvre dans les bases relationnelles	Transaction · Opération de base · Clés et Index · Déclencheur · Jointure
Modèle de données	Structure de données · Intégrité des données · Langage de définition de données · Langage de requête
Les données	Table · Vue · Champ · Procédure stockée

• Portail de l’informatique