Vad är en sökdatadruktur?
Att hitta ett objekt i en datadatallista kan vara svårt och tidskrävande, varför sökdatastrukturen skapades. En sökdatastruktur är varje datastruktur som automatiskt kan sökas, vare sig det är en stor databas eller en liten lista. Det finns två huvudtyper av sökstrukturer, statiska och dynamiska; statisk kan inte ändras, medan dynamisk tillåter modifiering. Sökning kan vara en kostsam operation, så de flesta datastrukturer är optimerade för att hjälpa sökfunktionen att hitta data. Att hitta objekt snabbt är en uppenbar fördel med denna struktur men eftersom den är så kostsam används sökfunktionen bäst med stora strukturer.
Till skillnad från de flesta andra datastrukturer kan en sökdatastruktur vara vilken typ av datastruktur som helst. Det dominerande kännetecknet för denna struktur är att användare kan söka igenom strukturen via en fråga; strukturen måste också ha minst två objekt i en lista, även om de flesta strukturer har tiotals, hundratals eller tusentals artiklar. Detta innebär att en databas, lista, sträng eller binärt träd kan betecknas som en sökstruktur.
En sökdatastruktur kan delas upp i en av två kategorier: statisk och dynamisk. Den statiska versionen är oföränderlig och användare kan bara söka i listan. Den här strukturen är mycket lättare att underhålla, eftersom användare inte behöver oroa sig för att ändra bokmärkesystemet och att sökningen vanligtvis är enklare. Dynamiska strukturer tillåter användare att ändra objekt, antingen genom att ändra eller genom att ta bort dem, men de är svårare att köra. Objekt kan ändras så ofta att det måste finnas ett bokmärkesystem för att hålla reda på varje objekts position.
Att söka igenom en datastruktur kan vara kostsamt, vilket innebär att det kan ta mycket tid och ansträngning för datorn. Till exempel, om en datastruktur söks linjärt och objektet ligger längst ner, måste frågan titta igenom varje objekt tills den hittar rätt. För att hjälpa datorn optimeras de flesta sökdatastrukturer genom att använda ett bokmärkesystem och genom att dela strukturen upp i sektioner så att sökfrågan kan titta igenom rätt sektion istället för hela strukturen.
Den uppenbara fördelen med att använda en sökdatastruktur är att användare kan söka i poster tills de hittar den specifika information de behöver. På samma gång, eftersom frågan är så kostsam, är detta inte lika fördelaktigt för mindre datastrukturer. Om datastrukturen är liten och enkelt kan sökas av en person kan det faktiskt ta längre tid för datorn att hitta en post än om en användare gjorde sökningen manuellt.