Pronalaženje stavke na popisu računalnih podataka može biti teško i dugotrajno, zbog čega je stvorena struktura podataka pretraživanja. Struktura podataka pretraživanja je svaka struktura podataka koja se može automatski pretraživati, bilo da se radi o velikoj bazi podataka ili malom popisu. Postoje dvije glavne vrste struktura pretraživanja, statičke i dinamičke; statički se ne može promijeniti, dok dinamički dopušta modifikacije. Pretraživanje može biti skupa operacija, pa je većina struktura podataka optimizirana kako bi pomogla funkciji pretraživanja pronaći podatke. Brzo lociranje stavki očita je prednost ove strukture, ali, budući da je tako skupa, funkciju pretraživanja najbolje je koristiti s velikim strukturama.
Za razliku od većine drugih struktura podataka, struktura podataka pretraživanja može biti bilo koja vrsta strukture podataka. Dominantna karakteristika ove strukture je da korisnici mogu pretraživati strukturu putem upita; struktura također mora imati najmanje dvije stavke na popisu, iako većina struktura ima desetke, stotine ili tisuće stavki. To znači da se baza podataka, popis, niz ili binarno stablo mogu kvalificirati kao struktura pretraživanja.
Struktura podataka pretraživanja može se podijeliti u jednu od dvije kategorije: statičku i dinamičku. Statička verzija je nepromjenjiva, a korisnici mogu pretraživati samo popis. Ovu strukturu je mnogo lakše održavati, jer korisnici ne moraju brinuti o promjeni sustava označavanja i pretraživanje je obično lakše. Dinamičke strukture omogućuju korisnicima da mijenjaju stavke, bilo promjenom ili brisanjem, ali ih je teže pokrenuti. Stavke se mogu mijenjati tako često da mora postojati sustav označavanja za praćenje položaja svake stavke.
Pretraživanje strukture podataka može biti skupo, što znači da može potrajati puno vremena i truda za računalo. Na primjer, ako se struktura podataka linearno traži, a stavka je na dnu, onda će upit morati pregledavati svaku stavku dok ne pronađe ispravnu. Kako bi se pomoglo računalu, većina struktura podataka pretraživanja optimizirana je korištenjem sustava označavanja i razbijanjem strukture na odjeljke tako da upit za pretraživanje može pregledavati pravi odjeljak umjesto cijele strukture.
Očigledna prednost korištenja strukture podataka pretraživanja je da korisnici mogu pretraživati zapise dok ne pronađu specifične informacije koje su im potrebne. U isto vrijeme, budući da je upit tako skup, to nije toliko korisno za manje strukture podataka. Ako je struktura podataka mala i osoba je može lako pretraživati, tada će računalu zapravo trebati više vremena da pronađe zapis nego da je korisnik ručno pretraživao.