Sökhastigheten

Sökhastigheten är ett begrepp som beskriver hur snabbt ett system kan hitta eller lokalisera ett objekt i en samling data eller i en indexstruktur. Den mäts vanligen som tid per uppslag eller som antal behandlade element per tidsenhet, och påverkas av algoritm, datastruktur, lagringsmedia och arbetsbelastning.

Algoritmisk komplexitet ger en teoretisk bild av sökhastigheten. Linjär sökning i en oordnad lista har O(n) tid; binary search i sorterad data har O(log n); hashbaserad uppslagning har i genomsnitt O(1); navigering i en B-träds- eller indexstruktur har ofta O(log n). Praktisk sökhastighet påverkas starkt av minneslokalitet och cachehitrate, särskilt när data bor i minnet eller på sekundära lagringsmedier.

Olika system används: minnesbaserade strukturer som arrayer och hashtabeller erbjuder ofta mycket hög genomsnittlig sökhastighet, medan on-disk data domineras av I/O-kostnader och följer ofta logaritmiska eller bättre än så med avseende på diskens genomströmning, exempelvis via B-träd- eller LSM-trädsindex. Sökhastigheten i text- eller webbindustrin påverkas också av indexering, tokenisering och komprimering.

Mätning och benchmarking används för att jämföra sökhastigheter mellan implementationer. Vanliga mått är latency (tidsfördröjning per uppslag) och throughput (antal uppslag per sekund). Värden varierar med cachevärme, samtidighet, datafördelning och hårdvara.

Praktiska överväganden inkluderar avvägningar mellan hastighet, minnesanvändning och uppdateringskostnader. Hashbaserade uppslag är snabba men kräver bra hashfunktion och hantering av kollisioner; uppdateringar i vissa indexstrukturer kan vara kostsamma; ordning och sorterade uppslag kräver ofta mer arbete vid uppdateringar men möjliggör effektiva intervallfrågor.