B-Baum

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Wechseln zu:Navigation, Suche

Der B-Baum ist ein eine spezielle Datenstruktur zur effizienten Speicherung und Verwaltung von Massendaten auf einem Massenspeicher mit wahlfreiem Zugriff, wie Festplatte oder SSD. Ein B-Baum ist vollständig balanziert und sehr flach, dafür aber sehr breit.

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur eingeschränkt:
  ★★★★☆ Korrektheit: großteils überprüft
  ★★☆☆☆ Umfang: wichtige Fakten fehlen
  ★★★★☆ Quellenangaben: fast vollständig vorhanden
  ★★★★★ Quellenqualität: ausgezeichnet
  ★★★☆☆ GlossarWiki-Konformität: gut

1 Graphentheoretische Definition (Bayer, McCreight 1970[1])

Let $h \ge 0$ be an integer, $k$ a natural number. A directed tree $T$ is in the class $\tau(k,h)$ of B-Trees if $T$ is either empty ($h=0$) or has the flollowing properties:

  1. Each path from the root to any leaf has the same length $h$, also called the height of $T$. i.e., $h$ = number of nodes in path.
  2. Each node except the root and the leaves has at least $k + 1$ sons. The root is a leaf or has at least two sons.
  3. Each node has at most $2k +1$ sons.

1.1 Übersetzung (Kowarschick 2015)

Es seien $h \ge 0$ eine ganze Zahl und $k$ eine natürliche Zahl [größer Null]. Ein gerichteter Baum $T$ ist Element der Klasse $\tau(k,h)$ von B-Bäumen, wenn $T$ entweder leer ist ($h=0$) oder folgende Eigenschaften hat:

  1. Jeder Pfad von der Wurzel zu irgendeinem Blatt hat dieselbe Länge $h$, welche auch die Höhe von $T$ genannt wird. Das heißt, $h$ = Anzahl der Knoten im Pfad.
  2. Jeder Konten mit Ausnahme der Wurzel und der Blätter hat mindestens $k + 1$ Söhne. Die Wurzel ist entweder ein Blatt oder hat mindestens zwei Söhne.
  3. Jeder Knoten hat höchstens $2k +1$ Söhne.

2 Beispiel für einen B-Baum

Beispiel B Baum.png

3 Quellen

  1. Bayer, McCreight (1970): Rudolf Bayer und Edward M. McCreight; Organization and Maintenance of Large Ordered Indexes; Proceedings of the 1970 ACM SIGFIDET (SIGFIDET '70); Verlag: Association for Computing Machinery; Adresse: New York; Web-Link; 1970; Quellengüte: 5 (Konferenzartikel)
  1. Bayer, McCreight (1972): Rudolf Bayer und Edward M. McCreight; Organization and Maintenance of Large Ordered Indexes; in: Acta Informatica; Band: 1; Nummer: 3; Seite(n): 173-189; Verlag: Springer-Verlag; Web-Link; 1972; Quellengüte: 5 (Artikel)
  2. Bayer (1982): Rudolf Bayer; Datenstrukturen – Kurseinheit 6: Datenstrukturen für Peripheriespeicher; Band: 6; Hochschule: Fernuniversität – Gesamthochschule – in Hagen; Adresse: Hagen; 1982; Quellengüte: 4 (Skript)