Encontrar un elemento en una lista de datos de computadora puede ser difícil y llevar mucho tiempo, razón por la cual se creó la estructura de datos de búsqueda. Una estructura de datos de búsqueda es cualquier estructura de datos que se puede buscar automáticamente, ya sea una base de datos grande o una lista pequeña. Hay dos tipos principales de estructuras de búsqueda, estáticas y dinámicas; la estática no puede cambiar, mientras que la dinámica permite la modificación. La búsqueda puede ser una operación costosa, por lo que la mayoría de las estructuras de datos están optimizadas para ayudar a la función de búsqueda a encontrar los datos. Ubicar elementos rápidamente es una ventaja obvia para esta estructura pero, dado que es tan costosa, la función de búsqueda se usa mejor con estructuras grandes.
A diferencia de la mayoría de las otras estructuras de datos, una estructura de datos de búsqueda puede ser cualquier tipo de estructura de datos. La característica dominante de esta estructura es que los usuarios pueden buscar en la estructura mediante una consulta; la estructura también debe tener al menos dos elementos en una lista, aunque la mayoría de las estructuras tienen decenas, cientos o miles de elementos. Esto significa que una base de datos, lista, cadena o árbol binario puede calificar como estructura de búsqueda.
Una estructura de datos de búsqueda se puede dividir en una de dos categorías: estática y dinámica. La versión estática no se puede cambiar y los usuarios solo pueden buscar en la lista. Esta estructura es mucho más fácil de mantener, porque los usuarios no tienen que preocuparse por cambiar el sistema de marcadores y la búsqueda suele ser más fácil. Las estructuras dinámicas permiten a los usuarios modificar elementos, ya sea cambiándolos o eliminándolos, pero son más difíciles de ejecutar. Los elementos pueden cambiar con tanta frecuencia que debe haber un sistema de marcadores para realizar un seguimiento de la posición de cada elemento.
La búsqueda en una estructura de datos puede resultar costosa, lo que significa que la computadora puede requerir mucho tiempo y esfuerzo. Por ejemplo, si se busca una estructura de datos linealmente y el elemento está en la parte inferior, la consulta tendrá que examinar cada elemento hasta encontrar el correcto. Para ayudar a la computadora, la mayoría de las estructuras de datos de búsqueda se optimizan mediante el uso de un sistema de marcadores y dividiendo la estructura en secciones para que la consulta de búsqueda pueda ver la sección correcta en lugar de la estructura completa.
El beneficio obvio de utilizar una estructura de datos de búsqueda es que los usuarios pueden buscar registros hasta encontrar la información específica que necesitan. Al mismo tiempo, debido a que la consulta es tan costosa, esto no es tan beneficioso en estructuras de datos más pequeñas. Si la estructura de datos es pequeña y una persona puede buscarla fácilmente, es posible que la computadora tarde más en encontrar un registro que si un usuario hiciera la búsqueda manualmente.