En informática , una estructura de datos de búsqueda [ cita requerida ] es cualquier estructura de datos que permite la recuperación eficiente de elementos específicos de un conjunto de elementos, como un registro específico de una base de datos .
La estructura de búsqueda más simple, más general y menos eficiente es simplemente una lista secuencial desordenada de todos los elementos. La localización del elemento deseado en dicha lista, mediante el método de búsqueda lineal , inevitablemente requiere un número de operaciones proporcional al número n de elementos, tanto en el peor de los casos como en el caso medio . Las estructuras de datos de búsqueda útiles permiten una recuperación más rápida; sin embargo, se limitan a consultas de algún tipo específico. Además, dado que el costo de construir tales estructuras es al menos proporcional an , solo se amortizan si se van a realizar varias consultas en la misma base de datos (o en una base de datos que cambia poco entre consultas).
Las estructuras de búsqueda estáticas están diseñadas para responder a muchas consultas en una base de datos fija; Las estructuras dinámicas también permiten la inserción, eliminación o modificación de elementos entre consultas sucesivas. En el caso dinámico, también se debe considerar el costo de corregir la estructura de búsqueda para tener en cuenta los cambios en la base de datos.
El tipo de consulta más simple es ubicar un registro que tiene un campo específico (la clave ) igual a un valor especificado v . Otros tipos comunes de consulta son "encontrar el elemento con el valor clave más pequeño (o más grande)", "encontrar el elemento con el valor clave más grande que no exceda v ", "buscar todos los elementos con valores clave entre los límites especificados v min y v max ".
En determinadas bases de datos, los valores clave pueden ser puntos en algún espacio multidimensional . Por ejemplo, la clave puede ser una posición geográfica ( latitud y longitud ) en la Tierra . En ese caso, los tipos comunes de consultas son encontrar el registro con una clave más cercana a un punto dado v ", o" encontrar todos los elementos cuya clave se encuentra a una distancia dada de v ", o" encontrar todos los elementos dentro de una región específica R de el espacio".
Un caso especial común de este último son las consultas de rango simultáneas en dos o más claves simples, como "buscar todos los registros de empleados con salario entre 50.000 y 100.000 y contratados entre 1995 y 2007".