B-Baum

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 0 (nicht überprüft)

Umfang: 2 (wichtige Fakten fehlen)

Quellenangaben: 3 (wichtige Quellen vorhanden)

Quellenarten: 3 (gut)

Konformität: 3 (gut)

Definition

Der B-Baum gehört zu den klassischen Indexstrukturen wie auch der Hash. Wichtigstes Merkmal ist das der B-Baum immer vollständig balanciert ist. Die Daten werden nach Schlüsseln sortiert gespeichert. In Datenbanken wird der B-Baum für den optimierten Zugriff auf die Datensätze eingesetzt.

Eigenschaften

• der B-Baum ist vollständig balanciert, d.h. die gleiche Tiefe von der Wurzel zum Blatt
• pro Knoten mind. n und max. 2n Schlüssel (n ⩽ m ⩽ 2n Datensätze)
• Wurzel mind. 1 oder max 2n Schlüssel (1 ⩽ m ⩽ 2n Datensätze)
• jeder Knoten mit n Schlüssel (außer den Blättern) hat n+1 Kindknoten
• der Baum und alle Schlüssel sind sortiert
• Knoten mit 0 Kindknoten heißen Blätter, diese liegen beim B-Baum auf einer Ebene.

Beispiel für einen B-Baum

Quellen

• Objektrelationale Datenbanken, Can Türker, Gunter Saake, 2006, ISBN 3-89864-190-2
• http://mmdb.hs-augsburg.de/literatur/
• http://cis.cs.tu-berlin.de/Lehre/WS-0304/Sonstiges/db-pages/Inhalt/datenorganisation/Folien
• http://de.wikipedia.org/wiki/B-Baum