134
Introduction pratique aux bases de données relationnelles
sous-arbre de droite contient des valeurs satisfaisant la condition «E#
est supérieur à E4» (c'est-à-dire E7 et E19). Nous procédons de la
même manière pour insérer d'autres valeurs de clé sans changer la
hauteur de l'arbre.
Figure 4-11
Mise à jour
dynamique d’un
arbre multiple
Processus de
recherche
Pour rechercher une valeur de clé particulière, le système de
bases de données procède comme suit : soit E15 la valeur à rechercher
dans l'arbre multiple A4 à la figure 4-11. Le système la compare tout
d'abord aux entrées du nœud racine. E15 est comprise entre les
valeurs de clé E4 et E18, le système choisit donc le sous-arbre
EMPLOYÉ
E19
E1
E7
E4
Savoy
Meier
Humbert
Brodard
E#
Nom
D6
D3
D5
D6
Affectation
Romont
Fribourg
Bulle
Fribourg
Ville
Construction de
l'arbre multiple
Insérer :
E3
Insérer :
E9,E18,E24,E2
Insérer :
E26,E15
Scinder
la racine
Arbre A1
Scinder
le sous-arbre
E1 E4 E7 E19
E7 E9 E15
Arbre A2
E4
E1 E3
E7 E19
Arbre A3
E4
E1 E2 E3
E7 E9 E18 E19
Arbre A4
E4
E18
E1 E2 E3
E19 E24 E26
E# < E4
E4 < E# < E18
E# > E18