BaumIndizes

Baumindizes sind Indexstrukturen, die auf Baumdatenstrukturen basieren, um Datensätze effizient nach Schlüsselwerten zu suchen. Sie ermöglichen schnelle Abfragen, Einfügungen und Löschungen, indem sie Daten hierarchisch ordnen und Suchpfade durch logarithmische Höhen begrenzen. Baumindizes können sowohl auf Festplatten als auch im Arbeitsspeicher implementiert sein; in Datenbanken und Dateisystemen dienen sie dazu, Eingriffe von I/O zu reduzieren, indem viele Suchoperationen über wenige Baumebenen erfolgen.

Zu den verbreitetsten Baumindizes gehören B-Bäume und B+-Bäume, die durch ihren hohen Verzweigungsgrad große Blöcke pro Knoten nutzen. Selbstbalancierende Suchbäume wie Rot-Schwarz-Bäume oder AVL-Bäume halten die Baumhöhe klein, um Such- und Update-Operationen konstant logarithmisch zu halten. In relationalen Datenbanksystemen sind B+-Bäume oft der Standardindex, wobei alle Suchschlüssel in den Blättern gespeichert sind und innere Knoten nur Führungswerte enthalten.

Die Indizes unterstützen Bereichsabfragen, Sortieroperationen und schnellen Zugriff auf zugehörige Datensätze, indem sie Zeiger oder Referenzen auf Tupel speichern. Ein Index kann auf eine oder mehrere Spalten angewendet werden (Composite-Indizes) und wird üblicherweise in Blöcken gespeichert, um die Festplattenzugriffe zu minimieren.

Vorteile von Baumindizes sind schnelle Lesezugriffe, gute Skalierbarkeit und effiziente Nutzung von Speicher- bzw. Festplattenblockgrößen. Nachteile ergeben sich aus dem Aufwand bei Einfügungen und Löschungen, der Notwendigkeit regelmäßiger Rebalancing- oder Blätter-Verlinkungsarbeiten und der Speicherkosten für Indexstrukturen. Für mehrdimensionale Abfragen kommen oft andere Strukturen wie R-Bäume, KD-Bäume oder trie-ähnliche Indizes zum Einsatz. Der korrekte Einsatz hängt von Abfragearten, Dataset-Größe und Speichergesetzen ab.