12.4 Indexsuche

Grundidee

Im Grunde handelt es sich bei der Indexsuche ebenfalls um eine Art Sprungsuche. Allerdings wird hier nicht mit einer konstanten Sprungweite durch das Array gesprungen, sondern es wird vorher ein Index-Array erzeugt, in dem bestimmte Indizes des Haupt-Arrays gespeichert werden, die dann bei der eigentlichen Suche der Reihe nach angesprungen werden

Betrachten wir dazu das folgende Bild:

Schema zur Indexsuche
Autor: Ulrich Helmich 2026, Lizenz: Public domain.

Das zu durchsuchende Array besteht aus 30 aufsteigend sortierten int-Zahlen im Bereich zwischen 3 und 107.

Nun werden die Positionen herausgesucht und in dem Index-Array gespeichert, an denen zum ersten Mal eine Zahl >= 20, >= 40, >= 60, >= 80 und >= 100 im Haupt-Array vorkommt. Das sind in unserem Beispiel die Positionen 9, 13, 20, 23 und 26 im Haupt-Array.

Das Index-Array besteht dann aus fünf Elementen, in denen die folgenden Zahlen gespeichert sind:

9 - 13 - 20 - 23 - 26

Suchvorgang

Beispiel 1

Wir wollen jetzt die Zahl 57 suchen. Diese Zahl erfüllt die Bedingung >= 40. Daher wird im Index-Array nachgeschaut, an welcher Position im Haupt-Array die Zahlen >= 40 beginnen. Im Index-Array finden wir den Index 13.

Also beginnen wir mit der sequentiellen Suche im Haupt-Array an Index 13. Dort finden wir die Zahl 45, dann die 48, die 51, die 54, die 55 und dann die 58. Die 57 haben wir offensichtlich nicht gefunden.

Schema zur Indexsuche
Autor: Ulrich Helmich 2026, Lizenz: Public domain.

Beispiel 2

Jetzt wollen wir nach der Zahl 95 suchen. Die Bedingung >= 80 ist erfüllt, also schauen wir im Index-Array an Position 3 nach, welche Zahl dort steht. Wir finden die Zahl 23. Das ist jetzt der Index des Haupt-Arrays, an dem wir mit der sequentiellen Suche beginnen: 81, 95. Nach zwei Vergleichen haben wir die Suchzahl 95 gefunden.

Ein Beispiel aus dem Alltag

Angenommen, Sie haben auf ihrem Handy 314 verschiedene Kontakte gespeichert. Wenn Sie nun mit ihrer Freundin Lisa telefonieren möchten, tippen Sie einfach den Buchstaben "L" ein, und sofort springt die App zu den Namen, die mit "L" anfangen. Ab hier suchen Sie dann sequentiell nach "Lisa".

Wann ist eine Indexsuche sinnvoll?

Es müssen mehrere Bedingungen erfüllt sein, damit eine solche Indexsuche überhaupt sinnvoll ist.

1. Das zu durchsuchende Array muss relativ groß sein und aus Tausenden oder gar Millionen Elementen bestehen. Bei kleinen Arrays lohnt sich der Aufwand für die Erzeugung des Index-Arrays nicht.
2. Wegen der linearen Struktur des Haupt-Arrays sollten Einfüge- und Lösch-Operationen möglichst wenig vorkommen. Nach jeder dieser Operationen muss nämlich das Index-Array neu aufgebaut werden. Bei Datensammlungen, die groß sind und nur selten aktualisiert werden, könnte eine Indexsuche durchaus sinnvoll sein. Ein Beispiel, das in der Fachliteratur oft genannt wird, sind Telefonbücher oder -verzeichnisse, Postleitzahlen-Verzeichnisse, Wörterbücher etc.
3. Der Aufbau eines Index-Arrays lohnt sich nur, wenn im Haupt-Array sehr oft gesucht wird. Wird nur sehr selten eine Suche durchgeführt, ist der Aufbau des Index-Arrays ein unnötiger Aufwand.
4. Die Indexsuche funktioniert ähnlich wie die Sprungsuche am besten, wenn die Elemente in dem Haupt-Array möglichst gleichmäßig verteilt sind.

Die Indexsuche war übrigens lange Zeit das Standardverfahren, als man noch mit Magnetbändern oder ähnlichen Datenträgern arbeitete (sequentielle Dateien). In der Index-Datei waren dann die Adressen bestimmter Datensätze auf dem Magnetband gespeichert, so dass man nicht das ganze Magnetband von vorne bis hinten durchsuchen musste, sondern gleich zu einer geeigneten Startposition vorspulen konnte.

Indexsuche in Datenbanken

Große Datenbanken können viele Millionen Datensätze enthalten. Jeder dieser Datensätze kann wiederum zahlreiche Informationen umfassen. Häufig besitzt jeder Datensatz eine eindeutige Kennung, beispielsweise eine Kundennummer, eine Versicherungsnummer oder eine Artikelnummer. Eine solche Kennung wird in Datenbanken auch als Primärschlüssel bezeichnet.

Um einen bestimmten Datensatz möglichst schnell zu finden, kann die Datenbank einen Index verwenden. Dieser enthält die Schlüsselwerte und Informationen darüber, wo die zugehörigen Datensätze gespeichert sind. Wird beispielsweise nach einem Kunden mit einer bestimmten Kundennummer gesucht, muss die Datenbank nicht sämtliche Datensätze nacheinander durchsuchen. Stattdessen wird zunächst der wesentlich kleinere Index durchsucht. Sobald der gesuchte Schlüssel gefunden wurde, kann die Datenbank gezielt auf den entsprechenden Datensatz zugreifen.

Bei großen Datenbanken verwendet man für solche Indizes normalerweise keine einfachen Arrays, sondern spezielle Datenstrukturen, die eine besonders effiziente Suche ermöglichen. Dazu gehören vor allem B-Bäume. Diese Baumstrukturen sind so organisiert, dass auch bei Millionen von Datensätzen nur wenige Suchschritte und Speicherzugriffe notwendig sind.

Die grundlegende Idee ist jedoch dieselbe wie bei der einfachen Indexsuche: Anstatt den gesamten Datenbestand zu durchsuchen, sucht man zunächst in einer kleineren, speziell dafür angelegten Indexstruktur.

Optimierungen

1. Die Zahl der Partitionen könnte erhöht werden. Das würde einerseits die Suche im Haupt-Array beschleunigen, andererseits aber die Suche nach dem Einstiegs-Index verlangsamen, da das Index-Array größer würde.
2. Das Suchverfahren innerhalb der Partitionen könnte verbessert werden. Wir haben bei unserem Beispiel eine schlichte sequentielle Suche verwendet. Man könnte innerhalb einer Partition aber auch binär suchen, was die Suchzeit noch einmal stark beschleunigen würde.
3. Das Index-Array ist linear aufgebaut. Würde man es durch einen binären Suchbaum oder einen B-Baum ersetzen, könnte man den ersten Teil der Suche noch stark beschleunigen.