indexación de archivos simple
TRANSCRIPT
INDEXACIÓN DE
ARCHIVOS SIMPLE
David Fernández Puentes
Búsqueda y ordenación
eficiente
Índice (Puede existir más de uno por fichero) : Estructura de datos en memoria, que permite el
acceso a la información almacenada en un
archivo a partir de un determinado orden.
Se mantiene en memoria:
Un dato identificador.
Dirección física/lógica del registro en el fichero que
hace referencia a la información completa.
Se almacena en una dupla (<clave>,<dirección>),
permitiendo el acceso único a la dirección.
Normalmente se usa un vector ordenado, pero por
eficiencia sería mejor una estructura de tipo árbol ABB
Índice Simple o primario
Guarda únicamente una primary key,
indentificando de forma única a un registro
El índice Guarda campo clave y dirección
física de fichero.
El fichero Guarda registros sin orden
establecidoClave Dir. fich.
Ana 0
Beatriz 170
Miguel 68
Pablo 34
Dir. Fis.fich
Clave Resto de campos
0 Ana Sánchez Romero|20|Jaén
34 Pablo Moreno Jiménez|18|Almería
68 Miguel Cano Ruano|32|Huelva
170 Beatriz Gómez Solano|25|Granada
F. Índice F. Datos
Operaciones de mantenimiento de
un archivo indexado
Tareas para el manejo de un índice:
Crear un nuevo índice a partir de un fichero de
datos.
Cargar un índice ya existente en memoria desde
un fichero de índice.
Reescribir el fichero e índice al final.
Añadir registros al fichero de datos.
Eliminar registros del fichero de datos.
Modificar registros del fichero.
Pasos para crear un índice
Recorrer el fichero de datos
secuencialmente e ir extrayendo de cada
registro el campo clave.
Crear la dupla <clave, dir_fichero>, siendo
dir_fichero la dirección física del fichero donde
se encuentra el registro con dicha clave.
Insertar dicha dupla en el índice en memoria.
Guardar el índice en fichero para mantener
la integridad del sistema.
Se hace un recorrido secuencial del índice y
se guarda la dupla <clave, dir_fichero> en el
fichero de índices.
Cargar el índice en
memoria/Guardar el índice a
fichero Cargar el índice a memoria: Recorrer el
fichero de índices secuencialmente con las
duplas <clave, dir_fichero>, e
insertarlos directamente en el índice en
memoria.
Guardar el índice en disco: salvar el índice de
memoria al fichero de índices antes de
terminar la aplicación.
El fichero de datos siempre permanece
actualizado pero el de índices puede no
estarlo. Para salvar este problema puede
marcarse el fichero índice con alguna etiqueta
cuando éste se modifica en memoria.
Añadir un nuevo registro al
fichero.
Implica añadir una nueva entrada al índice:
Se extrae la clave del registro a insertar.
Se busca una posición válida para insertar el
registro en el fichero de datos y se inserta en
dicha posición.
Se inserta la dupla <clave, dir_fichero> en el
índice en memoria.
Eliminar un registro de
fichero.
Implica eliminar la entrada correspondiente en
el índice.
Se busca la clave del dato a borrar en el índice,
para conocer su localización en el fichero.
Se utilizará un método de borrado u otro según
las características.
Se elimina en memoria la dupla <clave,
dir_fichero> del índice.
Actualizar un registro de
fichero.
Implica 2 situaciones diferentes:
Si cambia el valor del campo clave cambia su
posición.
La actualización no cambia al campo clave no
se modifica el índice.
Implementación. Clase para
gestionar un índice simple