Für eine korrekte Darstellung dieser Seite benötigen Sie einen XHTML-standardkonformen Browser, der die Darstellung von CSS-Dateien zulässt.

. .
Suche

Universität Siegen Department ETI Fachgruppe Praktische Informatik

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


  • relevant für die Lehrveranstaltung(en):
  • Vorausgesetzte Lehrmodule:
    keine
  • Stoffumfang in Vorlesungsdoppelstunden: 1.0
  • Umfang in (DIN-A5-) Seiten: 20
  • URLs der Volltexte des Skripts:
    (Erläuterungen zu den Dateiformaten; bitte lesen, sofern beim Entpacken oder Drucken der Dateien Probleme auftreten.)
  • Begleitmaterial:
    - keines -
  • Änderungen gegenüber früheren Versionen:
    2013-11-26: geringfügige redaktionelle Bearbeitung
    2004-10-22: redaktionelle Überarbeitung; Glossar zusätzlich
    2004-11-06: Abschnitt 3.2, S.8: redaktionelle Umstellungen; S. 9 und 17: Formel "k+s+t" durch "k+i+t" ersetzt
    2002-10-07: redaktionelle Überarbeitung
    2002-02-02: Erstversion