Skippunkter

Skippunkter är extra referenser i en datastruktur som gör det möjligt att hoppa över ett antal element vid sök eller traversal. De används för att accelerera genomgång av stora datamängder, till exempel i länkade listor, indexstrukturer och sökalgoritmer.

Den mest kända tillämpningen är i skip lists, där varje element har flera framåtriktade pekare i olika nivåer. Genom att hoppa mellan nivåerna kan sökningen undvika att jämföra varje enskilt element och i genomsnitt uppnå logaritmisk tidskomplexitet. En enklare variant av skippunkter är att lägga till en pekare var n:e nod i en vanlig länkad lista, så att sökningen kan hoppa framåt i större steg och sedan fortsätta där den slutade.

Användningsområden inkluderar textindex, databaser och informationssökning där snabb åtkomst till positioner i dokument eller mellan förekomster krävs. I textsökning används skippunkter ofta för att snabbare lokalisera block av text eller mellan förekomster i ett index.

Fördelar innefattar snabbare sökningar och bättre prestanda i stora datastrukturer, medan nackdelar inkluderar ökad minnesanvändning samt komplexitet vid insättning och borttagning av element, eftersom skippunkter måste underhållas.

Historik och relaterade begrepp: begreppet förekommer i flera sammanhang inom datalagring. Skip lists, som populariserades av William Pugh 1990, illustrerar hur flera nivåer av pekare skapar en effektiv balans mellan snabbhet och minnesanvändning. Andra relaterade metoder inkluderar blockbaserad indexing och landmärken inom informationssökning.