Rasti elementą kompiuterio duomenų sąraše gali būti sudėtinga ir atimti daug laiko, todėl buvo sukurta paieškos duomenų struktūra. Paieškos duomenų struktūra yra bet kokia duomenų struktūra, kurioje galima automatiškai ieškoti, nesvarbu, ar tai būtų didelė duomenų bazė, ar mažas sąrašas. Yra du pagrindiniai paieškos struktūrų tipai – statinė ir dinaminė; statinis negali keistis, o dinaminis leidžia keisti. Paieška gali būti brangi operacija, todėl dauguma duomenų struktūrų yra optimizuotos, kad padėtų paieškos funkcijai rasti duomenis. Greitas elementų nustatymas yra akivaizdus šios struktūros pranašumas, tačiau, kadangi tai labai brangu, paieškos funkciją geriausia naudoti esant didelėms struktūroms.
Skirtingai nuo daugelio kitų duomenų struktūrų, paieškos duomenų struktūra gali būti bet kokios rūšies duomenų struktūra. Dominuojanti šios struktūros savybė yra ta, kad vartotojai gali ieškoti struktūroje naudodami užklausą; struktūroje taip pat turi būti bent du elementai sąraše, nors daugumoje struktūrų yra dešimtys, šimtai ar tūkstančiai elementų. Tai reiškia, kad duomenų bazė, sąrašas, eilutė arba dvejetainis medis gali būti laikomi paieškos struktūra.
Paieškos duomenų struktūrą galima suskirstyti į vieną iš dviejų kategorijų: statinę ir dinaminę. Statinė versija nekeičiama, o vartotojai gali ieškoti tik sąraše. Šią struktūrą daug lengviau prižiūrėti, nes naudotojams nereikia jaudintis dėl žymėjimo sistemos keitimo, o paieška paprastai yra paprastesnė. Dinaminės struktūros leidžia vartotojams keisti elementus, juos keičiant arba ištrinant, tačiau juos sunkiau paleisti. Elementai gali keistis taip dažnai, kad turi būti žymėjimo sistema, leidžianti sekti kiekvieno elemento padėtį.
Ieškoti duomenų struktūroje gali kainuoti brangiai, o tai reiškia, kad kompiuteriui gali prireikti daug laiko ir pastangų. Pavyzdžiui, jei duomenų struktūros ieškoma tiesiškai, o elementas yra apačioje, tada užklausa turės peržiūrėti kiekvieną elementą, kol suras tinkamą. Siekiant padėti kompiuteriui, dauguma paieškos duomenų struktūrų optimizuojamos naudojant žymėjimo sistemą ir suskaidant struktūrą į dalis, kad paieškos užklausa galėtų peržiūrėti tinkamą skyrių, o ne visą struktūrą.
Akivaizdi paieškos duomenų struktūros naudojimo nauda yra ta, kad vartotojai gali ieškoti įrašų tol, kol suranda jiems reikalingą konkrečią informaciją. Tuo pačiu metu, kadangi užklausa yra tokia brangi, tai nėra tokia naudinga mažesnėms duomenų struktūroms. Jei duomenų struktūra yra maža ir asmuo gali lengvai jos ieškoti, kompiuteris gali užtrukti ilgiau, kol suras įrašą, nei tuo atveju, jei vartotojas ieškotų rankiniu būdu.