Organización de Ficheros y Métodos de Acceso en ingeniería del software - Ficheros con índices (Modo Indexado)

En este modo de organización, al fichero le acompaña un fichero de índice que tiene la función de permitir el acceso directo a los registros del fichero de datos.

El índice se puede organizar de diversas formas, las más típicas son: secuencial, multinivel y árbol.

A través del índice podremos procesar un fichero de forma secuencial o de forma directa según la clave de indexación, y esto independientemente de como esté organizado el fichero por sí mismo.

El índice debe estar organizado en función de alguno de los campos de los registros de datos. Se pueden tener tantos índices como se quiera variando la clave (o campo) que se emplee. El índice está formado por registros (entradas) que contienen:

• Clave de organización.
  
  
• Puntero(s) al fichero de datos, en concreto al registro que corresponda.

Los índices se pueden clasificar en dos tipos, según cada entrada señale a la dirección de un registro del fichero de datos (índice total o denso), o bien apunte a un grupo de registros del fichero de datos que debe estar ordenado (índice escaso o no denso). En el caso de índices totales, el fichero puede estar desordenado.

Con el segundo tipo se podría procesar directamente el fichero de datos de forma secuencial.

Los índices totales o densos no suelen utilizarse de forma simple, sino combinados con índices escasos más cortos, de esta manera pueden almacenarse en memoria principal obteniendo así un acceso más rápido.

A continuación veremos las tres formas principales de organizar los índices:

Secuencial

En esta forma de organización se usan cadenas de punteros. Dentro de ella podemos distinguir dos tipos:

1. Simple Casi no se utiliza, en ella las inserciones y supresiones son realizadas por copia.
   
   
2. Encadenada: Se emplea más que la anterior, aún así tiene el problema de que si crece mucho el fichero de datos, crece también el número de entradas, provocando que la búsqueda, al ser secuencial no se óptima para un acceso directo.

Multinivel o Jerarquizada

Consiste en varios índices secuenciales encadenados. Tendremos un índice a los registros de datos y otros índices que apuntarán a un índice de nivel menor.

Este método surge para mejorar la organización secuencial encadenada. Los índices de nivel alto suelen ser escasos y los de primer nivel densos.

Al igual que en la organización secuencial, si aumenta el número de registros sigue aumentando el número de entradas.

Árbol

Viene a mejorar el problema del crecimiento de entradas en un nivel. Se pretende que el número de entradas en cada nivel sea fijo, y lo que crezca sea el número de niveles.

Se usan diferentes tipos de árboles, binarios (de búsqueda y AVL), multirrrama y B⁺