Técnicas de Búsqueda y Ordenamiento de Datos

Búsqueda Binaria

Ventajas:

• Recomendada para buscar en arreglos muy grandes.
• Reduce el tiempo requerido para buscar en una lista.
• Rápida por su recursividad.

Desventajas:

• El archivo debe estar ordenado.
• No revisa todos los elementos del archivo.

Búsqueda Secuencial

Se utiliza cuando el array no está ordenado. Consiste en buscar el elemento comparándolo secuencialmente con cada elemento del array hasta encontrarlo o hasta que llegue al final.

Ventajas:

• Recomendada para buscar en arreglos en el que los archivos no están ordenados.

Desventajas:

• Muy lenta, requiere mucho tiempo ya que compara los elementos uno a uno.

KeySorting

Se usa para ordenar datos de archivos que no caben completos en la memoria principal, por lo que se toma una llave de cada dato y se le asigna un RRN que apunta a la dirección en el disco. De esta forma, se ordenan todas las llaves en una estructura tal que al hacer una búsqueda de una llave, esta te envíe a la dirección en el disco.

Indexación

Indexación:

Técnica para recuperar los datos contenidos en un fichero o en una zona de memoria por medio de un índice que guarda la posición de los datos.

Hashing

Método de Búsqueda Hash:

Hash se refiere a una función o método para generar claves que representen de manera casi unívoca a un archivo, registro, etc (resumir o identificar un dato). Este método aumenta la velocidad de búsqueda un registro en un arreglo, permitiendo la eliminación e inserción de nuevos registros. No requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento (función hash).

Ventajas:

• Se pueden usar los valores naturales de la llave
• No se requiere almacenamiento adicional para los índices

Desventajas:

• No pueden usarse registros de longitud variable
• No permite llaves repetidas
• Solo permite acceso por una sola llave

Índice:

• Impone el orden en un archivo sin tener que reorganizar el archivo
• Varios ingresos a discos
• Cuando un archivo se modifica, cada índice en el archivo debe modificarse
• Ineficiencia al insertar y eliminar registros

Hashing:

• No hay orden en un archivo
• Un solo ingreso a disco
• Cuando el archivo se modifica, los índices no se modifican
• Eficiencia al insertar y eliminar registros