Kohteen löytäminen tietokoneen tietoluettelosta voi olla vaikeaa ja aikaa vievää, minkä vuoksi hakutietorakenne luotiin. Hakutietorakenne on mikä tahansa tietorakenne, jota voidaan hakea automaattisesti, olipa se sitten suuri tietokanta tai pieni luettelo. Hakurakenteita on kahta päätyyppiä, staattinen ja dynaaminen; staattinen ei voi muuttua, kun taas dynaaminen mahdollistaa muokkaamisen. Haku voi olla kallista, joten useimmat tietorakenteet on optimoitu auttamaan hakutoimintoa löytämään tiedot. Kohteiden nopea paikantaminen on ilmeinen etu tälle rakenteelle, mutta koska se on niin kallista, hakutoimintoa käytetään parhaiten suurissa rakenteissa.
Toisin kuin useimmat muut tietorakenteet, hakutietorakenne voi olla minkä tahansa tyyppinen tietorakenne. Tämän rakenteen hallitseva ominaisuus on, että käyttäjät voivat etsiä rakennetta kyselyn avulla; Rakenteessa on myös oltava vähintään kaksi kohdetta luettelossa, vaikka useimmissa rakenteissa on kymmeniä, satoja tai tuhansia kohteita. Tämä tarkoittaa, että tietokanta, luettelo, merkkijono tai binaaripuu voidaan luokitella hakurakenteeksi.
Hakutietorakenne voidaan jakaa kahteen luokkaan: staattinen ja dynaaminen. Staattista versiota ei voi muuttaa, ja käyttäjät voivat tehdä hakuja vain luettelosta. Tämä rakenne on paljon helpompi ylläpitää, koska käyttäjien ei tarvitse huolehtia kirjanmerkkijärjestelmän muuttamisesta ja etsiminen on yleensä helpompaa. Dynaamisten rakenteiden avulla käyttäjät voivat muokata kohteita joko muuttamalla tai poistamalla niitä, mutta niiden suorittaminen on vaikeampaa. Kohteet voivat muuttua niin usein, että jokaisen kohteen sijainnin seurantaan tarvitaan kirjanmerkkijärjestelmä.
Tietorakenteen etsiminen voi olla kallista, joten se voi viedä paljon aikaa ja vaivaa tietokoneelle. Jos esimerkiksi tietorakennetta etsitään lineaarisesti ja kohde on alareunassa, kyselyn on tarkasteltava jokaista kohdetta, kunnes se löytää oikean. Tietokoneen auttamiseksi useimmat hakutietorakenteet on optimoitu käyttämällä kirjanmerkkijärjestelmää ja jakamalla rakenne osiin, jotta hakukysely voi katsoa oikean osan koko rakenteen sijaan.
Hakutietorakenteen käytön ilmeinen etu on, että käyttäjät voivat etsiä tietueita, kunnes he löytävät tarvitsemansa tiedot. Samaan aikaan, koska kysely on niin kallis, tämä ei ole yhtä hyödyllistä pienemmissä tietorakenteissa. Jos tietorakenne on pieni ja henkilö voi helposti etsiä sitä, tietokoneen tietueen löytäminen voi kestää kauemmin kuin jos käyttäjä tekisi haun manuaalisesti.