4. Les composants de l'architecture d'un système de bases de données
135
approprié (qui est ici une feuille) et continue sa recherche.
Finalement, il trouve l'entrée désirée dans la feuille choisie. Dans cet
exemple simple, le coût de recherche de la valeur de clé E15 équivaut
seulement à deux accès pour atteindre d'abord la page associée au
nœud racine et ensuite la page associée à une feuille.
La hauteur de
l’arbre détermine le
temps d’accès
La hauteur de l'arbre multiple détermine le temps d'accès à une
valeur de clé ainsi qu'aux données identifiées par cette valeur. Il est
possible de réduire le temps d'accès en augmentant le nombre de
valeurs de clé (degré de branchement) par nœud dans un arbre
multiple.
L’arbre B* est
orienté feuilles
Une autre méthode consiste à construire un arbre multiple
orienté feuilles (aussi connu sous le nom d'arbre B*). Dans cette
structure, les enregistrements de données ne sont jamais stockés dans
des nœuds intérieurs mais toujours dans les feuilles de l'arbre. Tous
les nœuds contiennent uniquement des valeurs de clé afin de réduire
le plus possible la profondeur de l'arbre.
4.4.2 Méthodes de hachage
Stockage utilisant
la technique
d’adressage
dispersé
Les méthodes de transformation de clés ou de calcul des adresses
(key hashing, ou simplement hashing, en anglais) constituent le
fondement des structures d'accès et de stockage aléatoire. Une
fonction de hachage (hash function, en anglais) permet de transformer
un ensemble de clés en un ensemble d'adresses qui forme un espace
d'adressage contigu.
Une fonction de
hachage simple
Une méthode de transformation simple consiste à associer une
adresse, représentée par un nombre naturel de 1 à n, à chaque clé dans
une table. Cette adresse est interprétée comme un numéro de page
relatif. Chaque page contient un nombre fixe de valeurs de clé, avec
ou sans les enregistrements de données correspondants.
La transformation des clés doit satisfaire les critères suivants :
Conditions
imposées au calcul
des adresses
la méthode de transformation doit comporter des opérations
simples et non onéreuses ;
135
approprié (qui est ici une feuille) et continue sa recherche.
Finalement, il trouve l'entrée désirée dans la feuille choisie. Dans cet
exemple simple, le coût de recherche de la valeur de clé E15 équivaut
seulement à deux accès pour atteindre d'abord la page associée au
nœud racine et ensuite la page associée à une feuille.
La hauteur de
l’arbre détermine le
temps d’accès
La hauteur de l'arbre multiple détermine le temps d'accès à une
valeur de clé ainsi qu'aux données identifiées par cette valeur. Il est
possible de réduire le temps d'accès en augmentant le nombre de
valeurs de clé (degré de branchement) par nœud dans un arbre
multiple.
L’arbre B* est
orienté feuilles
Une autre méthode consiste à construire un arbre multiple
orienté feuilles (aussi connu sous le nom d'arbre B*). Dans cette
structure, les enregistrements de données ne sont jamais stockés dans
des nœuds intérieurs mais toujours dans les feuilles de l'arbre. Tous
les nœuds contiennent uniquement des valeurs de clé afin de réduire
le plus possible la profondeur de l'arbre.
4.4.2 Méthodes de hachage
Stockage utilisant
la technique
d’adressage
dispersé
Les méthodes de transformation de clés ou de calcul des adresses
(key hashing, ou simplement hashing, en anglais) constituent le
fondement des structures d'accès et de stockage aléatoire. Une
fonction de hachage (hash function, en anglais) permet de transformer
un ensemble de clés en un ensemble d'adresses qui forme un espace
d'adressage contigu.
Une fonction de
hachage simple
Une méthode de transformation simple consiste à associer une
adresse, représentée par un nombre naturel de 1 à n, à chaque clé dans
une table. Cette adresse est interprétée comme un numéro de page
relatif. Chaque page contient un nombre fixe de valeurs de clé, avec
ou sans les enregistrements de données correspondants.
La transformation des clés doit satisfaire les critères suivants :
Conditions
imposées au calcul
des adresses
la méthode de transformation doit comporter des opérations
simples et non onéreuses ;