B-Baum
aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Dieser Artikel sollte auf Korrektheit, Quellenangaben und GlossarWiki-Konformität hin überprüft werden.
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