Búsquedas

Búsquedas

Búsquedas

Los algoritmos de búsqueda permiten realizar búsquedas sobre un conjunto definido que puede ser homogéneo o heterogéneo, cualquiera sea el caso. Las búsquedas son útiles cando se manejan colecciones muy grandes de datos, y es necesario poder recuperar la información en los contenedores. Es necesario tener en cuenta que las búsquedas se realizan sobre elementos representativos de memoria, es decir arreglos unidimensionales o multidimensionales, listas enlazadas, etc. En el documento PDF anexo a la guía básica se encuentra la teoría referente a los algoritmos de búsqueda principales, es decir búsqueda secuencial y búsqueda binaria, en la pagina 26 (haciendo la búsqueda de páginas con el adobe reader). En este documento se estudiará la búsqueda indexada.

Búsqueda Indexada

Una analogía valida para el esquema de búsqueda indexada, es el tipo de búsqueda que hacemos en diccionarios o libros con índice. Por ejemplo, para buscar la palabra “Redención” en el diccionario, en vez de buscar pagina por pagina la información, lo que se hace es ir directo a la sección de la letra “R”, luego cada sección internamente tiene un orden alfabético para las palabras contenidas en ella, de modo que una vez más saltamos las palabras hasta llegar a las palabras que empiezan por “Red” y luego mediante otra búsqueda damos con la palabra. Basándonos en este ejemplo, podemos definir la búsqueda indexada como el proceso de búsqueda que hace uso de índices y subíndices para poder ubicar el elemento a buscar.

Prerrequisitos

Este tipo de búsqueda requiere que la información esté ordenada y a demás clasificada en subtipos o secciones. Por ejemplo, si se quiere modelar un sistema de inventario de una tienda que vende productos variados, donde se tienen productos alimenticios, productos de limpieza, equipos electrónicos, textiles y calzados, el modelo de almacenamiento de este sistema debe contemplar una colección de índices, donde cada índice “apunta” a su sección correspondiente, donde cada sección alberga un tipo especifico de piezas de inventario. Bajo este ejemplo se necesitan 5 índices, uno para cada tipo de inventario (textiles, comida, calzado, limpieza, electrónicos), así como también una colección referenciada por cada índice, con un total de 5 colecciones diferentes de datos. Cada colección internamente puede manejar indexación interna o no, según sea la implementación.

Niveles de Indexación

Mientras más índices se tengan, más eficientes a nivel de procesamiento serán las búsquedas, pero conlleva a consumir más memoria para almacenar cada índice. Adicionalmente, es posible tener niveles de indexación para un modelo de memoria determinado. Se puede establecer el nivel superior de indexación con la colección principal de índices, así como también por cada sección interna tener otro nivel de indexación para agilizar búsquedas internamente a nivel de secciones. Eso dejaría un modelo de memoria con dos niveles de indexación. Si es requerido es posible aumentar los niveles, a expensas del gasto implícito de memoria.

Optimalidad

Las búsquedas indexadas son fuertemente usadas en los diversos tipos de bases de datos, sobre todo en las bases de datos relacionales, y son por defecto los mecanismos mas eficientes de búsqueda actuales. El uso de búsqueda de indexada es aplicado mayormente usando arboles binarios de búsqueda (ABB), que sirven como estructuras eficientes para estos casos. Otras implementaciones hacen uso de Diccionarios o Tablas de Hash, tratando las colisiones como búsquedas exitosas. Adicionalmente a todo esto es posible aplicar búsquedas indexadas sin el uso de elegantes técnicas como el hashing, haciendo uso de vectores o listas en paralelo.

Estructura básica genérica

Colección de índices

Index1

Index2

Index3

Index4

….

…..

…..

…..

IndN-1

indexN

Correlación entre índices y lo que apuntan

Index1

Coleccion1

Index2

Coleccion2

Index3

Coleccion3

.

.

.

IndexN

ColeccionN

Colecciones de Datos

Coleccion1

Data1

Coleccion2

Data2

Coleccion3

Data3

.

.

.

ColeccionN

DataN