Index (base de données)

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.

Sommaire

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 à \sqrt{n}, la racine carrée de n (la table étant alors composée de \sqrt{n} valeurs de hachage accédant chacune à \sqrt{n} 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 :

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

Voir aussi

Article connexe


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Index (base de données) de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Index (base de donnees) — Index (base de données) En informatique, et en particulier dans le contexte des bases de données, un index est un élément de redondance que l on va spécifier pour permettre au Système de Gestion de Base de Données d optimiser certaines requêtes.… …   Wikipédia en Français

  • Base De Données — Pour les articles homonymes, voir base, BD, BDD et DB. Schéma de la base de données relationnelle …   Wikipédia en Français

  • Base de donnees — Base de données Pour les articles homonymes, voir base, BD, BDD et DB. Schéma de la base de données relationnelle …   Wikipédia en Français

  • Base de données en ligne — Base de données Pour les articles homonymes, voir base, BD, BDD et DB. Schéma de la base de données relationnelle …   Wikipédia en Français

  • Base de donnees bibliographiques — Base de données bibliographiques Une base de données bibliographiques est une base de données qui contient des notices bibliographiques. Cette définition s applique à toute catégorie d objets bibliographiques : livres, collections, revues,… …   Wikipédia en Français

  • Base De Données Multimédia — Une base de données multimédia est un type de base de données consacré au stockage et à l organisation de données multimédia : documents sonores, images, vidéos. Elles peuvent s appuyer sur différentes architectures de bases de données, les… …   Wikipédia en Français

  • Base de donnees multimedia — Base de données multimédia Une base de données multimédia est un type de base de données consacré au stockage et à l organisation de données multimédia : documents sonores, images, vidéos. Elles peuvent s appuyer sur différentes… …   Wikipédia en Français

  • Base de données — Pour les articles homonymes, voir base, BD, BDD et DB. modèle de données de la base de données de MediaWiki …   Wikipédia en Français

  • Base de données bibliographiques — Les base de données bibliographiques répertorient toute catégorie d objets bibliographiques : livres, collections, revues, articles de revues etc. Elles sont le fruit de l informatisation des catalogues de bibliothèque, et permettent des… …   Wikipédia en Français

  • Base de données multimédia — Une base de données multimédia est un type de base de données consacré au stockage et à l organisation de données multimédia : documents sonores, images, vidéos. Elles peuvent s appuyer sur différentes architectures de bases de données, les… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”