Procesamiento De Base De Datos

Tema II. Procesamiento de Bases de Datos.

La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades:

• Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.

• Si el elemento está en el conjunto, hallar la posición en la que se encuentra.

Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

Para la búsqueda en bases de datos podemos definir tres tipos: búsqueda secuencial, búsqueda binaria y búsqueda de Hash.

Búsqueda secuencial

La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. A la búsqueda secuencial, también se le conoce como búsqueda lineal. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.

Mejoras en la eficiencia de la búsqueda secuencial:

1) Muestreo de acceso:

Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas.

2) Movimiento hacia el frente:

Este esquema consiste en que la lista de registros se reorganice dinámicamente. Con este método, cada vez que la búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que él.

3) Transposición:

Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre más accesos tenga el registro, más rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere más tiempo de actividad para reorganizar al conjunto de registros. Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.

4) Ordenamiento:

Una forma de reducir el número de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

El método de búsqueda secuencial funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Búsqueda Binaria

A la búsqueda binaria, también se le conoce como dicotómica. Es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central. El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.

Este método permite buscar un valor en una matriz que se está ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño.

Se puede aplicar tanto a datos en listas lineales (Vectores, Matrices, etc.) como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:

• La lista debe estar ordenada en un orden especifico de acuerdo al valor de la llave.

• Debe conocerse el número de registros.

Búsqueda hash (mediante transformación de claves)

El método de transformación de claves nos permite encontrar directamente el registro buscado en tablas o archivos que no se encuentran necesariamente ordenados, en un tiempo independiente de la cantidad de datos.

El método de Hashing nos permite manejar aplicaciones de búsqueda donde no tenemos claves con características tan limitadas. El resultado es un método de búsqueda completamente diferente a los métodos basados en comparaciones, ahora en vez de navegar por las estructuras comparando palabras clave con las claves en los items, tratamos de referenciar items en una tabla directamente haciendo operaciones aritméticas para transformar claves en direcciones de la tabla. Esto último se logra implementando una Función Hash, que se va a encargar de dicha transformación.

Idealmente, todas las claves deberían corresponder con direcciones diferentes, pero es muy frecuente que dos o mas claves diferentes sean transformadas a la misma dirección, cuando esto pasa, se dice que se presenta una Colisión. Es por eso que también

...