Datenstruktur für effiziente Suche

Datenmodell-Verfeinerung:

Eine Tabelle (map, assoziatives Feld) soll so realisiert werden, dass die Suche nach einem Schlüssel in der Zeit linear von der Länge des Schlüssels abhängt, aber unabhängig von der Anzahl der Elemente in der Tabelle ist.

Bei fester Schlüssellänge kann also eine konstante Laufzeit garantiert werden.

Diese Struktur ist insbesondere geeignet für eine Präfix-Suche, d.h. für eine Suche bei der nur ein Anfangsstück des Schlüssels bekannt ist. Daher kann sie auch in der Fallstudie zur Freitextsuche sehr gut verwendet werden.