Download - ORGANIZACIÓN RELATIVA ACCESO DIRECTO
![Page 1: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/1.jpg)
ORGANIZACIÓN RELATIVA
ACCESO DIRECTO
Concepto
Funciones Hash
![Page 2: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/2.jpg)
Organización Relativa
Es aquella organización que plantea, que el archivo se mantiene organizado en modo directo debido a que el orden físico no corresponde con el orden lógico. Para accesar a los datos almacenados en el archivo se hace de manera directa por la posición que ocupan en el archivo.
Los registros se deben almacenar en un medio direccionable y tener un campo clave el cual será transformado para ser utilizado como dirección de almacenamiento. Por lo tanto debe existir la correspondencia entre los valores clave y las direcciones disponibles en el medio de almacenamiento
![Page 3: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/3.jpg)
VentajasLos registros se pueden leer y escribir en cualquier orden
y posición Es mas rápido el acceso a los registrosSe pueden realizar accesos secuencialesLos registros se actualizan en el mismo archivo en tiempo
real
DesventajasSe requiere programar la relación entre el contenido del
registro y la posición que ocupa.Existen huecos libres dentro del medio de
almacenamiento y entre registrosEl algoritmo para la conversión de las claves y para el
almacenamiento deben ser creados de modo que dejen el menor numero de huecos libres y se genere el menor numero de colisiones de dirección.
![Page 4: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/4.jpg)
Espacios libres
![Page 5: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/5.jpg)
Funciones Hash
Dada la siguiente expresión
Dirección Relativa Dirección Absoluta
A toda dirección relativa corresponde una dirección absoluta, es decir a cada registro a almacenar de acuerdo a un campo clave, le corresponde una dirección absoluta en el medio de almacenamiento. Por lo tanto se debe transformar la clave en un dirección, por medio de las funciones Hash .
h(x)
![Page 7: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/7.jpg)
Aritmética Modular
Se elige un número primo, o con pocos divisores, mayor que el número N de registros a almacenar.
La función se define:
h(k) = k mod m para que las direcciones vayan de 0 a m-1Ó
h(k) = k mod m para que las direcciones vayan de 1 a m
En esta formula m ha de ser primo para minimizar el número de colisiones
![Page 8: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/8.jpg)
Ejemplo:
En un archivo se almacenaran 996 direcciones (registros), para esto se elige un número primo cercano 997, aplicando la formula se obtiene:
Para : Fórmula Resultado
245643 h(245643) = 245643 mod 997 =381245981 h(245981) = 245981 mod 997 = 719257135 h(257135) = 257135 mod 997 =906
![Page 9: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/9.jpg)
Plegamiento
Consiste en partir la clave k en varias partes k1,k2,k3..kn, y la combinación de las partes de un modo conveniente (con frecuencia sumando las partes) da como resultado la dirección del registro.Cada parte ki, a excepción de la última tiene el mismo número de dígitos que la dirección especificada.
La función hash es:
h(k) = k1,k2,k3..kn
![Page 10: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/10.jpg)
Ejemplo :
El archivo de alumnos con el campo clave de 6 dígitos, este se puede dividir en grupos de tres y tres dígitos. Aplicando al función :
Para : Formula Resultado245643 h(245643) = 245 + 643 = 888
245981 h(245981) = 245 + 981 = 1226 queda 226 ( se ignora el 1)
257135h(257135) = 257 + 135 = 392
![Page 11: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/11.jpg)
O a la inversa usando las partes pares k2,k4 antes de sumarlas para obtener otras direcciones.
Para : Formula Resultado245643 h(245643) = 245 + 346 = 591245981 h(245981) = 245 + 189 = 434257135 h(257135) = 257 + 531 = 788
![Page 12: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/12.jpg)
Mitad del cuadrado
Consiste en calcular el cuadrado de la clave k y la dirección del registro viene representada por los dígitos de k2 que ocupan cierta posición.La función hash es:
h(k) 2 = c Donde c se forma por los dígitos de k2 que están en las posiciones P1,P2,..,Pi
![Page 13: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/13.jpg)
Ejemplo :
El archivo de alumnos con el campo clave de 6 dígitos, se escogen los dígitos 4to, 5to y 6to por la derecha.
Para : Fórmula Resultado245643 h(245643)2 = 60340483449 483245981 h(245981)2 = 60506652361 652257135 h(257135)2 = 66118408225 408
![Page 14: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/14.jpg)
Resolución de Colisiones
Las funciones hash no siempre ofrecen direcciones distintas, cuando se presentan direcciones repetidas se trata entonces de una colisión, para resolver esto se deben seguir métodos de solución.
Direccionamiento abierto
Se trata de buscar la primera dirección disponible después de la que dio como resultado la función hash.
![Page 15: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/15.jpg)
El problema de este método al ser lineal, llega a agrupar los registros en posiciones contiguas, lo cual aumenta el tiempo de búsqueda de un registro. Esto se puede minimizar por medio de :
• Prueba Cuadrática
h(k) = p donde p se repite para otro valor clave k,
entonces : p,p+1,p+2,p+3…p+n
p,p+1,p+4,p+9..p+i2
![Page 16: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/16.jpg)
Ejemplo:
Suponiendo que se obtiene lo siguiente:
k formula p245643 h(245643)2 = 60340483449 483
y p colisiono, entonces la búsqueda de lugar libre seria
438+12 = 439 o 438+22 =442 o 438+32 = 447
![Page 17: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/17.jpg)
• Prueba doble direccionamiento hash
En este método se aplica una segunda función hash para k, de manera que :
Primera hash h(k) = p y existe colisión, entonces segunda hash h(k) = p’ por lo tanto la dirección absoluta p + p’
En caso de seguir la colisión, se trataría lo siguiente:
p, p+p’, p+2p’, p+3p’
y así sucesivamente
![Page 18: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/18.jpg)
Direccionamiento por encadenamiento o cerrado
En este método el problema de colisiones se resuelve utilizando listas ligadas, que contendrán todos los registros que tienen la misma dirección
![Page 20: ORGANIZACIÓN RELATIVA ACCESO DIRECTO](https://reader036.vdocumento.com/reader036/viewer/2022082711/56813650550346895d9dd3e3/html5/thumbnails/20.jpg)
•Altas
•Bajas
• Individual• General
•Consulta• Individual• General
•Modificación• Individual• General
Consideraciones
• Validar : Entrada y salida de datos
• Validar : Duplicación de registros
• Generar posición
• Controlar colisiones
Operaciones de actualización: