Iskanje elementa na seznamu računalniških podatkov je lahko težko in dolgotrajno, zato je bila ustvarjena struktura podatkov za iskanje. Iskalna podatkovna struktura je katera koli podatkovna struktura, ki jo je mogoče samodejno iskati, naj bo to velika zbirka podatkov ali majhen seznam. Obstajata dve glavni vrsti iskalnih struktur, statična in dinamična; statično se ne more spremeniti, medtem ko dinamično omogoča spreminjanje. Iskanje je lahko draga operacija, zato je večina podatkovnih struktur optimiziranih za pomoč iskalni funkciji pri iskanju podatkov. Hitro lociranje predmetov je očitna prednost te strukture, a ker je tako draga, je funkcijo iskanja najbolje uporabiti pri velikih strukturah.
Za razliko od večine drugih podatkovnih struktur je lahko iskalna podatkovna struktura katera koli vrsta podatkovne strukture. Prevladujoča značilnost te strukture je, da lahko uporabniki iščejo po strukturi prek poizvedbe; struktura mora imeti tudi vsaj dva elementa na seznamu, čeprav ima večina struktur na desetine, stotine ali tisoče elementov. To pomeni, da se baza podatkov, seznam, niz ali binarno drevo lahko kvalificira kot iskalna struktura.
Podatkovno strukturo iskanja lahko razdelimo v eno od dveh kategorij: statično in dinamično. Statična različica je nespremenljiva, uporabniki pa lahko iščejo samo po seznamu. To strukturo je veliko lažje vzdrževati, saj uporabnikom ni treba skrbeti za spreminjanje sistema zaznamkov in je iskanje običajno lažje. Dinamične strukture uporabnikom omogočajo spreminjanje elementov s spreminjanjem ali brisanjem, vendar jih je težje izvajati. Predmeti se lahko spreminjajo tako pogosto, da mora obstajati sistem zaznamkov za spremljanje položaja vsakega predmeta.
Iskanje po strukturi podatkov je lahko drago, kar pomeni, da lahko za računalnik vzame veliko časa in truda. Na primer, če se podatkovna struktura išče linearno in je postavka na dnu, bo morala poizvedba pregledati vsak element, dokler ne najde pravilnega. Za pomoč računalniku je večina iskalnih podatkovnih struktur optimizirana z uporabo sistema zaznamkov in z razčlenitvijo strukture na odseke, tako da lahko iskalna poizvedba pogleda skozi desni odsek namesto celotne strukture.
Očitna prednost uporabe iskalne podatkovne strukture je, da lahko uporabniki iščejo zapise, dokler ne najdejo posebnih informacij, ki jih potrebujejo. Hkrati, ker je poizvedba tako draga, to ni tako koristno za manjše podatkovne strukture. Če je podatkovna struktura majhna in jo lahko oseba zlahka išče, lahko dejansko traja dlje, da računalnik najde zapis, kot če bi uporabnik iskal ročno.