116
Introduction pratique aux bases de données relationnelles
Utilité du parcours
d’un index
Si nous créons un index pour l'attribut A ou B, il est possible de
réduire le coût de la jointure par boucles imbriquées. L'index (index,
en anglais) d'un attribut est une structure d'accès qui, dans un ordre de
rangement déterminé, associe à chaque valeur de l'attribut une adresse
interne où l'enregistrement de données correspondant est stocké.
L'index est comparable à celui d'un livre : chaque mot-clé - imprimé
dans l'ordre alphabétique - est suivi du numéro de la page où il
apparaît dans l'ouvrage.
Les clés d’accès
sont définies par la
création d’index
À titre d'exemple nous décidons de doter la table EMPLOYÉ d'un
index sur l'attribut Nom. Le système de bases de données crée donc
cette structure d'index (voir 4.4) qui reste cependant cachée à
l'utilisateur. Chaque nom dans la table EMPLOYÉ, rangé par ordre
alphabétique dans l'index, est associé soit à la clé d'identification E#
soit à l'adresse interne du tuple de l'employé nommé. Le système de
bases de données utilise cet index des noms pour traiter une
interrogation ou une jointure impliquant la table EMPLOYÉ. Dans ce
contexte, l'attribut Nom est appelé la clé d'accès.
Les structures
d’index améliorent
la performance
Dans le calcul de la jointure en figure 4-4, l'attribut D# possède
aussi son propre index car le numéro de département est la clé
primaire
1 de la table DÉPARTEMENT. À chaque itération de la boucle
interne, le système de bases de données utilise la structure d’index du
numéro de département pour atteindre directement un département
recherché au lieu de parcourir toute la table DÉPARTEMENT de tuple à
tuple séquentiellement. Dans le meilleur des cas, l'attribut Affectation
de la table EMPLOYÉ comporte aussi un index que le système de bases
de données peut utiliser à des fins d’optimisation. Cet exemple nous
montre le rôle important de l'administrateur de bases de données dans
le choix des structures d'index appropriées.
Avantage des
attributs dont les
valeurs sont triées
Nous pouvons développer un algorithme plus performant que la
jointure par boucles imbriquées si les tuples contenus dans les tables
R et S se présentent en ordre croissant ou décroissant des valeurs des
1 Le système de bases de données crée automatiquement une structure d’index
pour chaque clé primaire ; des structures d'index étendues sont définies pour
les clés formées par la concaténation de plusieurs attributs.
Introduction pratique aux bases de données relationnelles
Utilité du parcours
d’un index
Si nous créons un index pour l'attribut A ou B, il est possible de
réduire le coût de la jointure par boucles imbriquées. L'index (index,
en anglais) d'un attribut est une structure d'accès qui, dans un ordre de
rangement déterminé, associe à chaque valeur de l'attribut une adresse
interne où l'enregistrement de données correspondant est stocké.
L'index est comparable à celui d'un livre : chaque mot-clé - imprimé
dans l'ordre alphabétique - est suivi du numéro de la page où il
apparaît dans l'ouvrage.
Les clés d’accès
sont définies par la
création d’index
À titre d'exemple nous décidons de doter la table EMPLOYÉ d'un
index sur l'attribut Nom. Le système de bases de données crée donc
cette structure d'index (voir 4.4) qui reste cependant cachée à
l'utilisateur. Chaque nom dans la table EMPLOYÉ, rangé par ordre
alphabétique dans l'index, est associé soit à la clé d'identification E#
soit à l'adresse interne du tuple de l'employé nommé. Le système de
bases de données utilise cet index des noms pour traiter une
interrogation ou une jointure impliquant la table EMPLOYÉ. Dans ce
contexte, l'attribut Nom est appelé la clé d'accès.
Les structures
d’index améliorent
la performance
Dans le calcul de la jointure en figure 4-4, l'attribut D# possède
aussi son propre index car le numéro de département est la clé
primaire
1 de la table DÉPARTEMENT. À chaque itération de la boucle
interne, le système de bases de données utilise la structure d’index du
numéro de département pour atteindre directement un département
recherché au lieu de parcourir toute la table DÉPARTEMENT de tuple à
tuple séquentiellement. Dans le meilleur des cas, l'attribut Affectation
de la table EMPLOYÉ comporte aussi un index que le système de bases
de données peut utiliser à des fins d’optimisation. Cet exemple nous
montre le rôle important de l'administrateur de bases de données dans
le choix des structures d'index appropriées.
Avantage des
attributs dont les
valeurs sont triées
Nous pouvons développer un algorithme plus performant que la
jointure par boucles imbriquées si les tuples contenus dans les tables
R et S se présentent en ordre croissant ou décroissant des valeurs des
1 Le système de bases de données crée automatiquement une structure d’index
pour chaque clé primaire ; des structures d'index étendues sont définies pour
les clés formées par la concaténation de plusieurs attributs.