6.1 Allgemeines zum Suchen

Suchen gehört zu den häufigsten Aufgaben, die Computer im Alltag übernehmen – ob beim Auffinden von Internetadressen, Telefonnummern, Artikeln oder Dateien. Suchalgorithmen spielen daher eine zentrale Rolle in der Informatik.

Grundsätzlich unterscheidet man beim Suchen nach dem Zustand der Daten, die durchsucht werden sollen. Es ergeben sich dabei drei typische Situationen:

• Die Daten sind unsortiert.
• Die Daten sind einfach sortiert (z. B. alphabetisch oder numerisch aufsteigend).
• Die Daten sind suchfreundlich strukturiert, z. B. in einem binären Suchbaum.

Sind die Daten nicht sortiert, bleibt nur die lineare Suche (auch sequentielle Suche genannt). Dabei werden die Elemente nacheinander durchsucht – beginnend beim ersten Eintrag, bis entweder das gesuchte Element gefunden oder das Ende der Daten erreicht ist.

6.1.1 Beispiele aus dem Alltag

Beispiel 1:

Stellen Sie sich vor, Sie haben eine neue Stelle als Hausmeister in einer Schule angetreten. Ihren Vorgänger musste man entlassen, weil er keine Ordnung halten konnte. Zunächst glauben Sie das nicht, aber als Sie vor das Schlüsselbrett im Hausmeisterraum treten, wird Ihnen das plötzlich klar: Alle Schlüssel hängen dort wild durcheinander am Brett, völlig unsortiert. Wenn Sie jetzt einen bestimmten Schlüssel suchen wollen, müssen Sie links oben anfangen und jeden Schlüssel ausprobieren, ob er passt. Irgendwann, nach 10 oder 11 Versuchen (wenn Sie Glück haben) finden Sie den passenden Schlüssel schließlich.

Das Bild wurde von ChatGPT erstellt.

Beispiel 2:

Sie haben von Ihrem Vater eine große Platten-Sammlung geerbt. Ihr Vater war - im Gegensatz zu dem entlassenen Hausmeister - sehr ordentlich. Natürlich hat er seine Platten-Sammlung gut sortiert, und zwar exakt nach dem Kaufdatum. Die ältesten Platten stehen in einem Kasten ganz oben links im Regel, die neuesten Platten ganz rechts unten.

Sie wollen nun schauen, ob auch eine alte Platte von The Luftschiff dabei ist, einer Rockgruppe, von der Sie von Ihren Freunden nur Gutes gehört haben. Wo fangen Sie an mit der Suche? Natürlich ganz vorne, denn die ersten Platten von The Luftschiff sind schon 1964 erschienen, als Ihr Vater anfing, Platten zu sammeln. Es könnte aber auch sein, dass er die Platte erst kurz vor seinem Tod im Jahre 2024 gekauft hat.

Obwohl die Plattensammlung hoch geordnet ist, müssen Sie hier eine sequentielle Suche durchführen, da das Ordnungssystem nicht Ihrem Suchkriterium entspricht.

Sind die zu durchsuchenden Daten aber so sortiert, dass das Ordnungssystem ihren Suchkriterienb entspricht, kann man viel bessere Suchverfahren einsetzen.

Beispiel 3:

Das Bild wurde von ChatGPT erzeugt

Sie stehen vor dem Bücherregal, in dem Sie all die Romane aufbewahren, die Sie seit Jahren gesammelt haben. Die Romane sind alphabetisch nach Autor bzw. Autorin geordnet. Sie wollen nun ein Buch von Karl Melcher lesen. Dann werden Sie sicherlich nicht oben links im Regal bei "A" anfangen zu suchen, aber auch nicht unten rechts bei "Z", sondern werden gezielt irgendwo in der Mitte des Regals mit der Suche anfangen.

Dieses Beispiel soll zeigen, dass eine Suche erheblich schneller verläuft, wenn das Ordnungs-Kriterium mit dem Such-Kriterium übereinstimmt.

Wären die Bücher unsortiert oder nach Kaufdatum in das Regal einsortiert gewesen, hätten Sie eine lineare bzw. sequentielle Suche durchführen müssen.

Dieses Beispiel sollte zeigen, wie sinnvoll es ist, Daten nach bestimmten Kriterien zu sortieren. Darum haben wir in der letzten Folge ja auch die verschiedenen Sortierverfahren ausführlich besprochen.

6.1.2 Indexdateien (Fallbeispiel)

Nehmen wir einmal an, dass in einer großen Datenbank alle 18 Millionen Personaldaten eines Bundeslandes wie Nordrhein-Westfalen gespeichert sind.

Wenn nun jemand nach dem Namen "Helmich" sucht, werden selbstverständlich nicht alle 18 Millionen Datensätze durchsucht. Selbst eine binäre Suche (siehe Folge 6.3) wäre hier nicht praktikabel, da sie voraussetzt, dass die gesamte Datenmenge bereits nach Namen sortiert vorliegt – und selbst dann wäre der Zugriff auf die riesigen Datensätze unnötig aufwendig.

Große Datenbanken arbeiten daher mit sogenannten Indexdateien. Eine solche Indexdatei funktioniert ähnlich wie das Stichwortverzeichnis eines Buches: Man liest nicht jede Seite, sondern schlägt im Register nach. Dort sind die Begriffe alphabetisch sortiert - zusammen mit den Seitenzahlen.

Übertragen auf eine Personendatenbank bedeutet das:

• Zu jedem Datensatz existiert ein Eintrag in einer Indexdatei.
• Ein Namensindex enthält z. B. Nachname, Vorname und einen Verweis auf den eigentlichen Datensatz.
• Andere Indexdateien können nach Postleitzahlen oder Geburtsdaten sortiert sein.

Wird nun nach "Helmich" gesucht, durchsucht das System nicht die Hauptdatenbank, sondern zunächst den Namensindex. Dort kann der gesuchte Eintrag sehr schnell gefunden werden, etwa mithilfe einer binären Suche oder einer geeigneten Baumstruktur. Erst danach greift das System gezielt auf die zugehörigen Datensätze zu.

Da es mehrere Personen mit demselben Nachnamen geben kann, wird innerhalb dieser kleineren Treffermenge weitergesucht – aber nicht mehr innerhalb aller 18 Millionen Datensätze.

Wird dagegen nach einem Geburtsdatum gesucht, verwendet das System den entsprechenden Geburtsdaten-Index.

Interessant wird es bei kombinierten Suchanfragen, etwa: "Nachname 'Helmich' und Geburtsdatum 1.1.1991".

In einfachen Systemen existiert hierfür kein kombinierter Index. Man kann dann zwar mithilfe des Geburtsdatums-Index zur passenden Teilmenge springen, muss innerhalb dieser Gruppe jedoch sequenziell weiter prüfen, ob auch der Nachname passt.

Vorteile von Indexdateien

Indexdateien reduzieren den Suchraum drastisch. Statt 18 Millionen Datensätze zu prüfen, wird zunächst nur eine speziell strukturierte, deutlich kleinere Indexmenge durchsucht. Der Suchaufwand sinkt dadurch von einer linearen Suche über Millionen Einträge auf wenige, sehr schnelle Vergleichsschritte.