Indexstruktur

Indexstrukturen (Indizes) werden in der Informatik verwendet, um den schnellen Zugriff auf Daten in einer umfangreichen Datensammlung zu gewährleisten. Daten werden üblicherweise sequentiell auf einem Speichermedium verwaltet. Die Bearbeitung einer Suchanfrage wäre dabei mit linearem Aufwand verbunden, im ungünstigsten Fall müsste der komplette Datenbestand durchsucht werden.

Wird nun ein bestimmter Datensatz anhand eines Suchkriteriums in dieser Datenmenge gesucht, kann über eine Indexstruktur eine aufwendige Suche vermieden werden. Der Index erlaubt es, die Position des Datensatzes innerhalb des Mediums schnell zu bestimmen.

Bekannte Verfahren

Indexstrukturen sind selbst spezielle Datenstrukturen wie

• sortierte Reihe (effiziente Suche mittels binärer Suche)
• Hashtabellen
• Baum-Strukturen wie Binärbäume, B-Bäume, B*-Baum

Für besondere Anforderungen gibt es auch spezielle Indexstrukturen. Beispielsweise verwenden Geodatenbanken zum Indizieren mehrdimensionaler Daten R-Bäume. Diese Bäume erlauben mehrdimensionale Suchkriterien und Distanzberechnungen.

• Bitmapindex, Gridfile, k-d-Baum, R-Baum, UB-Baum, Bereichsbaum für mehrdimensionale Datenstrukturen

Funktionsprinzip anhand eines Beispiels

Ein typisches Karteikarten-System kann als Indexstruktur bezeichnet werden: Die Menge der Adressen wird so unterteilt, dass anhand des Suchkriteriums („Familienname“) nur eine bestimmte Teilmenge aller Adressen in Frage kommt. Eine typische Unterteilung wäre nach dem Anfangsbuchstaben. Wird dann der Name „Müller“ gesucht, muss lediglich die Teilmenge, die mit „M“ anfängt, durchsucht werden. Diese Teilmenge kann meist über eine Markierung in der Kartei schnell gefunden werden. Ist diese Teilmenge noch immer zu groß, können die Teilmengen über den zweiten oder dritten Buchstaben weiter untergliedert werden. Anstatt nun alle Namen zu durchsuchen, werden nur noch die Namen durchsucht, die mit „Mül“ anfangen. Dies kann in vergleichsweise kurzer Zeit geschehen.

Um herauszufinden, wer an einem bestimmten Tag Geburtstag hat, ist ein solches Karteikartensystem jedoch nicht geeignet: Man müsste stets die gesamte Kartei durchsuchen. Man spricht davon, dass das Attribut „Geburtstag“ nicht indiziert wurde. Abhilfe schafft hier ein zweiter Index, in dem für jeden Kalendertag meist nur ein Verweis auf den Primärindex gespeichert wird, hier typischerweise der Name. Formell bezeichnet man so etwas als „Sekundärindex“ oder „externen Index“. Um jetzt aber beispielsweise für einen bestimmten Tag Grußkarten zum Geburtstag zu verschicken, ist es notwendig, zuerst die Namen der Empfänger zu ermitteln, dann im primären Index die zugehörigen Adressen nachzuschlagen. Der Vorteil ist aber, dass eine Adressänderung auch nur in der primären Adresskartei gemacht werden muss, nicht zusätzlich in der Geburtstagsliste.

Eine beliebige vollständig sortierte Liste stellt ebenfalls eine einfache Art Indexstruktur dar, die mittels der sogenannten binären Suche effizient durchsucht werden kann. Hierbei wird die Liste gedanklich wiederholt in zwei Teile geteilt, und aufgrund der bestehenden Sortierung kann einfach festgestellt werden, in welchem der beiden Teile das gesuchte Element liegen muss. Eine derartige Suche ist beispielsweise auch in einem gedruckten Telefonbuch möglich. Eine fortgeschrittenere, auf derselben Idee basierende Indexstruktur ist der B-Baum. Wesentliche Vorteile liegen hier in einer einfacheren Aktualisierbarkeit. In einem von Hand geführten Adressbuch hat man aber die Problematik, dass man keine Einträge einfügen kann, daher kann man dort weder eine vollständige sortierte Liste noch einen B-Baum realisieren – das oben beschriebene Karteikartensystem (bei dem innerhalb eines Anfangsbuchstabens nicht vollständig sortiert wird) jedoch schon. Auf den üblicherweise von Hand geführten Datenmengen ist dies auch kein Problem.

Verwendung

Datenbanken sind das bekannteste Anwendungsgebiet von Indexstrukturen. Da hier besonders große Datenmengen verarbeitet werden müssen – insbesondere auch so große Datenmengen, dass sie nicht vollständig in den Hauptspeicher passen –, ist hier der schnelle Zugriff kritisch. So können auf Tabellen geeignete Indizes definiert werden, die zu einer erheblichen Leistungserhöhung führen. Siehe dazu auch Datenbankindex, welche die technische Umsetzung zur Invertierte Datei ist.

Geoinformationssysteme verwenden Indexstrukturen oft in Form einer Datenbank, jedoch kann manchmal eine direkte Integration der Indexstruktur notwendig sein, um die gewünschte Performanz zu bringen. Hier werden räumliche Indexstrukturen eingesetzt, um den Suchbereich zu begrenzen.

Ein weniger offensichtliches Anwendungsgebiet ist die Computergrafik, insbesondere bei Echtzeit-Anwendungen und 3D-Computerspielen. Hier werden oft räumliche Indexstrukturen wie der BSP-Baum zur Verwaltung der Umgebung verwendet.

Typen

Indexstrukturen können anhand ihrer grundlegenden Arbeitsweise in verschiedene Typen unterteilt werden.

Interne und externe Indexstrukturen

Interne Indexstrukturen speichern die eigentlichen Daten selbst, externe Strukturen lediglich Verweise auf die Daten (beispielsweise in einem anderen Index). Man spricht hier auch von einem Primär- oder Sekundärindex. Ein Sekundärindex benötigt im Allgemeinen weniger Speicher und ist einfacher synchron zu halten bei Änderungen an den Daten. Er ist jedoch auch langsamer, da stets die eigentlichen Daten aus dem Primärindex geholt werden müssen.

Ein Beispiel für einen Sekundärindex wäre folgendes: Adressdaten sind wie oben beschrieben auf Karteikarten, sortiert nach Familienname abgelegt. Als Sekundärindex wird eine Liste gepflegt, die den Vornamen auf Familiennamen abbildet, also beispielsweise „Max“ auf „Müller“ und „Mustermann“. Es wird hier aber nur der Familienname abgelegt, nicht die vollständige Adresse. Ändert sich beispielsweise die Telefonnummer, so reicht es, diese im Primärindex zu aktualisieren. Möchte man jedoch die Telefonnummer von jedem „Max“ ermitteln, so müssen zunächst im Sekundärindex die Familiennamen nachgeschlagen werden, anschließend mit dem Familiennamen im Primärindex die Telefonnummer. Würde man die vollständige Adresse auch unter dem Vornamen ablegen, so wäre dies ein zweiter Primärindex, jede Änderung müsste dann aber in beiden Karteien vorgenommen werden.

Sekundärindizes erlauben die Emulation von mehrdimensionalen Indexstrukturen. Sie sind aber in vielen Anwendungsfällen einer echt mehrdimensionalen Indexstruktur unterlegen.

Dynamische und statische Indexstrukturen

Eine Indexstruktur heißt dynamisch, wenn sie ihre Struktur bei Änderungen an den Daten dynamisch an diese anpasst, sonst wird sie als statisch bezeichnet.

Statische Indexstrukturen erlauben einen schnelleren Zugriff auf die Daten, müssen jedoch bei Änderungen an den Daten aufwendig neu berechnet werden. So müssen beispielsweise beim Einfügen in eine sortierte Reihe im Schnitt die Hälfte der gespeicherten Daten verschoben werden. Dynamische Indexstrukturen erlauben es, den Index bei jeder Änderung dynamisch zu aktualisieren. Man sagt auch, dass bei Änderungen nur eine „lokale“ Änderung an der Indexstruktur vorgenommen wird, sich also nur ein kleiner Teil des Index dadurch verändert.

Ein typisches Beispiel für eine statische Indexstruktur ist die (statische) Hashtabelle und für eine dynamische Indexstruktur der B-Baum. Die Baumtiefe und -Struktur wird hier automatisch der Datenmenge angepasst. Änderungen am Baum passieren oft nur in dem betroffenen Blatt oder einem Pfad von der Wurzel zu dem betroffenen Blatt.

Ein- und mehrdimensionale Indexstrukturen

Typische Indexstrukturen indizieren nach einem einzigen Attribut (beispielsweise nach „Nachname“), auch wenn die Daten zusätzliche Attribute enthalten. Um Anfragen nach solchen zusätzlichen Attributen (oder der Kombination daraus) zu erlauben, werden zusätzliche eindimensionale Sekundär-Indizes angelegt. Möchte man aber nach zwei Attributen gleichzeitig anfragen, so muss der Schnitt berechnet werden. Hierbei werden in ungünstigen Fällen sehr viele Daten zunächst geladen und dann bei der Berechnung des Schnittes wieder verworfen.

Eine Indexstruktur, die Anfragen mit mehr als einem Attribut (beispielsweise „Vorname“ und „Nachname“ gleichzeitig) effizient beantworten kann, heißt mehrdimensional. Dies findet vor allem bei räumlichen Daten Anwendung, beispielsweise in Geoinformationssystemen. Anfragen der Art „Was ist die nächstgelegene Tankstelle?“ oder „Alle Objekte im Rechteck R“ können nicht anhand einer einzelnen Dimension beantwortet werden, sondern erfordern eine Rechtecks-Anfrage in der Indexstruktur. Anfragen nach nur einzelnen Attributen können dann oft immer noch beschleunigt beantwortet werden, indem man das Anfrage-Rechteck so wählt, dass es den Wertebereich der nicht benötigten Attribute vollständig abdeckt.

Geclusterte und nicht geclusterte Indexstrukturen

Eine Indexstruktur heißt geclustert, wenn die Daten physisch genauso sortiert werden, wie sie im Index und in Anfragen benötigt werden. So können Bereichsanfragen effizienter beantwortet werden, während bei sukzessiven Operationen benachbarter Elemente meist dieselben Datenseiten benötigt werden und so gepuffert werden können.

Ein alphabetisch nach dem Familiennamen sortiertes Adressbuch mit eigenen Seiten für jeden Buchstaben entspricht funktionell einem geclusterten Index. Eine Hashtabelle ist normalerweise nicht geclustert; die Daten benachbarter Schlüssel liegen meist in ganz unterschiedlichen Datenseiten. Ein B+-Baum ist ein Beispiel für eine geclusterte Indexstruktur, jede Datenseite entspricht einem disjunkten Intervall des Schlüsselraumes.

Dünn- und dichtbesetzte Indexstrukturen

Eine Indexstruktur heißt dünnbesetzt, wenn sie in ihren Datenstrukturen auch „Lücken“ (d. h. unbesetzte Speicherpositionen) erlaubt. Dünnbesetzte Indexstrukturen belegen daher zusätzlichen Speicher, und bei der Suche müssen solche Positionen übergangen werden. Bei dynamischen Indexstrukturen ist dies jedoch auch ein wichtiger Vorteil: In eine solche Lücke können einfach neue Daten eingefügt werden. Umgekehrt können beim Entfernen von Daten neue Lücken entstehen, ohne dass der Index aufwendig neu organisiert werden muss. Der reduzierte Reorganisationsaufwand ist daher bei sich oft ändernden Daten ein deutlicher Vorteil trotz des erhöhten Speicherverbrauchs und der erhöhten Suchzeit. Viele dünnbesetzte Indexstrukturen erlauben eine dynamische Größenanpassung und versuchen so beispielsweise zu garantieren, dass sie nicht mehr als doppelt so viel Platz belegen wie notwendig.

Eine sortierte Reihe ist ein Beispiel für eine dichtbesetzte Indexstruktur. Hashtabellen und Bäume sind in der Regel dünnbesetzt.

Abwägung

Nachteile von Indexstrukturen sind ein zusätzlicher Verwaltungsaufwand durch die Struktur selbst sowie fallweise ein hoher Speicheraufwand.