Indexstruktur
aus Wikipedia, der freien Enzyklopädie
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.
Inhaltsverzeichnis |
[Bearbeiten] Bekannte Verfahren
Indexstrukturen sind selbst spezielle Datenstrukturen wie
Für besondere Anforderungen gibt es auch spezielle Indexstrukturen. Beispielsweise verwenden Geodatenbanken zum Indizieren von mehrdimensionalen Daten R-Bäume. Diese Bäume erlauben mehrdimensional Suchkriterien.
- Gridfile, k-d-Baum, k-d-b-Baum, R-Baum, UB-Baum für mehrdimendionale Datenstrukturen
[Bearbeiten] Funktionsprinzip an einem Beispiel
Typischerweise funktionieren Indexstrukturen nach dem Prinzip Teile und Herrsche. Ähnlich zu einem Karteikarten-System, kann eine Menge von Adressen so unterteilt werden, dass anhand des Suchkriteriums nur eine bestimmte Teilmenge aller Adressen in Frage kommt. Eine solche Unterteilung wäre zum Beispiel über den Anfangsbuchstaben möglich. Wird der Name "Müller" gesucht, muss lediglich die Teilmenge, die mit "M" anfängt, durchsucht werden. Ist diese Teilmenge noch immer zu groß, können die Teilmengen über den zweiten oder dritten Buchstaben weiter verfeinert 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.
[Bearbeiten] Verwendung in der Datenbanktechnik
Indexstrukturen haben eine besondere Bedeutung in Datenbanken. Da hier besonders große Datenmengen verarbeitet werden müssen, 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.
[Bearbeiten] Ein- und mehrdimensionale Indexstrukturen
Ein Element in der Indexstruktur werde anhand einer Attributmenge S mit | S | > 1 indiziert. Eine Indexstuktur heißt mehrdimensional, wenn sie auch eine Indizierung von Elementen anhand einer Attributmenge 
ermöglicht. Ansonsten heißt sie eindimensional.
Mehrdimensionale Zugriffsstrukturen sind speziell in Datenbanksystemen von Bedeutung. Sie ermöglichen beispielsweise, dass ein über mehrere Attribute aufgespannter Index des Primärschlüssels gleichzeitig eine effiziente Suche von Elementen anhand einzelner Attribute erlaubt. In einer Relation Einwohner mit Primärschlüsseln über { Vorname, Nachname, Geburtsdatum } wäre so auch das effiziente Auflisten aller Personen möglich, die in einem bestimmten Jahr geboren sind.
Eine beliebte mehrdimensionale Indexstruktur sind Gridfiles.
[Bearbeiten] Geclusterte und nicht geclusterte Indexstrukturen
Eine Indexstruktur heißt geclustert, wenn die Reihenfolge der Elemente in der Indexstruktur dieselbe ist wie im Speicher, der die Elemente enthält. So können Elemente zum Beispiel nach Größe sortiert im Speicher abgelegt sein, was ein effizientes sortiertes Auflisten von Elementen ermöglicht.
[Bearbeiten] Dünn- und dichtbesetzte Indexstrukturen
Eine Indexstruktur heißt dünnbesetzt, falls nicht jedes zu indizierende Element einen Eintrag in der Indexstruktur besitzt. Ermöglicht wird dies durch geclusterte Speicherung der Elemente. Das Auffinden eines Elementes läuft dann wie folgt ab: Über die Indexstruktur wird das größte Element gesucht, dessen Schlüssel kleiner ist als das aufzufindende. Von diesem Element an werden die Datensätze anschließlich unter Verwendung von linearer Suche durchlaufen, bis das richtige Element gefunden wurde.
[Bearbeiten] Dynamische und statische Indexstrukturen
Eine Indexstruktur heißt dynamisch, falls sie ihre Struktur der Anzahl zu indizierender Elemente anpasst. Ansonsten wird sie als statisch bezeichnet.
Ein typisches Beispiel für eine statische Indexstruktur ist die Hashtabelle und für eine dynamische Indexstruktur der B*-Baum. Die Baumtiefe wird hier automatisch der Datenmenge angepasst.
[Bearbeiten] Abwägung
Nachteile von Indexstrukturen sind ein zusätzlicher Verwaltungsaufwand durch die Struktur selbst, sowie fallweise ein hoher Speicheraufwand.
