Embed Size (px)
Citation preview
1
Arbre-B+ Hypothèse initiale : clé simple et unique Nœud = bloc
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
45 48
Bloc 8
2
Structure d ’une feuille
1. Remplie à moitié au minimum
2. Clés triées : i < j Ci < Cj
3. Clés d'une feuille < clés de la suivante
4. Au même niveau (équilibré)
Ci : Clé
Ri : reste de l'enregistrement ou référence
S : Pointeur sur le bloc suivant dans la liste des feuilles
C 1 R 1 ... C n R n SEspace
libre
3
Structure d’un bloc interne
1. Rempli à moitié au minimum:
OrdreI ≤ n = nombre de pointeurs ≤ 2*OrdreI
2. Clés triées : i < j Ci < Cj
3. Ci-1 <= Clés sous Pi-1 < Ci P 1 C 1 ... P n-1 C n-1 P nP 2 ... C i-1 P i-1 C i
C i-1 <= C < C i
Espacelibre
C < C 1 C n-1 <= C
4
Rechercher 43
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
45 48
Bloc 8
5
Insertion dans un arbre-B+
OrdreI = 2
40 ...
B loc 0
20 ... 40 ...
B loc 0
20 ... 40 ... 60 ...
B loc 0
6
Débordement et division Insertion de 30 Débordement et la division du bloc 0 40 est promue Nouvelle racine
20 ... 40 ... 60 ...
B loc 0
20 ... 30 ...
B loc 0
40 ... 60 ...
B loc 1
40
Bloc 2
7
Insertion de 25
20 ... 30 ...
B loc 0
40 ... 60 ...
B loc 1
40
Bloc 2
40
Bloc 2
20
Bloc 0
25 30 40
Bloc 1
60
8
Insertion de 10
40
Bloc 2
20
Bloc 0
25 30 40
Bloc 1
60
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60
Débordement et la division du bloc 0 25 est promue
9
Insertion de 70
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Insertion de 50
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 60
Bloc 4
70
Débordement et la division du bloc 1 60 est promue
11
Insertion de 53
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 60
Bloc 4
70
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 53 60
Bloc 4
70
12
Insertion de 45
10
Bloc 0
20
25 40 60
Bloc 2
25
Bloc 3
30 40
Bloc 1
50 53 60
Bloc 4
70
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
Division du bloc 1 50 est promue Division de la racine
13
Suppression dans un arbre-B+
Cas simple minimum préservé pas la première
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60
14
Première clé du bloc et pas la première feuille
Remplacer dans le parent (si pas « aîné »)
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
60 70
10
Bloc 0
20
25 60
Bloc 2
25
Bloc 3
30 60
Bloc 1
70
15
Première clé du bloc et pas la première feuille
Remonter tant que l'enfant est l’« aîné »
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7050
Bloc 5
53 55
60
Bloc 6
50
Bloc 7
45 48
Bloc 8
10
Bloc 0
20
25 40 45
Bloc 2
25
Bloc 3
30 40
Bloc 1
43 44 60
Bloc 4
7053
Bloc 5
55
60
Bloc 6
53
Bloc 7
45 48
Bloc 8
16
Violation du minimum : redistribution si possible
Ajuster séparateur40
Bloc 2
20
Bloc 0
25 30 40
Bloc 1
60
30
Bloc 2
20
Bloc 0
25 30
Bloc 1
60
17
Violation du minimum : fusion
Fusion des deux frères
10
Bloc 0
20
25 60
Bloc 2
25
Bloc 3
30 60
Bloc 1
70
10
Bloc 0
25 30
60
Bloc 2
60
Bloc 1
70
Violation de larègle du minimum
18
Cas de fusion de feuilles et de redistribution au niveau du parent
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 60
Bloc 4
7050
Bloc 5
53
60
Bloc 6
50
Bloc 7
Violation de larègle du minimum
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
60
Bloc 6
50
Bloc 7
Violation de larègle du minimum
Redistribution
Fusion des deux frères
19
Cas de fusion de feuilles et de redistribution au niveau du parent (suite)
10
Bloc 0
20
25 40
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
60
Bloc 6
50
Bloc 7
Violation de larègle du minimum
Redistribution
10
Bloc 0
20
25
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7
20
Cas de fusion en cascade
Fusion des deux frères
10
Bloc 0
20
25
Bloc 2
25
Bloc 3
30 40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7
Violation de larègle du minimum
Fusion des deux frères
10
Bloc 0
25 30
25
Bloc 2
40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7Violation de la
règle du minimum
21
Cas de fusion en cascade (suite) : réduction de la hauteur
Fusion des deux frères
10
Bloc 0
25 30
25
Bloc 2
40
Bloc 1
45 50
Bloc 5
60 70
50
Bloc 6
40
Bloc 7Violation de la
règle du minimum
10
Bloc 0
25 30
40 50
Bloc 2
40
Bloc 1
45 50
Bloc 5
60 70
