149
6.1 Principes de l’indexation
Figure 6.2 — Nœuds de l’index
Figure 6.3 — Plan d’exécution, seek et RID lookup
Vous voyez dans ce plan d’exécution que RID lookup coûte 57 % relativement au
coût total de la requête. Il s’agit donc d’une opération lourde, nous reviendrons sur
ce point. La recherche de chaque RID est exprimée par un opérateur de boucle
imbriquée (nested loop). Cela veut simplement dire que pour RID trouvé par le seek
de l’index, il devra se produire une recherche de RID dans la table heap. Un peu
comme les épreuves de l’émission télévisée « Intervilles ». Une équipe doit transporter des seaux d’eau à travers un parcours difficile, mais chaque participant ne peut
bien sûr transporter que deux seaux à la fois. Ils doivent donc constamment revenir
au point de départ pour prendre les seaux restants. C’est le nested loop : à chaque
apparition de nouveau match dans l’index, le moteur de requête « déréférence » le
pointeur RID et va chercher physiquement la ou les lignes dans la page de données.
Chaque niveau de l’index est une liste doublement liée entre les pages de ce
niveau. En d’autres termes, chaque page d’index contient les identifiants de la page