BD et SGBD -- Les index

Index Tdm
Précédent Introduction
Go up to Stockage des données
Suivant Les clusters

Les index

Selon le modèle relationnel les sélections peuvent être faites en utilisant le contenu de n'importe quelle colonne et les lignes sont stockées dans n'importe quel ordre.

Considérons le SELECT suivant :


SELECT * 
FROM emp
WHERE nom = 'MARTIN'

Un moyen de retrouver la ou les lignes pour lesquelles nom est égal à MARTIN est de balayer toute la table. Un tel moyen d'accès conduit à des temps de réponse prohibitifs pour des tables dépassant quelques centaines de lignes. Une solution offerte par tous les systèmes de gestion de bases de données est la création d'index, qui permettra de satisfaire aux requêtes les plus fréquentes avec des temps de réponse acceptables.
Un index sera matérialisé par la création de blocs disque contenant des couples (valeurs d'index, numéro de bloc) donnant le numéro de bloc disque dans lequel se trouvent les lignes correspondant à chaque valeur d'index.

Utilisation des index

L'adjonction d'un index à une table ralentit les mises à jour (insertion, suppression, modification de la clé) mais accélère beaucoup la recherche d'une ligne dans la table.
L'index accélère la recherche d'une ligne à partir d'une valeur donnée de clé, mais aussi la recherche des lignes ayant une valeur d'index supérieure ou inférieure à une valeur donnée, car les valeurs de clés sont triées dans l'index.

Exemple : Les requêtes suivantes bénéficieront d'un index sur le champ n_dept.


SELECT * FROM emp WHERE num = 16034  ;
SELECT * FROM emp WHERE num >= 27234 ;
SELECT * FROM emp WHERE num BETWEEN 16034  AND 27234;

Un index est utilisable même si le critère de recherche est constitué seulement du début de la clé.

Exemple : La requête suivante bénéficiera d'un index sur la colonne nom.


SELECT * 
FROM emp
WHERE nom LIKE 'M

Par contre si le début de la clé n'est pas connu, l'index est inutilisable.

Exemple : La requête suivante ne bénéficiera pas d'un index sur le champ nom.


SELECT * 
FROM emp
WHERE ename LIKE '

Valeurs `NULL`

Elles ne sont pas représentées dans l'index, ceci afin de minimiser le volume nécessaire pour stocker l'index. En contrepartie, l'index ne sera d'aucune utilité pour retrouver les valeurs NULL lorsque le critère de recherche est du type IS NULL.

Conversions

L'index n'est utilisable que si le critère de sélection est le contenu de la colonne indexée, sans aucune transformation. Par exemple un index sur salaire ne sera pas utilisé pour la requête suivante :


SELECT * FROM emp
WHERE salaire * 12 > 300000 ;

Attention en particulier aux conversions de type qui peuvent empêcher l'utilisation de l'index.

sql est un langage typé, chaque type de données (numérique, caractère, date) ayant ses propres opérateurs, ses propres fonctions et sa propre relation d'ordre. En conséquence, si dans une expression, figurent à la fois un nombre et une chaîne de caractères, sql convertira la chaîne de caractères en nombre. De même si dans une expression, figurent à la fois une chaîne de caractères et une date, sql convertira la chaîne de caractères en date.

Or, dans un prédicat du type :


WHERE fonction(col_indexée) = constante

sql ne peut pas utiliser l'index.

Ceci peut se produire , de façon insidieuse, lorsque sql est obligé d'ajouter un appel à une fonction de conversion à cause d'une discordance de type.

Exemple : Le prédicat suivant ne bénéficiera pas d'un index sur le champ embauche.


SELECT * FROM emp
WHERE embauche LIKE '

En effet, sql est obligé d'effectuer une conversion, et le prédicat qui sera évalué est :


WHERE TO_CHAR(embauche) LIKE '

Le critère de recherche est une fonction de embauche, et non le champ embauche lui-même, dans ce cas l'index est inutilisable.

Choix des index

Indexer en priorité :

les clés primaires
les colonnes servant de critère de jointure
les colonnes servant souvent de critère de recherche

Ne pas indexer :

les colonnes contenant peu de valeurs distinctes (index alors peu efficace)
les colonnes fréquemment modifiées

Index comprimé et non comprimé

Les clés dans les index peuvent être comprimées ou non. La compression est une technique permettant de réduire dans des proportions très importantes (d'autant plus que la clé est longue) le volume de l'index.

En contrepartie, il faut parfois un traitement supplémentaire pour recomposer la clé lors des mises à jour de l'index.

Par défaut, les index sont comprimés, les avantages de réduction de taille l'emportant sur les inconvénients dans la plupart des cas.

sql sait exécuter certaines requêtes directement au niveau de l'index sans passer par le segment de données, si l'index est non comprimé et si tous les champs résultats de la requête sont dans l'index.

Exemple : L'index crée par :


CREATE INDEX x 
ON emp (num, nom)
nocompress ;

permettra de répondre à la question :


SELECT nom
FROM emp
WHERE num > 17217 ;

sans lire la table puisque toutes les informations se trouvent dans l'index et que l'index est non concaténé.

Index concatene

Un index concaténé est un index portant sur plusieurs colonnes.

Exemple :


CREATE INDEX xemp
ON (n_dept,num) ;

Les index concaténés peuvent être utilisés pour matérialiser une clé composée de plusieurs colonnes.

sql sait utiliser un index concaténé même si le critère de recherche ne porte pas sur toutes les colonnes présentes dans l'index.

Exemple : L'index ci-dessus est utilisable si l'on ne connait que le numéro de département.


SELECT nom
FROM emp
WHERE n_dept = 20 ;