Sandoval_Padilla_Fernando_Cesar_Segunda parte de dispersión (colisiones) - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Estructuras de datos II
“Segunda parte de dispersión: Resolución de colisiones”
Docente: Lara López Graciela
Sección: D12
Salón: X-10
Alumno: Sandoval Padilla Fernando Cesar
Código: 215685409
	
			 14 de Mayo de 2020
“Segunda parte de dispersión: Resolución de colisiones”
En seis tablas comparativas anotar 2 ventajas y 2 desventajas de los métodos de resolución de colisiones:
	Saturación Progresiva
	Ventajas
	Desventajas
	-Su simplicidad, es un método perfectamente adecuado.
	-Si los registros se cargan en un archivo vacío y se usa saturación progresiva para resolver las colisiones, solo dos registros estarán en sus direcciones base, por lo que se requieren accesos adicionales para extraer los demás.
	-Si se coloca más de un registro en una sola dirección la longitud media de búsqueda deja de ser un problema; es decir, si la densidad de empaquetamiento se mantiene baja, el registro requerirá menos de dos accesos.
	-La longitud media de búsqueda es el número promedio de veces que se espera acceder al disco para extraer un registro. Entonces usando la saturación progresiva, la longitud media de búsqueda aumenta rápidamente conforme se incrementa la densidad de empaquetamiento.
	Almacenamiento Por Compartimentos
	Ventajas
	Desventajas
	-El problema de la saturación ocurre con mucho menor frecuencia cuando se usan compartimientos que cuando cada dirección puede almacenar solo un registro, entonces ninguna dirección a la que se asignan uno o dos registros tiene saturación.
	-Cuando un compartimiento se llena persiste el problema de la saturación, es decir, si el archivo es demasiado grande tardara más cargando los registros.
	-El compartimiento completo se carga en memoria primaria. Entonces puede usarse una búsqueda en memoria RAM.
	-Si hay solo una pista por cilindro, el tiempo de desplazamiento consumirá una gran cantidad del tiempo de búsqueda
	Dispersión Doble
	Ventajas
	Desventajas
	-Evitan el acumulamiento de registros y el número de colisiones.
	-Viola la localidad al trasladar deliberadamente los registros en saturación a cierta distancia de sus direcciones base, incrementando así la probabilidad de que el disco necesite tiempo adicional para obtener la nueva dirección en saturación.
	-Pueden solucionar algunas de sus desventajas si son capaces de generar direcciones en saturación, de tal modo que los registros en saturación se mantengan en el mismo cilindro que los registros con direcciones base.
	-Si el archivo tiene mas de un cilindro, esto podría requerir un costoso movimiento adicional de la cabeza.
	Saturación Progresiva Encadenada
	Ventajas
	Desventajas
	-Evita los problemas causados por el acumulamiento y en el peor de los casos solo requiere 6 accesos.
	-Requiere un poco más de almacenamiento porque se agrega un campo liga a cada registro.
	-Los registros que no son base se guardan en un archivo separado garantizando que ninguna dirección base potencial este ocupada por registros en saturación.
	-Los métodos usados para eliminar estos problemas después de la carga inicial son un tanto complejos y, en un archivo muy volátil pueden requerir muchos accesos adicionales al disco.
	Encadenamiento con un área de saturación separada
	Ventajas
	Desventajas
	-Evita que los registros en saturación ocupen las direcciones base en donde no deben estar.
	-Si el área de saturación separada está en un cilindro diferente del de la dirección base, toda búsqueda de un registro en saturación implicara un movimiento de cabeza muy costoso.
	-Mantiene todas las direcciones base potenciales que no se han usado libres para inserciones posteriores.
	-Por lo general el tiempo de acceso real es peor cuando los registros en saturación están almacenados en un área de saturación separada que cuando se almacenan en el área de saturación principal.
	Dispersión extensible
	Ventajas
	Desventajas
	-Dobla el tamaño de la tabla de dispersión cuando sea necesario redispersar el archivo; es decir, facilita el organizar y reorganizar las tablas de dispersión.
	-Debe cumplir ciertas restricciones como el generar un entero mucho mayor que el número máximo de direcciones que se usaran.
	-Se desperdicia muy poco tiempo en el proceso de reorganización de la tabla original.
	-Se deteriora el empeño cuando el tamaño del espacio de direcciones crece dinámicamente conforme el crecimiento del tamaño del archivo 
Para el desarrollo de esta actividad, la información podrá ser investigada en el capítulo 11 del libro de “Estructuras de Archivos” de Michael J. Folk.