Wie funktioniert ein invertierter Index?

Question

IT Interview Practice · Accepted Answer

**Ein invertierter Index ordnet einem Begriff die Dokumente zu, die ihn enthalten.** So findet eine Suchmaschine Kandidaten, ohne bei jeder Suche jedes Dokument vollständig zu lesen.

Denken Sie an ein Stichwortverzeichnis im Buch: Wort nachschlagen und genannte Seiten aufrufen. Dokumentkennungen ersetzen bei der Suche die Seitenzahlen.

## 1. Beginnen Sie mit einer kleinen Sammlung

Wir haben drei Dokumente und einen einfachen Analyzer, der Text kleinschreibt und Wörter trennt. Ein Analyzer ist die Folge von Schritten, die Text in suchbare Begriffe umwandelt.

```text
D1: Red apple
D2: Green apple
D3: Red car

apple -> D1, D2
car   -> D3
green -> D2
red   -> D1, D3
```

Ursprünglich führt die Richtung vom Dokument zu Wörtern. Der Index dreht sie um: vom Wort zu Dokumenten. Daher der Name. Die Dokumentliste eines Begriffs heißt Posting List.

## 2. Beantworten Sie Abfragen mit Listen

Für red und apple gemeinsam lesen Sie beide Listen und bilden den Schnitt: D1 ist in beiden. Genügt einer der Begriffe, ergibt die Vereinigung D1, D2 und D3.

Das erklärt Trefferfindung, nicht Rangfolge. Mehrere Treffer lassen sich anhand von Begriffshäufigkeit und Verbreitung in der Sammlung bewerten. Treffer finden und sortieren sind verwandte, aber getrennte Schritte.

## 3. Stimmen Sie Indexierung und Suche ab

Die Anfrageanalyse muss zu den gespeicherten Begriffen passen. Wird Red beim Indexieren zu red, sucht die Anfrage aber wörtlich Red, kann der erwartete Treffer fehlen.

Die passende Analyse hängt vom Feld ab. Produktbeschreibungen profitieren von Textanalyse, genaue Bestellkennungen brauchen meist exakte Übereinstimmung. Das Zerlegen einer Kennung in gewöhnliche Wörter kann ihre Bedeutung verändern. Siehe Elastics Erklärung zur [Volltextsuche](https://www.elastic.co/docs/solutions/search/full-text/how-full-text-works).

## 4. Speichern Sie genug Informationen für die Frage

Ein Dokument mit red und apple enthält nicht zwingend die Phrase red apple. Phrasensuche benötigt Wortpositionen zur Prüfung von Reihenfolge und Nachbarschaft.

- Dokumentkennungen beantworten, welche Dokumente den Begriff enthalten.
- Häufigkeiten beschreiben die Zahl der Vorkommen.
- Positionen unterstützen Fragen nach relativen Begriffslagen.

Mehr Informationen ermöglichen reichere Abfragen, vergrößern aber Index und Indexierungsaufwand. Die benötigten Sucharten bestimmen den nützlichen Index.

## 5. Verstehen Sie die Aktualisierungskosten

Bei geändertem Quelltext muss der Suchindex angepasst werden. Systeme wie Elasticsearch verwalten Segmente und führen sie später zusammen; ein Update schreibt nicht sofort jede vorhandene Posting List an Ort und Stelle neu. Suchsichtbarkeit hängt auch vom Refresh ab.

Berücksichtigen Sie zusätzlichen Speicher, Indexierungsaufwand und mögliche Verzögerung zwischen Schreiben und Finden. Ein invertierter Index eignet sich besonders für begriffsbasierte Textsuche, ersetzt aber nicht alle Indizes für exakte Zugriffe, Bereiche oder Transaktionen.

1. Beginnen Sie mit einer kleinen Sammlung

2. Beantworten Sie Abfragen mit Listen

3. Stimmen Sie Indexierung und Suche ab

4. Speichern Sie genug Informationen für die Frage

5. Verstehen Sie die Aktualisierungskosten

Ähnliche Fragen