Trovare un elemento in un elenco di dati del computer può essere difficile e richiedere molto tempo, motivo per cui è stata creata la struttura dei dati di ricerca. Una struttura di dati di ricerca è qualsiasi struttura di dati che può essere ricercata automaticamente, sia essa un grande database o un piccolo elenco. Esistono due tipi principali di strutture di ricerca, statiche e dinamiche; statico non può cambiare, mentre dinamico consente la modifica. La ricerca può essere un’operazione costosa, quindi la maggior parte delle strutture dati è ottimizzata per aiutare la funzione di ricerca a trovare i dati. L’individuazione rapida degli elementi è un ovvio vantaggio di questa struttura ma, poiché è così costosa, la funzione di ricerca viene utilizzata al meglio con strutture di grandi dimensioni.
A differenza della maggior parte delle altre strutture dati, una struttura dati di ricerca può essere qualsiasi tipo di struttura dati. La caratteristica dominante di questa struttura è che gli utenti possono effettuare ricerche all’interno della struttura tramite una query; la struttura deve anche avere almeno due elementi in un elenco, sebbene la maggior parte delle strutture abbia decine, centinaia o migliaia di elementi. Ciò significa che un database, un elenco, una stringa o un albero binario può essere qualificato come struttura di ricerca.
Una struttura di dati di ricerca può essere suddivisa in una delle due categorie: statica e dinamica. La versione statica non è modificabile e gli utenti possono solo eseguire ricerche nell’elenco. Questa struttura è molto più facile da mantenere, perché gli utenti non devono preoccuparsi di cambiare il sistema di bookmarking e la ricerca è in genere più semplice. Le strutture dinamiche consentono agli utenti di modificare gli elementi, modificandoli o eliminandoli, ma sono più difficili da eseguire. Gli elementi possono cambiare così frequentemente che deve essere presente un sistema di segnalibri per tenere traccia della posizione di ogni elemento.
La ricerca in una struttura di dati può essere costosa, il che significa che può richiedere molto tempo e fatica per il computer. Ad esempio, se si esegue una ricerca lineare in una struttura di dati e l’elemento è in fondo, la query dovrà esaminare ogni elemento finché non trova quello corretto. Per aiutare il computer, la maggior parte delle strutture di dati di ricerca sono ottimizzate utilizzando un sistema di bookmarking e suddividendo la struttura in sezioni in modo che la query di ricerca possa cercare nella sezione giusta anziché nell’intera struttura.
L’ovvio vantaggio dell’utilizzo di una struttura di dati di ricerca è che gli utenti possono cercare i record finché non trovano le informazioni specifiche di cui hanno bisogno. Allo stesso tempo, poiché la query è così costosa, non è altrettanto vantaggiosa su strutture di dati più piccole. Se la struttura dei dati è piccola e può essere facilmente cercata da una persona, il computer potrebbe effettivamente impiegare più tempo per trovare un record rispetto a se un utente effettuasse la ricerca manualmente.