Indexstruktur

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Indexstrukturen (Index) werden in der Informatik verwendet, um den schnellen Zugriff auf Daten in einer umfangreichen Datenstruktur zu gewährleisten. Daten werden üblicherweise sequentiell auf einem Speichermedium verwaltet. Die Bearbeitung einer Suchanfrage ist dabei mit linearem Aufwand verbunden, da im ungünstigsten Fall der komplette Datenbestand durchsucht werden muss.

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

[Bearbeiten] Bekannte Verfahren

Indexstrukturen sind selbst spezielle Datenstrukturen wie

Hashtabellen
Baum-Strukturen wie Binärbäume, B-Bäume, B*-Baum
Bitmapindex

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 kommen. 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 gross, 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] Bedeutung 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.