Such- und Sortiervorgänge sind sehr häufige Aufgaben die in Anwendungen gelöst werden müssen. Suchen ist ein Vorgang der komplementär zum Sortieren ist. Datenbestände die vollständig oder teilweise sortiert sind, lassen sich wesentlich einfacher durchsuchen. Ungeordnete Datenbestände lassen sich lassen sich im schlechtesten Fall nur linear durchsuchen. Suchvorgänge lassen wie folgt kategorisieren: Suchkriterium: Das gesuchte Objekt (Datum) unterscheidet sich durch eine eindeutiges Merkmal von allen anderen Daten. Das Merkmal kann aus einem einzelnen Attribut oder mehreren Attribute bestehen. Das Merkmal wird auch als Suchschlüssel bezeichnet. Suchauftrag: Die Suche eines bestimmten Datums in einer Menge von Daten. Suchziel: Der Zugriff auf das gesuchte Datum (Objekt).

Internes und externes Suchen

Man unterscheidet zwischen Suchvorgängen bei denen man den gesamten Datenbestand im Hauptspeicher verwalten kann (internes Suchen) und Suchvorgängen bei denen der Datenbestand nur teilweise in den Hauptspeicher geladen werden kann(externes Suchen).

Beim externen Suchen muss man also einen schnellen, aber begrenzten Hauptspeicher geschickt einsetzen um einen langsamen, aber kostengünstigeren Massenspeicher zu durchsuchen.

Die Unterscheidung zwischen den beiden Suchverfahren ist sehr wichtig für produktiv eingesetzte Anwendungen, in der Berechung der Zeitaufwände ist sie nicht hilfreich!

Ein Festplattenspeicher mag etwa 1000 mal langsamer als der Hauptspeicher eines Rechners sein. Dies macht bei einer echten Anwendung einen großen Unterschied. Bei der Berechnung der Zeitkomplexität wird dieser Faktor jedoch als "unbedeutend" weggekürzt.

Suchverfahren