Informationen zum Lehrmodul
B-Bäume

Stand: 26.11.2013

• Zusammenfassung dieses Lehrmoduls: B-Bäume bzw. B*-Bäume sind eine der wichtigsten Erfindungen der Informatik. Sie implementieren den generischen abstrakten Datentyp Verzeichnis. Im Gegensatz zu den hauptspeicherorientierten binären Bäumen sind B-Bäume plattenorientiert. Weiterhin weisen sie die Besonderheit auf, nicht zu degenerieren und Suchzeiten in der Größenordnung von log(n) zu garantieren. B*-Bäume verbessern die Suchgeschwindigkeit weiter, indem die Nutzdaten nur noch in den Blättern des Suchbaums gespeichert werden, wodurch die Indexknoten einen höheren Verzweigungsgrad haben können.
• Inhaltsverzeichnis:
  1   Historischer Hintergrund
  2   Verzeichnisse
  2.1   Generische ADT
  2.2   Der generische ADT directory [S,I]
  3   B-Bäume
  3.1   Grundlegende Implementierungsentscheidungen
  3.2   Vielweg-Suchbäume
  3.3   Merkmale von B-Bäumen
  3.4   Primärschlüssel
  4   Algorithmen
  4.1   Suche
  4.2   Einfügung
  4.3   Löschung
  4.4   Beispiel
  5   B*-Bäume
• Vorausgesetzte Lehrmodule: keine
• Stoffumfang in Vorlesungsdoppelstunden: 1.0
• Volltext des Skripts: PDF, 1-spaltig, DIN A5 (20 Seiten, 560 kB)
• Folien zur Vorlesung: PDF, 4:3-Format (355 kB)
• Begleitmaterial: - keines -