7.6 Interne Ebene: KdB-Bäume

• mehrdimensionaler (k-dimensionaler) B-Baum
• kann Primärschlüssel und mehrere Sekundärschlüssel gleichzeitig verwalten
• div. Variationen (KDB-tree, Kd-tree,..)
• Idee: auf jeder Seite steckt Teilbaum, der nach mehreren Attributen hintereinander verzweigt
• KdB-Baum vom Typ (b,t):
  • innere Knoten (Bereichsseiten): enthalten einen Kd-Baum mit max. b internen Knoten
  • Blätter (Satzseiten): enthalten bis zu t Tupel der gespeicherten Relation
• Bereichsseite enthält: Anzahl der Schnitt- und Adreß -Elemente der Seite, Zeiger auf Wurzel des in der Seite enthaltenen Kd-Baums, Schnitt- und Adreß-Elemente
• Schnittelement enthält: Index (Nummer eines Attributs), Wert des Attributs, 2 Zeiger auf Nachfolgeknoten innerhalb des Kd-Baums
• Adreß -Element enthält: Adresse eines Nachfolgers der Bereisseite im KdB-Baum
• Satzseite enthält: Anzahl der Sätze der Seite, Datensätze

KdB-Bäume

• Operationen analog zum B-Baum, auch in
  O(log n) Seitenzugriffen
• es gilt: alle Tupel im linken Teilbaum eines Kd-Baum-Knotens sind bzgl. des dort enthaltenen
  (Trenn-)Attributs höchstens so groß wie der darin enthaltene (Trenn-)Wert; rechts analog
• Reihenfolge der Trennattribute zyklisch (s. Bsp.)
• 2d-Baum entspr. 2-dimensionaler Einteilung des Datenraums (Vergl. Gridfiles)