Bases de données avancées
Mehdi Haddad
[email protected]
2024 - 2025
1
Traitement d’une requête
2
Index
I Quand une table est volumineuse, un parcours séquentiel
est une opération relativement lente et pénalisante pour
l’exécution des requête.
I En particulier dans le cas des jointures où ce parcours
séquentiel doit parfois être effectué répétitivement.
I La création d’un index permet d’améliorer
considérablement les temps de réponse en créant des
chemins d’accès aux enregistrements beaucoup plus directs.
3
Index
I L’utilisation d’index
I accélère l’exécution des sélections et des jointures
I ralentit l’exécution des mises à jour et des insertions
I offre des informations statistiques à l’optimiseur
I permet le contrôle efficace de contraintes d’intégrité
I Le choix des "bons" index et l’organisation des données
sont déterminants pour les performances
4
Index
I Une fois créés les index sont automatiquement utilisés et
actualisés par le SGBD :
I utilisés lors des recherches si une clé d’index est mentionnée
dans la clause WHERE d’une requête ;
I actualisés à chaque mise à jour (INSERT, UPDATE,
DELETE).
I La présence ou l’absence d’un index est complètement
transparente pour l’application ; c’est le SGBD qui utilise
(ou non) les index automatiquement.
I La maintenance des index dégrade les performances des
mises à jour.
5
Index : principe
6
Index : principe
7
Index : principe
8
Importance
I Un index permet de localiser des enregistrements sans avoir
à parcourir toute la table.
I Structure de données utilisées par les index
I Balenced Tree (B tree)
I Peut être utilisée pour les tests d’égalité ou de comparaison.
I Temps d’exécution logarithmique.
I Hash tables
I Peut être utilisée uniquement pour les tests d’égalité.
I Temps d’exécution "quasi" constant.
9
Structure d’un index B-tree
I Les données sont stockées dans des blocs Oracle.
I Les blocs branches (branch blocks) contiennent des données
qui pointent vers des blocs de niveau inférieur. Les blocs
branches permettent d’assurer un aiguillage d’un bloc
racine vers les blocs feuilles, en éliminant des branches à
chaque niveau.
I Les blocs feuilles (leaf blocks) contiennent les différentes
valeurs de la clé d’index avec les ROWID des lignes de la
table correspondante. Pour un index unique, il existe un
seul ROWID par valeur de clé ; pour un index non unique,
plusieurs ROWID sont possibles pour chaque valeur de clé.
Les blocs feuilles pointent vers les lignes de la table.
10
Structure d’un index B-tree
11
Structure d’un index B-tree
I Lorsque l’index est utilisé pour rechercher une valeur de clé.
I Le bloc racine est lu, puis le bloc feuille de niveau inférieur
correspondant à la branche qui contient la valeur de clé est
lu à son tour, et ainsi de suite jusqu’au bloc feuille qui
contient la valeur de clé ; associé à cette valeur de clé,
Oracle va trouver le(s) ROWID(s) de la ou les lignes qui
contiennent la valeur de la clé et pouvoir ainsi les lire
directement dans la table.
I Les blocs feuilles sont doublement chaînés pour faciliter le
parcours de l’index.
I Les valeurs de clé NULL ne sont pas présentes dans l’index.
I Dans les blocs feuilles d’un index non unique, les données
sont triées sur la clé puis sur le ROWID ; la valeur de la clé
est répétée à chaque fois.
12
Avantages des index B-tree
I L’index améliore la performance des requêtes (SELECT,
UPDATE et DELETE) qui utilisent la clé de l’index dans
la clause WHERE.
I L’arbre est maintenu équilibré par Oracle. Dans "B-tree",
"B" signifie balanced (balancé), c’est-à-dire qu’Oracle
s’arrange pour maintenir son arbre équilibré au fur et à
mesure des mises à jour de l’index. Pour cela, Oracle peut
couper des blocs en cas de besoin (notion de split).
I En conséquence, toutes les valeurs de la clé dans les blocs
feuilles sont situées à la même profondeur de l’arbre et sont
donc accessibles en parcourant le même nombre de blocs.
La recherche de n’importe quelle valeur de clé prend
toujours à peu près le même temps.
13
Inconvénients des index B-tree
I Le premier inconvénient d’un index est qu’il nécessite un
volume de stockage important.
I Le second inconvénient d’un index est qu’il dégrade les
performances des mises à jour.
I Pour des mises à jour unitaires, cela ne devient sensible que
si la table comprend un grand nombre d’index ; pour une
mise à jour massive, cette dégradation est sensible dès
l’existence du premier index.
I Ces deux inconvénients sont deux bonnes raisons pour ne
pas indexer toutes les colonnes d’une table.
14
Directives pour la création des index B-tree
I Les colonnes candidates à l’indexation sont les colonnes
fréquemment présentes dans les clauses WHERE, comme
critère de sélection ou de jointure.
I En complément, il faut s’assurer que les requêtes
correspondantes sont sélectives et ramènent moins de 5 à
10 % des lignes de la table.
I Cela implique donc que les valeurs de la colonne soient
relativement uniques (beaucoup de valeurs distinctes) et
que les conditions qui les utilisent soient elles-mêmes
sélectives. Il ne faut donc pas indexer les colonnes ayant
peu de valeurs distinctes (la colonne sexe par exemple).
I Il est inutile d’indexer les petites tables.
15
Directives pour la création des index B-tree
I Pour trouver les bonnes colonnes candidates à l’indexation,
il faut analyser les requêtes SELECT, UPDATE et
DELETE et rechercher les colonnes les plus fréquemment
utilisées dans les clauses WHERE (critère de sélection et
jointure).
I La performance d’un index dépend de sa sélectivité
intrinsèque et de la sélectivité des requêtes qui l’utilisent.
I La sélectivité peut être définie comme, le nombre moyen de
lignes ramenées par une requête divisé par le nombre total
de lignes.
16
Exemple sélectivité
I Prenons l’exemple de la table ADHERENT comprenant
100 000 personnes avec une répartition homogène
homme/femme. Considérons les clauses WHERE
suivantes :
I Ces exemples montrent que la colonne NUMERO est
intrinsèquement sélective mais que certaines requêtes
basées sur cette colonne peuvent ne pas l’être ; par contre,
la colonne SEXE n’est pas intrinsèquement sélective.
17
Sélectivité
I Une colonne ayant peu de valeurs distinctes est
intrinsèquement non sélective. Parmi les colonnes
candidates à l’indexation, il faut donc identifier celles qui
sont intrinsèquement sélectives et utilisées dans des
requêtes elles-mêmes sélectives
I Une colonne sera effectivement une bonne candidate à
l’indexation si la sélectivité (de la colonne et des requêtes
qui l’utilisent) est inférieure à environ 5 à 10 %. Dans les
grandes lignes, si une requête utilisant un index ramène
plus de 10 % des lignes.
18
Index composé
I Un index composé est un index portant sur plusieurs
colonnes.
I Parmi les colonnes candidates, il faudra d’abord identifier
les colonnes qui sont systématiquement présentes ensembles
dans la clause WHERE : ce sont de bonnes candidates à la
création d’un index composé qui est généralement plus
sélectif qu’un index simple.
I En effet, si les colonnes C1 et C2 d’une table sont
fréquemment utilisées ensemble dans les clauses WHERE et
qu’il existe 10 valeurs distinctes pour C1 (sélectivité de 10
%) et 10 valeurs distinctes pour C2 (sélectivité de 10 %), la
sélectivité théorique du couple (C1,C2) est de 1 % (dans
l’hypothèse où il n’y a pas de corrélation entre C1 et C2).
19
Index composé
I L’ordre des colonnes est important dans un index composé.
Un index composé est utilisé si les colonnes de tête de la clé
d’index sont présentes dans la condition.
I Si un index composé existe sur les colonnes
(NOM,PRENOM) de la table ADHERENT, les trois
requêtes suivantes utilisent l’index :
SELECT * FROM adherent
WHERE nom = ... AND prenom =...;
SELECT * FROM adherent
WHERE prenom = ... AND nom =...;
SELECT * FROM adherent
WHERE nom = ...;
I Par contre, la requête suivante n’utilise pas l’index :
SELECT * FROM adherent
WHERE prenom = ...;
20
