4. Les composants de l'architecture d'un système de bases de données
141
un fichier grille à k dimensions, le système parcourt la graduation
pour déterminer l'intervalle où se trouve la valeur de chaque attribut
constituant la clé de recherche. Les intervalles ainsi connus
permettent d'accéder directement à une section précise de l'index
grille. Chaque cellule de l'index contient le numéro de la page où sont
stockés des enregistrements de données. Un deuxième accès à la page
de données indiquée permet finalement de savoir si la page contient
l'enregistrement de données recherché ou non.
Deux accès
garantis pour
rechercher un
enregistrement
Le principe des deux accès aux pages est garanti pour rechercher
un enregistrement de données quelconque dans un fichier grille. Plus
précisément, l'opération de recherche requiert au maximum deux
accès aux pages stockées dans la mémoire secondaire : le premier
pour atteindre la bonne section dans l'index grille, le second pour
accéder à la bonne page de données.
Un exemple de
recherche
Par exemple, la recherche de l'employé N
o E18 engagé en 1969,
se déroule de la manière suivante dans le fichier grille G4 à la
figure 4-13 : le numéro d'employé E18 est compris dans l'intervalle
E15 à E30, plus exactement dans la moitié droite du fichier grille.
L'année d’entrée en service 1969 est comprise entre 1960 et 1970 et se
trouve donc dans la moitié supérieure. En utilisant ces deux
indications sur la graduation, le système de bases de données effectue
un premier accès à l’index grille pour obtenir l'adresse de la page de
données. Un deuxième accès atteint cette page qui contient les
enregistrements de données recherchés, identifiés par les clés d'accès
(E18,1969) et (E24,1964).
Soutien efficace
aux requêtes
d’intervalle
Un fichier grille à k dimensions permet de traiter des
interrogations pour extraire soit un enregistrement de données
particulier, soit un ensemble d'enregistrements appartenant à un
domaine spécifique. Dans une requête singulière (point query, en
anglais), le résultat obtenu est un enregistrement de données identifié
par k clés d'accès. Il est possible de formuler une requête singulière
partielle en spécifiant seulement une partie de la clé. Une requête
d’intervalle (range query, en anglais) permet d'effectuer la recherche
sur un domaine particulier de chacune des k parties de la clé. Le
résultat comprend tous les enregistrements de données pour lesquels
les valeurs des attributs constituant la clé appartiennent aux domaines
141
un fichier grille à k dimensions, le système parcourt la graduation
pour déterminer l'intervalle où se trouve la valeur de chaque attribut
constituant la clé de recherche. Les intervalles ainsi connus
permettent d'accéder directement à une section précise de l'index
grille. Chaque cellule de l'index contient le numéro de la page où sont
stockés des enregistrements de données. Un deuxième accès à la page
de données indiquée permet finalement de savoir si la page contient
l'enregistrement de données recherché ou non.
Deux accès
garantis pour
rechercher un
enregistrement
Le principe des deux accès aux pages est garanti pour rechercher
un enregistrement de données quelconque dans un fichier grille. Plus
précisément, l'opération de recherche requiert au maximum deux
accès aux pages stockées dans la mémoire secondaire : le premier
pour atteindre la bonne section dans l'index grille, le second pour
accéder à la bonne page de données.
Un exemple de
recherche
Par exemple, la recherche de l'employé N
o E18 engagé en 1969,
se déroule de la manière suivante dans le fichier grille G4 à la
figure 4-13 : le numéro d'employé E18 est compris dans l'intervalle
E15 à E30, plus exactement dans la moitié droite du fichier grille.
L'année d’entrée en service 1969 est comprise entre 1960 et 1970 et se
trouve donc dans la moitié supérieure. En utilisant ces deux
indications sur la graduation, le système de bases de données effectue
un premier accès à l’index grille pour obtenir l'adresse de la page de
données. Un deuxième accès atteint cette page qui contient les
enregistrements de données recherchés, identifiés par les clés d'accès
(E18,1969) et (E24,1964).
Soutien efficace
aux requêtes
d’intervalle
Un fichier grille à k dimensions permet de traiter des
interrogations pour extraire soit un enregistrement de données
particulier, soit un ensemble d'enregistrements appartenant à un
domaine spécifique. Dans une requête singulière (point query, en
anglais), le résultat obtenu est un enregistrement de données identifié
par k clés d'accès. Il est possible de formuler une requête singulière
partielle en spécifiant seulement une partie de la clé. Une requête
d’intervalle (range query, en anglais) permet d'effectuer la recherche
sur un domaine particulier de chacune des k parties de la clé. Le
résultat comprend tous les enregistrements de données pour lesquels
les valeurs des attributs constituant la clé appartiennent aux domaines