Ficheros – PRÁCTICA OBLIGATORIA Clases de Prácticas – 8ª sesión (8ª versión de la aplicación gestora)

Organizaciones Indexadas: Estudio Para mejorar la eficiencia en acceso a través de claves de búsqueda no privilegiadas, se plantea la introducción de almacenamiento auxiliar en forma de índices. En esta práctica se habrá de implementar al menos un índice, y tantos como se estime oportuno, pero siempre de modo justificado. En la memoria de prácticas deberá incluirse un estudio detallado y razonado de: (1) cuántos y qué índices se estiman necesarios; y (2) cuántos y qué índices se han implementado.

Organizaciones Indexadas: Implementación Los índices son archivos que se componen de ‘entradas’. Cada entrada consta de: -

Entrada de datos: valor de la clave de indización para esa entrada

-

Referencia al registro: puntero, que puede ser físico o lógico, según el caso

Podemos clasificar los índices en dos tipos principales, y según su tipo las operaciones serán ligeramente distintas -

Primarios: las claves de las entradas tienen valores únicos. o

añadir entrada: Cuando se quiere realizar esta acción, se recibirá la ‘entrada’ y el puntero relativo

o

borrar entrada: En este caso se recibirá únicamente la ‘entrada’

o

modificar entrada: Recibe la ‘ent_vieja’, la ‘ent_nueva’, y el puntero nuevo:

o -




La modificación de una entrada de índice se puede deber a que el usuario modifique el valor de la clave en el registro de datos.




La modificación puede no afectar a la clave pero causar que el registro cambie su posición (física), por ejemplo, pasando de la zona de direccionamiento a la de desbordamiento.

buscar entrada: recibe un entrada y devuelve el puntero relativo

Secundarios: la clave de indexación tendrá valores repetidos, y será necesario contemplar esto en las operaciones del índice. o

añadir entrada: recibe ‘entrada’ y puntero relativo

o

borrar entrada: recibe ‘entrada’ y puntero relativo (pues puede haber varias entradas en el índice que coincidan con ‘entrada’)

o

modificar entrada: recibe ‘ent_vieja’, puntero viejo, ‘ent_nueva’, y puntero nuevo

o

buscar entrada: recibe una entrada y devuelve una lista de punteros relativos. En este caso, si el índice es serial debemos recorrer todo el índice hasta el final.

Los índices secundarios pueden funcionar como primarios con una pequeña modificación: haciendo que cada entrada conste de su clave y una lista de punteros. El diseño físico-lógico de esta entrada sería como sigue: [long_clave —] clave — long_lista — lista_de_punteros De este modo, cada clave aparece una sola vez en el archivo de índices. Previamente a insertar, se debe buscar la clave (si está, se le añade el puntero; si no, se inserta la entrada completa). Al borrar, se localiza la entrada y se elimina el puntero señalado. Y al buscar, se localiza la entrada y se devuelven todos sus resultados. Debe observarse que para cualquier operación con el índice se necesita localizar una entrada (hasta para insertar). Por este motivo, cuando se utilizan listas de punteros se busca una organización de índice que haga eficiente la localización de una entrada (índice secuencial, arbóreo, etc., pero no suele hacerse serial). En la realización de estas prácticas sólo se requiere implementar índices seriales (al menos uno primario y otro secundario). Se penalizará implementar el índice secundario con repeticiones (sin listas de punteros).

Organizaciones Indexadas: Archivos y Ficheros de Índice Cada índice es un archivo independiente, que tiene su propia organización y su propia relación físico-lógica. Así, podrá almacenarse: 

en un fichero aparte, sistematizando el nombre de los ficheros.



todos los archivos en el mismo fichero, en cuyo caso será necesario poder localizar el primer bloque de cada índice. Puesto que en este caso, el crecimiento dinámico del fichero puede hacer que los bloques del índice no sean contiguos, será necesario encadenar los bloques que forman un índice:  si es índice serial, cada bloque apuntará al siguiente bloque  si es índice secuencial, el primer bloque contendrá la lista (ordenada)

de bloques que pertenecen al índice. Esta técnica facilita la inserción de espacio libre distribuido y la partición celular  en los índices multinivel, ese encadenamiento es inherente

Organizaciones Indexadas: Administración y Mantenimiento Además podemos tener operaciones de administración y de mantenimiento de índices. Estas últimas se refieren a sacar el mayor provecho de los índices existentes (reorganizar, reordenar, compactar,...). La administración consiste en decidir qué organizaciones son adecuadas para hacer más eficiente nuestro sistema (qué índices deben existir en cada momento). Para esto es necesario proporcionar dos operaciones (de implementación opcional en estas prácticas):

-

crear índice: recibe la clave de indización (campos a indexar) y construye el índice. Si el campo ya estuviera indexado la operación se abortaría ya que no deberíamos tener el mismo índice sobre una misma clave.

-

borrar índice: borra el índice (destruye el archivo)

Si se decide implementar la opción de administración debe existir un registro de claves indizadas, que diga qué claves están indizadas. Esto es necesario para poder actualizarlos (en todas las operaciones de actualización que sufra el archivo), para no crear un índice varias veces, y sobre todo para poder usar el índice en las búsquedas. Este registro de claves indizadas puede contener otra información útil (como por ejemplo, cómo localizar los archivos de índice). En el caso de los sistemas comerciales puede contener incluso estadísticas sobre el estado y el uso del índice. Si el conjunto de índices no es dinámico (todos se crean al crear el sistema de fichero, y no se administra) ese conocimiento puede estar ‘cableado’ en la lógica de la aplicación.

Modificaciones sobre el funcionamiento Selección La inclusión de índices es trivial si se utiliza la técnica del conjunto resultado para realizar las búsquedas. Para cada uno de los campos indexados debemos de construir un nuevo “filtro”, que utilice los resultados que aporta el índice: el índice recibe un valor de clave y devuelve un conjunto resultado:   

si no hay valor de clave, devuelve todas las direcciones si el valor de clave buscado no está en el índice, no devuelve ninguna dirección en otro caso, devuelve la(s) dirección(es) que encuentre en el índice

El método filtro recibe un conjunto resultado (actual), invoca al método de búsqueda del índice recibiendo otro conjunto resultado (filtro), y devuelve la intersección de ambos (que será el nuevo conjunto resultado, ya filtrado).

Actualización Es necesario actualizar las entradas de los índices convenientemente cuando se actualiza el registro. En el caso de la modificación sólo se modifica la entrada del índice si los campos modificados están indexados.

Otros tipos de Índices (I): Índices Secuenciales En estos índices, las entradas mantienen un orden (según una clave de ordenación física) y se puede realizar búsquedas dicotómicas para localizar entradas. En este caso es conveniente que el registro de índices almacene no solo la dirección del primer bloque del índice sino la de todos los bloques del índice. Para ordenar los índices, que pueden ser de mayor tamaño que la memoria de la que disponemos, es común utilizar algoritmos como la mezcla natural. Los índices secuenciales favorecen la recuperación de información, pero si el fichero está sometido a muchas inserciones o actualizaciones es muy costoso mantener el orden.

Por esta razón es común emplear algunas de éstas técnicas, incluso varias de ellas sobre un mismo diseño de índices. •

Área desordenada: donde se insertan temporalmente las entradas nuevas o modificadas (aumenta la eficiencia de las inserciones y modificaciones).

•

Espacio libre distribuido: cada cubo se llena parcialmente al crear el índice de forma que las entradas que se inserten o actualicen con posterioridad lo hacen sobre el espacio libre (percentage free).

•

División o partición celular: Se mantiene una lista encadenada de cubos de índice, de forma que cuando uno de ellos desborda o necesita más espacio se divide en dos, se inserta el nuevo en la cadena y se reparten sus entradas (esto es sencillo de realizar si se almacena en algún sitio una lista ordenada de punteros, con un puntero a cada cubo del índice).

Para grandes cantidades de datos, aún el recorrido de un índice serial o secuencial puede ser demasiado costoso. Según los casos la solución pueden ser índices parciales, multinivel o arbóreos.

Otros tipos de Índices (II): Índices Parciales Estos índices imponen una condición para añadir la entrada, de modo que sólo se indexan las entradas más frecuentes en uso, si son índices primarios, y/o en ocurrencias si son secundarios: -

por frecuencia: los índices llevarán un contador (1 byte), que sumará una cantidad fija (por ejemplo, 1) a cada entrada cada vez que se use. De modo periódico (por ejemplo, una vez al día, cuando el sistema está ocioso) se ejecutará un proceso automático que divide entre 2 ese contador (es decir, descarta el bit de la derecha); ese mismo proceso eliminará del fichero de índices aquellas entradas cuyo byte sea 0. También se puede realizar en base a otro almacenamiento auxiliar (un log de operaciones) para evitar que el índice se convierta en un cuello de botella.

-

por repetición: si es un índice secundario, habitualmente se buscará una optimización como la de listas de punteros (que ya se ha explicado antes). En este caso, tiene menos sentido un índice parcial por frecuencia. El criterio que se buscará es el de almacenar las listas más largas. Así, sólo se almacenarán las listas cuyo número de punteros sea mayor o igual a cierta cantidad (por ejemplo, el 25% del tamaño en caracteres de la clave de indización).

-

por actualización: las actualizaciones en el archivo no repercuten inmediatamente en el índice, sino que se almacenan aparte (en otro archivo, un log de operaciones). Posteriormente, se actualizan los índices (por la noche, cuando el sistema esté ocioso, o bien a instancias del administrador). Así se evita que las actualizaciones (si son costosas) colapsen el sistema.

Mientras que la búsqueda en un índice exhaustivo termina si la entrada no se encuentra en el índice, en los índices parciales, no se puede asegurar que el registro

no exista. Por ello, es necesario realizar una búsqueda ‘base’ (habitualmente serial sobre todo el área de datos). A estos sistemas se les denomina ‘sistemas duales’. En nuestra práctica, si el sistema es dual el método de búsqueda en el índice no devuelve nunca un conjunto resultado vacío: 



si no hay valor de clave o si lo hay pero éste no se encuentra en el índice, tendrá que devolver todas las direcciones en otro caso, devuelve la(s) dirección(es) que encuentre en el índice

Como puede verse, el filtrado en menos útil, pero a cambio es mucho más eficiente. En el caso de los índices parciales por frecuencia, si no se ha podido filtrar (no se ha encontrado ese valor de clave) pero la búsqueda ha tenido éxito (después se ha encontrado ese valor de clave en un registro) deberá añadirse una entrada al índice para ese registro (que se afianzará si vuelve a utilizarse, o se volverá a eliminar si no se usa). Observar que estos índices no siempre son útiles (depende del uso).

Características Opcionales y Obligatorias de esta práctica En cuanto a las características mínimas obligatorias, serán las siguientes:  Se hará un estudio de indización  Se creará y utilizará al menos un índice primario y otro secundario (implementación de los índices y de su utilización)  Las divergencias entre lo establecido en el estudio de indización y la implementación deberán ir convenientemente justificadas.  Todos los índices deberán crearse de modo obligatorio al crear el fichero (a menos que se implementen las operaciones de administración, opcionales).  Los índices deben ser, al menos, seriales y exhaustivos, es decir, que tengan una entrada por cada registro de datos.

De modo opcional, se podrán incorporar las siguientes características:  Operaciones de administración: crear/destruir índices bajo demanda  Índices secuenciales (ordenados) con todas sus operaciones  Operaciones de mantenimiento (reorganizar índices)  Índices parciales y sistemas duales  Índices arbóreos (de la familia B)