Direkt zum Inhalt

Lexikon der Mathematik: B-Baum

spezielle Form eines Suchbaumes, die bei aufwendigen Suchen sinnvoll ist.

Zur Definition eines B-Baumes unterteilt man einen gegebenen Baum in Teilbäume, die als Seiten bezeichnet werden, und legt eine Ordnung n ∈ ℕ des Baumes fest. Dann heißt der Baum ein B-Baum der Ordnung n, wenn die folgenden vier Bedingungen erfüllt sind:

  1. Jede Seite enhält höchstens 2n Elemente.
  2. Jede Seite mit Ausnahme der Wurzelseite enthält mindestens n Elemente.
  3. Jede Seite hat entweder gar keine Nachfolgerseite oder sie hat m + 1 Nachfolgerseiten, wobei m die Zahl ihrer Elemente ist.
  4. Alle nachfolgerfreien Seiten liegen auf der gleichen Stufe.

Mit Hilfe von B-Bäumen lassen sich effiziente Suchalgorithmen sowie einfache Einfügeprozeduren entwickeln.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos