4. Les composants de l'architecture d'un système de bases de données
139
Une importante structure de données multidimensionnelle
s'appelle fichier grille (grid file, en anglais).
Fichier grille
Définition du fichier
grille
Un fichier grille est une structure de données
multidimensionnelle qui possède les propriétés suivantes :
„ elle permet l'accès à partir d'une clé multidimensionnelle de
manière symétrique, en ce sens qu'aucune dimension n'est
dominante ;
„ elle permet de lire un enregistrement de données quelconque
après deux accès, le premier pour atteindre un index grille, le
deuxième pour atteindre la page de données recherchée.
Index grille
Un fichier grille consiste en un index grille et un fichier
contenant des pages de données. L'index grille représente un espace
multidimensionnel où chaque dimension correspond à une partie de la
clé d'accès multidimensionnelle. Pour insérer des enregistrements de
données, l'index est subdivisé en cellules dans chaque dimension en
alternance. À la figure 4-13, dans l'exemple avec une clé d'accès
bidimensionnelle, l'éclatement des cellules se fait alternativement
selon le numéro d'employé et l'année d'entrée en service. Les points
de subdivision ainsi obtenus dans chaque dimension constituent la
graduation de l'index grille.
Chaque cellule de l'index grille correspond à une page de
données et contient au moins n mais au plus 2*n entrées. Les cellules
vides de l’index grille doivent être fusionnées en cellules plus grandes
afin que les pages de données associées contiennent le minimum
d'entrées requis. Comme dans le précédent exemple illustrant la
méthode de la division, nous admettons de nouveau que chaque page
de données contient au maximum quatre entrées (n = 2).