Hvordan fungerer et inverteret indeks?

Question

IT Interview Practice · Accepted Answer

**Et inverteret indeks forbinder et ord med de dokumenter, der indeholder det.** Søgemaskinen kan dermed finde kandidater uden at læse alle dokumenter fra ende til anden ved hver søgning.

Tænk på stikordsregisteret bag i en bog: slå et ord op, og gå til de angivne sider. I en søgemaskine erstatter dokument-ID'er sidetallene.

## 1. Begynd med en lille samling

Antag tre dokumenter og en enkel analyzer, som gør tekst til små bogstaver og adskiller ord. En analyzer er trinene, der omdanner tekst til søgbare termer.

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

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

Den oprindelige retning er dokument til ord. Indekset vender den til ord til dokumenter, deraf navnet. Listen over dokumenter for en term kaldes en posting list.

## 2. Brug listerne til forespørgslen

Ved krav om både red og apple læses begge lister, og deres fællesmængde beholdes: D1 findes i begge. Hvis blot én term kræves, tages foreningsmængden: D1, D2 og D3 er kandidater.

Eksemplet forklarer matchning, ikke rangering. Flere match kan scores ud fra termfrekvens og termens udbredelse i samlingen. At finde match og bestemme rækkefølge er relaterede, men adskilte trin.

## 3. Gør indeksering og søgning kompatible

Forespørgslen skal analyseres på en måde, der passer til de indekserede termer. Hvis indeksering ændrer Red til red, men søgningen leder bogstaveligt efter Red, kan det tilsigtede match mistes.

Den rigtige analyse afhænger af feltet. Produktbeskrivelser har gavn af tekstanalyse, mens et præcist ordre-ID normalt kræver eksakt match. Opdeling af ID'er i almindelige ord kan ændre betydningen. Se Elastics forklaring af [fuldtekstsøgning](https://www.elastic.co/docs/solutions/search/full-text/how-full-text-works).

## 4. Gem oplysninger nok til spørgsmålet

Et dokument med både red og apple indeholder ikke nødvendigvis frasen red apple. Frasesøgning behøver ordpositioner for at kontrollere rækkefølge og naboskab.

- Dokument-ID'er angiver, hvilke dokumenter der indeholder termen.
- Frekvenser kan vise, hvor ofte termen forekommer.
- Positioner understøtter spørgsmål om termernes relative placering.

Flere oplysninger giver rigere forespørgsler, men øger indeksstørrelse og indekseringsarbejde. Det nyttige indeks bestemmes af de søgninger, applikationen skal understøtte.

## 5. Forstå prisen for opdatering

Når kildetekst ændres, skal søgeindekset også ændres. Systemer som Elasticsearch organiserer data i segmenter og sammenfletter dem over tid; en opdatering betyder ikke øjeblikkelig omskrivning af alle eksisterende lister på stedet. Synlighed afhænger også af motorens refresh-adfærd.

Medregn derfor ekstra lager, indekseringspris og mulig forsinkelse fra skrivning til søgbarhed. Inverterede indekser er særligt nyttige til termbaseret tekstsøgning; de erstatter ikke universelt indekser til præcise opslag, intervaller eller transaktioner.

1. Begynd med en lille samling

2. Brug listerne til forespørgslen

3. Gør indeksering og søgning kompatible

4. Gem oplysninger nok til spørgsmålet

5. Forstå prisen for opdatering

Relaterede spørgsmål