Arbre RN ↔ arbre 2-3-4
Qu’est-ce qui se passe lors d’une insertion ?
On cr´ee un nœud rouge : promotions+rotations en ascendant vers la racine
Rotation : nœud noir avec un enfant rouge et son grand-enfant rouge transform´e
en un nœud noir avec deux enfants rouges
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
61
xzyyzxRotationyzxABCDzyCDxABDécalageArbre RN ↔ arbre 2-3-4 (promotions)
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
62
xuyuxPromotionABCxABDécoupagevyuxvrang rrang rrang r+1uyvCDEvDEyArbre RN ↔ arbre 2-3-4 (cont)
Cas sp´ecial : promotion de la racine
⇒ la hauteur de l’arbre croˆıt par le d´ecoupage de la racine
(arbre binaire de recherche : la hauteur croˆıt par l’ajout de feuilles)
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
63
Advertisement
xuABCxABDécoupageuyvCDEvDEy(nouvelle racine)Recherche dans m´emoire externe
Supposons qu’on veut stocker un grand nombre de donn´ees : enregistrements
avec cl´es
On veut minimiser l’acces au disque dur : 105 fois plus de temps que l’acces `a la
m´emoire principale
Stocker un arbre rouge et noir ? ?
Arbre 2-3-4 est plus efficace : on modifie «quelques» nœuds seulement
Comment am´eliorer ?
on g´en´eralise `a M sous-arbres au lieu de 4.
Une autre bonne id´ee : on va mettre les donn´ees aux feuilles, et ne stocker que des
cl´es `a des nœuds internes («B+-arbre»)
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
64
B-arbre
Donn´ees stock´ees aux feuilles : L enregistrements `a une feuille
Cl´es stock´es aux nœuds internes : (M − 1) cl´es `a un nœud interne, M enfants
Advertisement
Cl´e i : valeur minimale dans le sous-arbre (i + 1)
Racine : 2..M enfants
Nœuds internes : dM/2e..M enfants (taille : M · |cl´e| + (M − 1) · |pointeur|)
Feuilles : dL/2e..L enregistrements (taille : L · |enregistrement|)
Feuilles ont la mˆeme profondeur
Choix de M et L : on utilise un bloc (taille typique : 4k, 8k, . . . ) par nœud
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
65
B-arbre
Thm. La hauteur h de B arbre est born´ee par
h ≤ 1 + logdM/2e
N
2
≤ 1 +
lg n
L
Advertisement
lg M − 1
o`u N est le nombre de feuilles et n est le nombre d’enregistrements.
Exemple (du livre) : blocs de 8k, cl´es de 32 octets, enregistrements de 256 octets,
M = 228, L = 32
h = 4 suffit jusqu’`a N = 2.9 · 106 ou n = 47 · 106
⇒ nombre d’acces au disque est determin´e par h : tres peu (en plus, on peut garder
la racine et peut-ˆetre mˆeme le premier niveau en m´emoire principale)
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
66
B-arbre (cont)
Insertion d’un enregistrement : s’il y a de la place dans la feuille, aucun probl`eme
s’il n’y a pas de place : d´ebordement de la feuille
solution : d´ecoupage de la feuille → ´el´ements distribu´es en deux feuilles de tailles
2 c + 1 et dL
bL
2 e.
Advertisement
peut causer un d´ebordement au parent : d´ecoupage si n´ecessaire en ascendant vers
la racine
⇒ la hauteur croˆıt en d´ecoupant la racine
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
67
B-arbre (cont)
Suppression d’un ´el´ement : si la feuille est toujours assez complete, aucun probleme
et si le nombre d’´el´ements tombe en-dessous de dL/2e ?
1. prendre des ´el´ements des sœurs imm´ediates
2. si elles sont au minimum, alors fusionner les feuilles → le parent perd un unfant
3. continuer avec le parent de la mˆeme mani`ere si nombre d’enfants < dM/2e
⇒ la hauteur d´ecroˆıt en enlevant la racine (quand elle a un enfant seulement)
Arbres ? IFT2010 H2006 ? UdeM ? Mikl´os Cs˝ur¨os
68