3.4 Modélisations par des structures arborescentes
111
Fig. 3.36 Un arbre dont les
nœuds internes représentent
l’index d’une base de
données, et les feuilles
contiennent les données
3.4.7 Index dans les bases de données
Dans le contexte des bases de données, il est souvent nécessaire de gérer des
ensembles d’adresses, pointant sur des enregistrements. De plus, les données sont
stockées en mémoire secondaire, et l’unité de transfert est une page mémoire, qui a
une capacité fixe (c’est un paramètre du système). Tant que l’ensemble d’adresses
est de taille assez petite pour tenir sur une page, tout va bien ; mais comment faire
lorsque la page est pleine ? Plusieurs méthodes ont été proposées, qui sont en fait
des variantes de l’idée suivante :
Supposons que nous disposions d’une fonction de hachage σ , qui associe à chaque clé x
une chaîne de bits σ (x), i.e., un élément de {0, 1} ∞ . Construisons un arbre digital paginé
sur l’ensemble {σ (x)}. Les feuilles contiennent au plus b clés ; l’arbre privé des feuilles est
ce qui est souvent appelé l’index, ou le répertoire.
Les différentes variantes portent sur la structure physique retenue pour implémenter le répertoire, et donnent lieu à diverses appellations 27 ; cf. Fagin [75] pour
le hachage extensible, Litwin [165] pour le hachage virtuel, Larson [163] pour le
hachage dynamique, et surtout Flajolet [79] pour une mise en perspective, le lien
avec les structures arborescentes, et l’analyse générale (figure 3.36).
Un autre exemple très fréquemment rencontré en pratique est celui des arbresB+ (cf. par exemple l’article de synthèse de Comer [49]). Il s’agit simplement
d’arbres-B, dont les nœuds internes contiennent des clés qui ne servent qu’à diriger
la recherche, et où seules les feuilles contiennent les données, qui sont ici des articles
comprenant chacun une clé et un certain nombre d’autres champs.
Les paramètres pertinents pour analyser les performances de tous ces algorithmes
sont ici le temps d’accès, lié à la hauteur de l’arbre, la taille de l’index, i.e., le nombre
de nœuds internes de l’arbre, et le taux d’occupation de la mémoire secondaire,
mesure qui est donnée par le nombre de pages utilisées, i.e., par le nombre de
feuilles.
27 Le terme de « hachage dynamique » est maintenant employé de manière globale pour toutes ces
variantes.
111
Fig. 3.36 Un arbre dont les
nœuds internes représentent
l’index d’une base de
données, et les feuilles
contiennent les données
3.4.7 Index dans les bases de données
Dans le contexte des bases de données, il est souvent nécessaire de gérer des
ensembles d’adresses, pointant sur des enregistrements. De plus, les données sont
stockées en mémoire secondaire, et l’unité de transfert est une page mémoire, qui a
une capacité fixe (c’est un paramètre du système). Tant que l’ensemble d’adresses
est de taille assez petite pour tenir sur une page, tout va bien ; mais comment faire
lorsque la page est pleine ? Plusieurs méthodes ont été proposées, qui sont en fait
des variantes de l’idée suivante :
Supposons que nous disposions d’une fonction de hachage σ , qui associe à chaque clé x
une chaîne de bits σ (x), i.e., un élément de {0, 1} ∞ . Construisons un arbre digital paginé
sur l’ensemble {σ (x)}. Les feuilles contiennent au plus b clés ; l’arbre privé des feuilles est
ce qui est souvent appelé l’index, ou le répertoire.
Les différentes variantes portent sur la structure physique retenue pour implémenter le répertoire, et donnent lieu à diverses appellations 27 ; cf. Fagin [75] pour
le hachage extensible, Litwin [165] pour le hachage virtuel, Larson [163] pour le
hachage dynamique, et surtout Flajolet [79] pour une mise en perspective, le lien
avec les structures arborescentes, et l’analyse générale (figure 3.36).
Un autre exemple très fréquemment rencontré en pratique est celui des arbresB+ (cf. par exemple l’article de synthèse de Comer [49]). Il s’agit simplement
d’arbres-B, dont les nœuds internes contiennent des clés qui ne servent qu’à diriger
la recherche, et où seules les feuilles contiennent les données, qui sont ici des articles
comprenant chacun une clé et un certain nombre d’autres champs.
Les paramètres pertinents pour analyser les performances de tous ces algorithmes
sont ici le temps d’accès, lié à la hauteur de l’arbre, la taille de l’index, i.e., le nombre
de nœuds internes de l’arbre, et le taux d’occupation de la mémoire secondaire,
mesure qui est donnée par le nombre de pages utilisées, i.e., par le nombre de
feuilles.
27 Le terme de « hachage dynamique » est maintenant employé de manière globale pour toutes ces
variantes.