© Éditions Eyrolles
31
chapitre n° 1
Définition des données
d’un index est d’éviter de parcourir une table séquentiellement du premier enregistrement
jusqu’à celui visé (problème rencontré si c’est le Français nommé « Zidane » qu’on recherche
dans une table non indéxée de plus de soixante-six millions d’enregistrements…). Le principe
d’un index est l’association de l’adresse de chaque enregistrement avec la valeur des colonnes
indéxées.
Sans index et pour n enregistrements, le nombre moyen d’accès nécessaire pour trouver un
élément est égal à n/2. Avec un index, ce nombre tendra vers log(n) et augmentera donc bien
plus faiblement en fonction de la montée en charge des enregistrements. Si une table contient
1 000 enregistrements, alors l’usage d’un index accélérera l’accès d’un facteur 100 par rapport
à un accès séquentiel.
Arbres balancés
La figure suivante illustre un index sous la forme d’un arbre. Cet index est basé sur la colonne
nom de la table Pilote. Cette figure est caricaturale, car un index n’est pas un arbre binaire
(plus de deux liens peuvent partir d’un nœud). Dans cet exemple, trois accès à l’index seront
nécessaires pour adresser directement un pilote via son nom, au lieu d’en analyser huit au plus.
Un index est associé à une table et peut être défini sur une ou plusieurs colonnes (dites
« indéxées »). Une table peut « héberger » plusieurs index. Ils sont mis à jour automatiquement après rafraîchissement de la table (ajouts et suppressions d’enregistrements ou modification des colonnes indéxées). Un index peut être déclaré unique si on sait que les valeurs des
colonnes indéxées seront toujours uniques.
Figure 1-3 Index sur la colonne nom
ROWID
Pilote
ROWID brevet
nom
nbHVol
compa
A
PL-1
Amélie Sulpice
450
AF
B
PL-2
Thomas Sulpice
900
AF
C
PL-3
Paul Soutou
1000
SING
D
PL-4
Aurélia Ente
850
ALIB
E
PL-5
Agnès Bidal
500
SING
F
PL-6
Sylvie Payrissat
2500
SING
G
PL-7
Thierry Guibert
600
ALIB
H
PL-8
Cathy Castaings
400
AF
Index (nom)
E
F
A
D
C
B
H
G
nom < ’D’
nom ≥ ’D’
< ’Am’
≥ ’Am’
≥ ’B’
< ’B’
< ’Aj’
≥ ’Aj’
≥ ’T’
< ’T’
≥ ’Q’
≥ ’Thl’
< ’Q’
≥ ’Thl’
31
chapitre n° 1
Définition des données
d’un index est d’éviter de parcourir une table séquentiellement du premier enregistrement
jusqu’à celui visé (problème rencontré si c’est le Français nommé « Zidane » qu’on recherche
dans une table non indéxée de plus de soixante-six millions d’enregistrements…). Le principe
d’un index est l’association de l’adresse de chaque enregistrement avec la valeur des colonnes
indéxées.
Sans index et pour n enregistrements, le nombre moyen d’accès nécessaire pour trouver un
élément est égal à n/2. Avec un index, ce nombre tendra vers log(n) et augmentera donc bien
plus faiblement en fonction de la montée en charge des enregistrements. Si une table contient
1 000 enregistrements, alors l’usage d’un index accélérera l’accès d’un facteur 100 par rapport
à un accès séquentiel.
Arbres balancés
La figure suivante illustre un index sous la forme d’un arbre. Cet index est basé sur la colonne
nom de la table Pilote. Cette figure est caricaturale, car un index n’est pas un arbre binaire
(plus de deux liens peuvent partir d’un nœud). Dans cet exemple, trois accès à l’index seront
nécessaires pour adresser directement un pilote via son nom, au lieu d’en analyser huit au plus.
Un index est associé à une table et peut être défini sur une ou plusieurs colonnes (dites
« indéxées »). Une table peut « héberger » plusieurs index. Ils sont mis à jour automatiquement après rafraîchissement de la table (ajouts et suppressions d’enregistrements ou modification des colonnes indéxées). Un index peut être déclaré unique si on sait que les valeurs des
colonnes indéxées seront toujours uniques.
Figure 1-3 Index sur la colonne nom
ROWID
Pilote
ROWID brevet
nom
nbHVol
compa
A
PL-1
Amélie Sulpice
450
AF
B
PL-2
Thomas Sulpice
900
AF
C
PL-3
Paul Soutou
1000
SING
D
PL-4
Aurélia Ente
850
ALIB
E
PL-5
Agnès Bidal
500
SING
F
PL-6
Sylvie Payrissat
2500
SING
G
PL-7
Thierry Guibert
600
ALIB
H
PL-8
Cathy Castaings
400
AF
Index (nom)
E
F
A
D
C
B
H
G
nom < ’D’
nom ≥ ’D’
< ’Am’
≥ ’Am’
≥ ’B’
< ’B’
< ’Aj’
≥ ’Aj’
≥ ’T’
< ’T’
≥ ’Q’
≥ ’Thl’
< ’Q’
≥ ’Thl’