Gestion de Datos - UNIDAD I - ARCHIVOS - 2020 - Ver 2

Vista previa del material en texto

Gestión de Datos
2020
Cátedra de Gestion de Datos
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
Medios de Almacenamiento. Concepto de Archivo. -Operaciones Básicas.
Recuperación, Inserción y Actualización de Registros. Distintas
Organizaciones. Archivos Hash. Archivos Indexados Secuenciales. Índices
estructurados como Arboles AVL - B y B*.
UNIDAD TEMATICA Nº 1: Archivos. 
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
La información en la computadora pueden almacenarse en:
• Almacenamiento Principal. Consiste en la memoria principal, pero no
es grande, además de ser volátil. En ella suele almacenarse los datos
necesarios para una consulta. Su acceso es rápido, pero resulta
inadecuada para el almacenamiento de grandes volúmenes en forma
permanente.
• Almacenamiento Secundario. Consiste en el almacenamiento en
dispositivos auxiliares como los discos, en donde puede guardarse la
información en forma durable. Debe contemplarse el tiempo de acceso al
dispositivo secundario, que deben reducirse al mínimo posible.
MEDIOS DE ALMACENAMIENTO
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
Un ARCHIVO o FICHERO (FILE) es un conjunto finito de información
estructurada en subconjuntos llamados REGISTROS, los cuales suelen estar
guardados en dispositivos secundarios de almacenamiento.
Un REGISTRO está formado por un conjunto de CAMPOS que toman un valor
particular de un conjunto de valores posibles o DOMINIO.
Una LLAVE o CLAVE (KEY) es un campo o conjunto de campos que permite
identificar en forma univoca a un registro.
ARCHIVOS
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
Ejemplo de un archivo de alumnos:
ARCHIVO ALUMNOS
Legajo (ID) Apellido Nombre DNI
123 Pérez Juan 43434343
456 Gómez María 44444444
789 Juárez Gustavo 45454545
899 Ibarra Daniel 46464646
911 Tejerizo Raul 47474747
CAMPOS
CLAVE
REGISTRO
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
Un REGISTRO LOGICO está formado por un conjunto de CAMPOS que toman un
valor particular de un conjunto de valores posibles o DOMINIO.
Una REGISTRO FISICO, también denominado BLOQUE o PAGINA, es una unidad
de transferencia entre el almacenamiento principal y el secundario.
Normalmente un registro físico contiene varios registros lógicos, pues se busca
minimizar los accesos al almacenamiento secundario, cuello de botella en los
sistemas informáticos.
REGISTROS LOGICOS Y REGISTROS FISICOS
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ORGANIZACIÓN DE ARCHIVO Y METODOS DE ACCESO
• La ORGANIZACIÓN DE ARCHIVO implica un criterio para representar,
almacenar y recuperar los registros de un archivo almacenados en un
soporte físico externo o secundario.
• El METODO DE ACCESO refleja los pasos necesarios para almacenar y
extraer los registros de un archivo.
• Normalmente la organización del archivo y los métodos de acceso están
íntimamente relacionados, debido a que algunos métodos solo pueden
aplicarse en algunas de las organizaciones de archivo.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
Un ORGANIZACIÓN DE ARCHIVO debe ser capaz de realizar las siguientes
operaciones sobre los archivos:
• RECUPERACION o CONSULTA (QUERY): recuperar un conjunto de
registros específicos en base a un criterio determinado, sin modificarlos.
• ACTUALIZACION: operaciones que producen diferentes cambios en el
archivo, que podemos clasificar en:
o INSERCION: implica el alta o inserción de un nuevo registro.
o MODIFICACION: significa la modificación de valores de un
registro existente.
o ELIMINACION: baja o eliminación de un registro existente.
OPERACIONES SOBRE ARCHIVOS
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ORGANIZACIÓN DE ARCHIVO
TIPOS PRINCIPALES DE ORGANIZACIÓN DE ARCHIVOS:
• ARCHIVOS DESORDENADOS O EN CUMULO.
• ARCHIVOS ORDENADOS O SECUENCIALES.
• ARCHIVOS HASH.
• ARCHIVOS SECUENCIALES INDEXADOS.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ARCHIVOS DESORDENADOS O EN CUMULO.
• Los registros se almacenan en el mismo
orden que se insertan. No existe ningún
criterio de ordenación de los registros en
base a los valores de sus campos.
• Inserción muy eficiente (el registro se
inserta al final).
• Solo se puede aplicar la búsqueda lineal,
que implica leer uno por uno los registros
hasta encontrar el deseado o llegar al fin
de archivo. Poco eficiente para grandes
volúmenes de información.
N = masa o cantidad de datos
T = tiempo de búsqueda
N
T
Orden Lineal
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ARCHIVOS ORDENADOS O SECUENCIALES
• Los registros se almacenan en forma
ordenada en base al valor de ciertos
campos (clave o llave), formando una
secuencia por esta clave.
• Inserción y borrado problemáticos, debido
a que debe mantenerse el orden.
• Se puede aplicar la búsqueda binaria, al
encontrarse ordenado. Se posiciona en la
mitad del archivo, y si no se encuentra el
registro, y el valor de la clave es inferior,
nos posicionamos en la mitad inferior y se
repite el proceso. De lo contrario, seguimos
por la mitad superior.
N = masa o cantidad de 
datos
T = tiempo de búsqueda
N
T
Orden 
Logarítmico
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ARCHIVOS HASH
Los ARCHIVOS HASH, también conocidos como ARCHIVOS DE ACCESO
DIRECTO, consiste en particionar los registros mediante una función hash –h(x)-
que toma como argumento el valor de la clave y nos devuelve una dirección de
memoria denominada bucket o cubeta, donde esperamos encontrar a nuestro
registro.
Por razones técnicas (por ejemplo para hacer al archivo reubicable)
normalmente a cada valor de la función hash h(x) se la asocia a una tabla hash,
en donde cada una de sus entradas tiene asociado un puntero por el cual se
accede al bucket o cubeta.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ARCHIVOS HASH
H(x) Puntero
0
1
2
3
…
……………..
B- 1 
BUCKETS O CUBETAS
Función 
Hash
H(X)
H(X) determina
la cantidad de
entradas de la
tabla Hash (B)
VALORES DE 
LA CLAVE –X-
TABLA HASH
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
La elección de la FUNCION HASH es critica ya que debe garantizar la
distribución de la manera mas uniforme de los registros a lo largo del
archivo.
Algunas
Funciones
Hash usuales
FUNCION HASH
FUNCION MODULO. Consiste en dividir el valor de la clave
por un numero entero predeterminado y tomar el resto de la
división entera como resultado.
FUNCION PLEGADO. Al valor de la clave expresada en
binario se la parte en secciones de la misma longitud, luego se
suman éstas cuyo resultado es el valor de la función.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
COLISIONES EN ARCHIVOS HASH
Desgraciadamente las funciones hash no siempre garantizan una
dirección univoca, siendo posible que mas de un registro tengan
asignado la misma cubeta o bucket. En estos casos tenemos registros
sinónimos y se genera una colisión, debiendo preverse un mecanismo
de gestión de colisiones.
DESBORDE ENCADENADO
AREA DE DESBORDE COMUN
HASH MULTIPLE O REHASHING
Mecanismos de
Gestión de 
Colisiones
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ARCHIVOS SECUENCIALES INDEXADOS
• Para acelerar las búsquedas, a un archivo secuencial se le suele
agregar una estructura adicional, el ÍNDICE, eliminando la necesidad
derecorrer secuencialmente el archivo de datos para acceder al
registro.
• El índice solo contiene dos registros: la clave y un puntero al archivo
de datos.
• Como el archivo de datos no cabe entero en la memoria principal, la
idea es buscar en una estructura auxiliar mas pequeña –el índice- y
acceder a los bloques necesarios de los datos.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
ARCHIVOS SECUENCIALES INDEXADOS
Clave Puntero
K1
K2
….. …………
KN
Clave Demas Campos
K1
K2
…. ……………………………………………..
KN
ARCHIVO INDICE ARCHIVO DE DATOS
Es un archivo mas
pequeño y puede caber
en memoria principal
Es el archivo que contiene toda la información y por
su voluminosidad no cabe en la memoria principal. La
idea es acceder solo a los bloques necesarios.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
TIPOS DE INDICES
• INDICE PRINCIPAL O PRIMARIO. Estructurado sobre la clave o llave,
garantiza la univocidad entre un valor de la clave y un registro. En un
esquema de archivos secuenciales indexados existe por lo menos un
archivo de datos y un índice principal o primario.
• INDICE SECUNDARIO. Se estructura sobre campos diferentes de la
clave y puede contener valores no unívocos. Se usan para acelerar
consultas por campos diferentes de la clave. Sin embargo, una
proliferación de estos índices puede degradar la performance del
sistema.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDEXADO PERFECTO – INDICES DENSOS
En un INDICE DENSO, existe una correspondencia unívoca entre un valor
de la clave y un registro.
Este esquema se denomina INDEXADO PERFECTO, en donde el índice
tiene tantos registros como el archivo de datos.
Clave Puntero
K1
K2
….. …………
KN
Clave Demas Campos
K1
K2
…. ……………………………………………..
KN
ARCHIVO INDICE ARCHIVO DE DATOS
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDEXADO POR BLOQUES – INDICES ESCASOS O DISPERSOS
En un INDICE ESCASO O DISPERSO, solo se almacenan algunos valores
de la clave, que apunta a un bloque del archivo de datos. En el índice se
almacena la clave mayor del bloque (cubrimiento).
Este esquema se denomina INDEXADO POR BLOQUES, en donde el
índice tiene tantos registros como bloques existen en el archivo de datos.
Suele emplearse este esquema cuando el índice es muy grande para caber
completo en memoria principal.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDEXADO POR BLOQUES – INDICES ESCASOS O DISPERSOS
Clave Puntero
K2
K4
….. …………
KN
Clave Demas Campos
K1
K2
K3
K4
…. ……………………………………………..
KN-1
KN
ARCHIVO DE DATOSARCHIVO INDICE
BLOQUE 1
BLOQUE 2
BLOQUE M
M
 R
EG
IS
TR
O
S
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDEXADO POR NIVELES
Clave Puntero
40
80
Clave Demas Campos
10
20
30
40
50
60
70
80
ARCHIVO DE DATOS
ARCHIVO INDICE
DE PRIMER NIVEL
Clave Puntero
20
40
60
80
ARCHIVO INDICE
DE SEGUNDO NIVEL
Si el archivo de datos y el índice
resultante son muy grandes, se puede
particionar al índice en varios niveles
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDEXADO CON ARBOLES EN LOS INDICES
Una estructura posible de indexación es la utilización de ARBOLES en los
archivos índice. Un árbol se encuentra compuesto por una jerarquía de
nodos, los cuales, salvo el raíz, tienen cero o mas nodos hijos. Un nodo sin
hijos, se llama nodo hoja o nodo terminal.
La profundidad o altura del árbol es el numero máximo de niveles entre el
nodo raíz y los nodos hoja. Se procura que la profundidad sea equilibrada y la
mínima posible.
El grado u orden del árbol es el numero máximo de hijos permitido por nodo.
Cuando el grado es mayor se reduce la profundidad o altura del árbol.
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDICES CON ARBOLES AVL
Un ARBOL AVL es un árbol binario de búsqueda, con las sencilla regla
que las claves menores se ubican a la izquierda del nodo y las mayores a
su derecha. No se permite que la profundidad o altura entre los dos
subárboles de un nodo sea superior a 1.
El registro de un índice de un árbol AVL es de la siguiente manera:
CLAVE
PUNTERO HIJO 
IZQUERDO
PUNTERO HIJO 
DERECHO
PUNTERO AL 
ARCHIVO DE 
DATOS
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDICES CON ARBOLES AVL
Dada la siguiente secuencia: 32, 20, 70, 10, 50, 79, podemos obtener el
siguiente árbol AVL, junto con sus archivos de datos e índice.
ARCHIVO INDICE ARCHIVO DE DATOS
32
20
10 50
70
79
CLAVE PHI PHD PAD
1 32 2 3 100
2 20 4 -- 101
3 70 5 6 102
4 10 -- -- 103
5 50 -- -- 104
6 79 -- -- 105
Clave Demas 
Campos
100 32
101 20
102 70
103 10
104 50
105 79
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDICES CON ARBOLES B
Para utilizar arboles con grado superior a 2, se utilizan los ARBOLES B de
orden m, de acuerdo a las siguientes reglas:
• Si el nodo raíz no es un nodo hoja, debe tener al menos dos hijos.
• Cada nodo, excepto el raíz y los nodos hoja, deben tener entre m/2 y m
punteros e hijos.
• El numero de claves en un nodo hoja esta comprendido entre (m-1)/2 y m-1.
• El numero de claves en un nodo que no sea hoja es uno menos que el numero
de punteros.
• El árbol debe estar equilibrado.
• Los nodos hoja están enlazados según el orden de los valores de las claves
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
INDICES CON ARBOLES B
El registro del índice de un árbol B de orden M tiene la siguiente
estructura:
• Si se organiza como un indexado perfecto:
• Si se organiza como un indexado por bloques:
M -1 
CLAVES 
M 
PUNTEROS A HIJOS
M
PUNTEROS A 
ARCHIVO DE DATOS
M -1 
CLAVES 
M
PUNTEROS A HIJOS
1 PUNTERO A 
ARCHIVO DE DATOS
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
1. Fundamentos de bases de datos. (Abraham Silberschatz, Henry F. Korth /y/
S. Sudarshan.—(Tra. Fernándo Sáenz Pérez, Antonio García Cordero /y/ Jesús
Correas Fernández.-- Rev. Tca. Luis Grau Fernández). McGraw Hill. Madrid
/c.2006/5a. Edic.
2. Sistemas de bases de datos. Un enfoque practico para diseño,
implementación y gestión. (Thomas M. Connolly /y/ Carolyn E. Begg. Pearson
Addison Wesley. Madrid /c.2005/4a. Edic.
3. Fundamentos de Bases de Datos. (Pablo Rovarini – Herminia De la Vega.
Editorial UNSTA /c.2005/2ª. Edic.
Referencias Bibliográficas
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional
Gestión de Datos
Departamento Sistemas
Facultad Regional Tucumán
Universidad Tecnológica Nacional