Hva er en søkedatastruktur?

Det kan være vanskelig og tidkrevende å finne et element i en datamaskin dataliste, og det er grunnen til at søkedatastrukturen ble opprettet. En søkedatasstruktur er en hvilken som helst datastruktur som kan søkes automatisk, det være seg en stor database eller en liten liste. Det er to hovedtyper av søkestrukturer, statiske og dynamiske; statisk kan ikke endres, mens dynamisk tillater endring. Å søke kan være en kostbar operasjon, så de fleste datastrukturer er optimalisert for å hjelpe søkefunksjonen med å finne dataene. Å finne gjenstander raskt er en åpenbar fordel for denne strukturen, men siden det er så kostbart, er søkefunksjonen best brukt med store strukturer.

I motsetning til de fleste andre datastrukturer, kan en søkedatasstruktur være hvilken som helst type datastruktur. Det dominerende kjennetegnet ved denne strukturen er at brukere kan søke gjennom strukturen via en spørring; strukturen må også ha minst to elementer i en liste, selv om de fleste strukturer har titalls, hundrevis eller tusenvis av elementer. Dette betyr at en database, liste, streng eller binært tre kan kvalifisere som en søkestruktur.

En søkedatasstruktur kan deles inn i en av to kategorier: statisk og dynamisk. Den statiske versjonen er uforanderlig, og brukere kan bare søke i listen. Denne strukturen er mye enklere å vedlikeholde, fordi brukere ikke trenger å bekymre seg for å endre bokmerkesystemet og det er vanligvis enklere å søke. Dynamiske strukturer lar brukerne endre elementer, enten ved å endre eller ved å slette dem, men de er vanskeligere å kjøre. Elementer kan endres så ofte at det må være et bokmerke-system for å holde oversikt over posisjonen til hvert element.

Å søke gjennom en datastruktur kan være kostbart, noe som betyr at det kan ta mye tid og krefter for datamaskinen. For eksempel, hvis en datastruktur blir søkt lineært og elementet er i bunnen, blir spørringen nødt til å se gjennom hvert element til den finner den riktige. For å hjelpe datamaskinen optimaliseres de fleste søkedatastrukturer ved å bruke et bokmerke-system og ved å dele strukturen opp i seksjoner slik at søket kan se gjennom den rette delen i stedet for hele strukturen.

Den åpenbare fordelen med å bruke en søkedatastruktur er at brukere kan søke i poster til de finner den spesifikke informasjonen de trenger. På grunn av spørringen er så kostbar, er dette ikke like gunstig for mindre datastrukturer. Hvis datastrukturen er liten og lett kan søkes av en person, kan det faktisk ta lengre tid før datamaskinen finner en registrering enn om en bruker gjorde søket manuelt.