Databases Reference
In-Depth Information
Definition: B
+
-Baum
Zu jedem B
+
-Baum gehört eine natürliche Zahl m, die als
Ord-
nung
des Baumes bezeichnet wird.
1.
2.
Jeder Knoten enthält maximal 2m Werte.
3.
Bis auf die Wurzel enthält jeder Knoten des Baumes mindestens
m Werte.
4.
In jedem inneren Knoten gibt es zu jedem seiner Werte
v
zwei
Referenzen auf andere Knoten im Baum, die wir als seinen lin-
ken und rechten
Nachfolger
bezeichnen. Alle Werte des linken
Nachfolgers sind kleiner als
v
, alle Werte des rechten Nachfol-
gers sind größer oder gleich
v
, insbesondere ist
v
auch im rech-
ten Nachfolger enthalten.
5.
Bis auf die Wurzel wird jeder Knoten von genau einem anderen
Knoten - seinem
Vorgänger
- referenziert.
6.
Die Werte sind in allen Knoten in aufsteigender Reihenfolge sor-
tiert.
7.
Wenn in einem inneren Knoten der Wert
w
auf den Knoten
v
folgt, dann sind der rechte Nachfolger von v und der linke Nach-
folger von w identisch.
8.
Ein innerer Knoten mit p Werten hat genau p+1 Nachfolger.
9.
Jeder Wert eines Blattes referenziert genau einen Datensatz über
seine RID.
Die letzte Regel wird wichtig, wenn wir in den folgenden Abschnitten die Algo-
rithmen beschreiben, mit denen der B
+
-Baum durchsucht, verkleinert und vergrö-
ßert wird.
Das Beispiel in Abbildung 20.4 ist ein B
+
-Baum der Ordnung 1. Jeder Knoten ent-
hält somit maximal zwei Werte. Im ersten Knoten der mittleren Ebene folgt der
Wert 42 dem Wert 31; der rechte Nachfolger von 31 ist in diesem Knoten der linke
Nachfolger von 42.
