Indexstruktur

Grundidee und Zweck

Indexstrukturen, auch Indizes genannt, sind Datenstrukturen der Informatik, die schnellen Zugriff auf Daten in großen Datensammlungen ermöglichen. Ohne Index werden Daten oft sequentiell auf einem Speichermedium verwaltet; eine Suchanfrage hätte dann linearen Aufwand, und im ungünstigsten Fall müsste der gesamte Datenbestand durchsucht werden.

Ein Index speichert Informationen darüber, wo ein gesuchter Datensatz liegt. Wird ein Datensatz anhand eines Suchkriteriums gesucht, kann der Index die Position im Speichermedium schnell bestimmen und eine aufwendige Suche vermeiden. Besonders wichtig ist das bei großen Datenmengen, etwa wenn sie nicht vollständig in den Hauptspeicher passen.

Wichtige Verfahren

Indexstrukturen sind selbst spezielle Datenstrukturen. Bekannte Verfahren sind sortierte Reihen, Hashtabellen und Baum-Strukturen wie Binärbäume, B-Bäume und B*-Bäume.

Eine sortierte Reihe erlaubt effiziente Suche durch binäre Suche. Dabei wird eine sortierte Liste wiederholt gedanklich halbiert, sodass aufgrund der Sortierung entschieden werden kann, in welcher Hälfte das gesuchte Element liegen muss.

Für besondere Anforderungen gibt es spezielle Indexstrukturen. Geodatenbanken verwenden zum Indizieren mehrdimensionaler Daten beispielsweise R-Bäume. Sie erlauben mehrdimensionale Suchkriterien und Distanzberechnungen. Weitere genannte Verfahren für mehrdimensionale Datenstrukturen sind Bitmapindex, Gridfile, k-d-Baum, R-Baum, UB-Baum und Bereichsbaum.

Beispiel Karteikarten

Ein Karteikarten-System kann als Indexstruktur verstanden werden. Eine Adresssammlung wird so unterteilt, dass bei einem Suchkriterium wie dem Familiennamen nur eine Teilmenge durchsucht werden muss. Wird etwa „Müller“ gesucht, genügt zunächst die Teilmenge der Namen mit Anfangsbuchstaben „M“. Ist diese Teilmenge noch zu groß, kann weiter nach zweitem oder drittem Buchstaben unterteilt werden, sodass nur noch Namen mit „Mül“ durchsucht werden.

Für andere Suchkriterien ist derselbe Index aber nicht automatisch geeignet. Wer an einem bestimmten Tag Geburtstag hat, lässt sich in einem nach Familiennamen geordneten Karteisystem nur finden, indem die gesamte Kartei durchsucht wird. Das Attribut „Geburtstag“ ist dann nicht indiziert. Ein zweiter Index kann helfen: Für jeden Kalendertag wird ein Verweis auf den Primärindex gespeichert, typischerweise auf den Namen. Ein solcher Index heißt Sekundärindex oder externer Index.

Der Vorteil eines Sekundärindex ist, dass Daten wie eine Adressänderung nur im primären Adressbestand geändert werden müssen. Der Nachteil ist, dass man bei einer Anfrage zuerst im Sekundärindex suchen und danach im Primärindex die eigentlichen Daten nachschlagen muss.

Auch eine vollständig sortierte Liste ist eine einfache Indexstruktur. Sie kann mit binärer Suche effizient durchsucht werden, wie etwa in einem gedruckten Telefonbuch. Eine weiterentwickelte Struktur nach ähnlichem Prinzip ist der B-Baum, der sich leichter aktualisieren lässt.

Anwendungsgebiete

Das bekannteste Anwendungsgebiet von Indexstrukturen sind Datenbanken. Dort werden sehr große Datenmengen verarbeitet, oft so groß, dass sie nicht vollständig in den Hauptspeicher passen. Geeignete Indizes auf Tabellen können die Leistung deutlich erhöhen. Der Artikel verweist hier auch auf den Datenbankindex und die technische Umsetzung zur Invertierten Datei.

Geoinformationssysteme verwenden Indexstrukturen häufig innerhalb von Datenbanken. Manchmal ist aber auch eine direkte Integration der Indexstruktur nötig, um die gewünschte Performanz zu erreichen. Dabei werden räumliche Indexstrukturen genutzt, um den Suchbereich zu begrenzen.

Ein weiteres Anwendungsgebiet ist die Computergrafik, besonders bei Echtzeit-Anwendungen und 3D-Computerspielen. Dort können räumliche Indexstrukturen wie der BSP-Baum zur Verwaltung der Umgebung eingesetzt werden.

Arten von Indexstrukturen

Indexstrukturen lassen sich nach ihrer Arbeitsweise in mehrere Typen einteilen.

Interne Indexstrukturen speichern die eigentlichen Daten selbst. Externe Indexstrukturen speichern nur Verweise auf die Daten, zum Beispiel in einem anderen Index. Man spricht auch von Primärindex und Sekundärindex. Ein Sekundärindex braucht im Allgemeinen weniger Speicher und ist bei Änderungen leichter synchron zu halten. Er ist aber langsamer, weil die eigentlichen Daten zusätzlich aus dem Primärindex geholt werden müssen. Sekundärindizes können mehrdimensionale Indexstrukturen emulieren, sind aber in vielen Fällen echten mehrdimensionalen Indexstrukturen unterlegen.

Dynamische Indexstrukturen passen ihre Struktur bei Änderungen an den Daten an. Statische Indexstrukturen tun das nicht. Statische Indexstrukturen erlauben schnelleren Zugriff, müssen bei Änderungen aber oft aufwendig neu berechnet werden. Beim Einfügen in eine sortierte Reihe müssen im Schnitt die Hälfte der gespeicherten Daten verschoben werden. Dynamische Indexstrukturen können bei Änderungen lokal aktualisiert werden, also nur in einem kleinen Teil des Index. Eine statische Hashtabelle ist ein Beispiel für eine statische Indexstruktur, ein B-Baum für eine dynamische.

Eindimensionale Indexstrukturen indizieren nach einem einzigen Attribut, zum Beispiel nach „Nachname“. Für zusätzliche Attribute werden oft zusätzliche eindimensionale Sekundärindizes angelegt. Mehrdimensionale Indexstrukturen können Anfragen mit mehr als einem Attribut effizient beantworten, etwa „Vorname“ und „Nachname“ gleichzeitig. Sie sind besonders wichtig für räumliche Daten, etwa bei Fragen wie „Was ist die nächstgelegene Tankstelle?“ oder „Alle Objekte im Rechteck R“.

Geclusterte Indexstrukturen ordnen die Daten physisch so, wie sie im Index und in Anfragen gebraucht werden. Dadurch können Bereichsanfragen effizienter sein, weil benachbarte Elemente oft auf denselben Datenseiten liegen. Ein alphabetisch nach Familiennamen sortiertes Adressbuch mit eigenen Seiten für jeden Buchstaben entspricht funktionell einem geclusterten Index. Eine Hashtabelle ist normalerweise nicht geclustert. Ein B+-Baum ist ein Beispiel für eine geclusterte Indexstruktur.

Dünnbesetzte Indexstrukturen erlauben Lücken, also unbesetzte Speicherpositionen. Das kostet zusätzlichen Speicher und kann die Suche verlangsamen, erleichtert aber Änderungen: Neue Daten können in Lücken eingefügt werden, und beim Entfernen von Daten können Lücken entstehen, ohne den ganzen Index neu zu organisieren. Viele dünnbesetzte Indexstrukturen können ihre Größe dynamisch anpassen und versuchen zum Beispiel zu garantieren, dass sie nicht mehr als doppelt so viel Platz belegen wie nötig. Eine sortierte Reihe ist dichtbesetzt; Hashtabellen und Bäume sind in der Regel dünnbesetzt.

Abwägung

Indexstrukturen beschleunigen Suchvorgänge und sind deshalb in vielen Bereichen unverzichtbar. Sie haben aber auch Nachteile: Die Struktur selbst verursacht zusätzlichen Verwaltungsaufwand. Außerdem kann je nach Verfahren ein hoher Speicheraufwand entstehen. Die Wahl einer geeigneten Indexstruktur hängt daher davon ab, welche Anfragen unterstützt werden sollen, wie häufig sich die Daten ändern, wie viel Speicher verfügbar ist und ob ein schneller Zugriff wichtiger ist als geringer Verwaltungsaufwand.