La búsqueda es un problema fundamental en Ciencias de la Computación, presente virtualmente en cada aplicación. Las bases de datos tradicionales se construyen basándose en el concepto de búsqueda exacta. Las consultas a la base de datos retornan todos aquellos registros cuyas claves coinciden con la aportada en la búsqueda. Las búsquedas más sofisticadas como búsqueda de rangos sobre claves numéricas, o búsqueda de prefijos sobre claves alfabéticas, se basan en la existencia de un orden lineal sobre las claves de búsqueda.