B*-Baum Part 2 (PDF)

B*-Baum Part 2 1 DB2 – Dr. Karsten Tolle  Ebene und Höhe Für gewurzelte Bäume werden unter Ebene (oder Level) alle Knoten zusammengefast, die mir 0 bis n Schritten von der Wurzel erreicht werden können. Also Ebene 0 ist die Wurzel selbst. Die Höhe d...

B*-Baum Part 2 1 DB2 – Dr. Karsten Tolle  Ebene und Höhe Für gewurzelte Bäume werden unter Ebene (oder Level) alle Knoten zusammengefast, die mir 0 bis n Schritten von der Wurzel erreicht werden können. Also Ebene 0 ist die Wurzel selbst. Die Höhe des Baumes ist das maximale n, bei dem alle Blätter erreicht werden. (In unseren B*-Bäumen sind alle Blätter auf der gleichen Ebene!) First record, key value omitted Second record Third record B1 25 144 Ebene 0 B2 9 – B3 64 100 B4 196 – Ebene 1 Höhe des Baumes ist also 2! 1…4… – 9… 16… – 25…36…49 64…81… – 100...121… – 144…169… – 196…225…256… Ebene 2 B5 B6 B7 B8 B9 B10 B11 2 DB2 – Dr. Karsten Tolle  k-Berechnung – mit echten Werten … k ist abhängig vom Schlüssel und Pointergröße Datenblock Pointer aktuell (64-bit machine) also 8 Byte Blockgröße: 4000 Byte (grob) Schlüssel: Integer = 4 Byte … alles andere je nach Situation  Integer als Key: 1. Eintrag braucht 8 Byte … jeder weitere Eintrag braucht 12 Byte 1 + 3992/12 = 333,66666 … # wir bekommen also maximal 333 Einträge in einen inneren Knoten 3 DB2 – Dr. Karsten Tolle  k-Berechung … Maximal 333 Einträge in einen inneren Knoten Maximale Einträge sind aber 2k-1  2k-1