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