Indeksstrukturer

Indeksstrukturer er datastrukturer og metoder som gjør det enklere å finne data i lagrede samlinger ved å gi raske referanser til hvor dataene befinner seg eller hvordan de kan hentes. De brukes i databaser, dokumentlagringssystemer og søkemotorer, og de bidrar til kortere responstider for spørringer, sortering og filtrering.

Vanlige typer inkluderer inverterte indekser, B-trær og B+-trær, hash-indekser og bitmap-indekser. En invertert indeks, sentral i fulltekstsøking, kobler hvert ord eller begrep til en liste over dokumenter som inneholder det. B-trær og spesielt B+-trær organiserer nøkkelverdier og peker til poster, noe som gjør oppslag og rekkeviddeforespørsler effektive for kolonnebasert lagring og relasjonsdatabaser. Hash-indekser gir raske eksakte oppslag på nøkkelverdier, men egner seg dårlig for rekkevidde- eller sorteringsforespørsler. Bitmap-indekser representerer verdier som biter i et eller flere kolonner, og er effektive for kombinasjonsforespørsler i datavarehus og analytiske arbeidsbelastninger med lav kardinalitet.

Indeksene krever ekstra lagringsplass og kostnader for vedlikehold ved innsetting, oppdatering og sletting, fordi de må holdes synkronisert med primærdataene. Valget av indeks avhenger av arbeidsload: om spørringene er hovedsakelig eksakte oppslag, rekkevidde- eller sorteringsforespørsler, eller tekstsøk; hvor ofte data endres; og hvor mye lagringsplass som er tilgjengelig. I praksis bruker mange systemer flere indekser samtidig og lar optimaliseringsmotoren velge bruk av dem i hvert enkelt spørringsløp.

Indeksstrukturer er en grunnleggende komponent i moderne databaser og informasjonsgjenfinning, og deres design reflekterer trade-offs mellom hastighet, lagringsplass og oppdateringskostnader.