Indices_Multiniveles.docx
INTRODUCCIN
Cuando estamos trabajando con archivos de gran tamao el problema
que tenemos para el mantenimiento de ndices se presenta en el tamao
que los ndices ocupan y como resultado la cantidad de memoria
requerida para mantenerlos en esa zona (memoria principal) y lograr
as un nivel de eficiencia ptimo.
Para solucionar este problema se fragmenta el ndice en mltiples
niveles en una estructura arbolada. Las principales tcnicas
son:
ISAM (Index Sequential Access Method) VSAM (Virtual Storage
Access Method)
ISAM
Es un modelo que se relaciona ntimamente al hardware de
almacenamiento puesto que se disea de acuerdo a la estructura de
los niveles del medio fsico como los cilindros, pistas y sectores.
Cada nivel contiene en el primer subnivel un ndice de los restantes
subniveles; ocasionalmente se reservan los ltimos elementos de este
nivel como rea de desborde. El rea principal de almacenamiento se
encuentra entre el ndice y el rea de desborde. Una cualidad de ISAM
es su alta velocidad de funcionamiento; su principal desventaja es
la escasa transportabilidad; es decir solo opera para un hardware
determinado. La implementacin de este modelo requiere la aplicacin
de tcnicas que sustituyen en cierto grado algunas funciones del
sistema operativo como son: almacenamiento y recuperacin de datos .
En vista de ello, deber obtenerse de un medio exclusivo para el
mantenimiento de los datos a manejar.
VSAM
Consiste en mantener en memoria principal un ndice maestro, el
cual contiene los intervalos iniciales de las llaves y las
referencias (ligas) hacia los archivos que contienen subintervalos
ms especficos de las llaves. Cuando se determina el archivo que ser
cargado en memoria, este se consulta para obtener un intervalo ms
especfico y se carga el siguiente archivo en las mismas localidades
de memoria, es decir, se sobre escribe en el ndice previo en la
memoria. Este proceso se repite hasta alcanzar el ltimo nivel el
cual contendr la direccin lgica del dato buscado en el archivo
principal. La principal cualidad de VSAM es su transportabilidad,
el inconveniente es la cantidad de accesos a disco que se requieren
para obtener el dato deseado. Segn la cantidad de memoria
disponible se diseara la cantidad de memoria de los bloques. A
mayor cantidad de memoria, mayor tamao de bloques y en consecuencia
menor cantidad de niveles y por lo tanto menos accesos a disco.
NDICES MULTINIVEL
Permiten reducir la parte del ndice que se requiere acceder en
un valor equivalente al factor de bloqueo del ndice. La principal
desventaja es su naturaleza esttica, es preferible usar un ndice
multinivel dinmico (rbol B/B+)
Estructura ndice Multiniveles
Se pretende reducir ms el coste de bsqueda de registros. Para un
ndice que ocupa b bloques de disco, tenemos:
ndices de un solo nivel: Coste de bsqueda de los registros: log2
b
En cada paso se reduce a la mitad el trozo de ndice en el que se
va a seguir buscando.
ndices multinivel: Coste de bsqueda de los registros: logr b
r = nmero de registros de ndice que caben en un bloque.
Se pretende reducir el tamao del trozo de ndice en el que se va
a seguir buscando el r, para esto se parte siempre de un fichero
ndice de un nivel ordenado y con entradas de tamao fijo.
Parmetros: Si ste primer nivel ocupa ms de un bloque, se define
un ndice de un nivel sobre el nivel base. Se repite el proceso
hasta que el ndice de nivel N quepa en un nico bloque de disco. El
nivel N ser el nivel mximo del ndice multinivel. El segundo nivel
tiene una entrada por casa bloque del primer nivel El tercer nivel
tiene una entrada por cada bloque del segundo nivel
Tiempo de acceso:
Ventaja que el nivel N quepa en memoria El nmero de bloques que
tenemos que leer para acceder a los datos es N
Problemas:
El ndice puede crecer mucho El nmero de bloques a leer para
acceder a los datos puede ser muy elevado Coste elevado en la
reorganizacin (mantener el ndice ordenado es muy costoso)
Como alternativa para los ndices multiniveles se pueden usar los
Arboles B y Arboles B+: ndices multinivel con espacio libre en cada
uno de los bloques para insertar nuevas entradas
Ejemplo: En la prctica no es excesivo tener un archivo con
100.000 registros, con 10 registros almacenados en cada bloque. Si
se dispone de un registro ndice por cada bloque, el ndice tendr
10.000 registros. Como los registros ndices son ms pequeos que los
registros de datos, se puede suponer- que caben 100 registros
ndices en un bloque. Por tanto el ndice ocupara 100 bloques. Estos
ndices de mayor tamao se almacenan como archivos secuenciales en
disco.
Si un ndice es lo bastante pequeo como para guardarlo en la
memoria principal, el tiempo de bsqueda para encontrar una entrada
ser breve. Sin embargo, si el ndice es tan grande que se debe
guardar en disco, buscar una entrada implicar leer varios bloques
de disco. Para localizar una entrada en el archivo ndice se puede
realizar una bsqueda binaria, pero aun as sta conlleva un gran
coste. Si el ndice ocupa b bloques, la bsqueda binaria tendr que
leer a lo sumo |log2(b)| bloques. (| x | denota el menor entero que
es mayor o igual que x; es decir, se redondea hacia abajo). Para el
ndice de 100 bloques, la bsqueda binaria necesitar leer siete
bloques. En un disco en el que la lectura de un bloque tarda 30
milisegundos, la bsqueda emplear 210 milisegundos, que es
bastante.
Para resolver este problema el ndice se trata como si fuese un
archivo secuencial y se construye un ndice disperso sobre el ndice
con agrupacin, como se muestra en la Figura. Para localizar un
registro se usa en primer lugar una bsqueda binaria sobre el ndice
ms externo para buscar el registro con el mayor valor de la clave
de bsqueda que sea menor o igual al valor deseado. El puntero
apunta a un bloque en el ndice ms interno. Hay que examinar este
bloque hasta encontrar el registro con el mayor valor de la clave
que sea menor o igual que el valor deseado. El puntero de este
registro apunta al bloque del archivo que contiene el registro
buscado.
ndice disperso de dos niveles.
Usando los dos niveles de indexacin y con el ndice ms externo en
memoria principal hay que leer un nico bloque ndice, en vez de los
siete que se lean con la bsqueda binaria. Si al archivo es
extremadamente grande, incluso el ndice exterior podra crecer
demasiado para caber en la memoria principal. En este caso se podra
crear todava otro nivel ms de indexacin. De hecho, se podra repetir
este proceso tantas veces como fuese necesario. Los ndices con dos
o ms niveles se llaman ndices multinivel. La bsqueda de registros
usando un ndice multinivel necesita claramente menos operaciones de
E/S que las que se emplean en la bsqueda de registros con la
bsqueda binaria.
CALCULO DE ACCESO A DISCO
El objetivo de los multiniveles es el de llegar a estructurar
los registros en un solo bloque lo cual significara que existiesen
varios niveles conectados entre niveles jerrquicos, el clculo del
acceso a disco es de la siguiente forma:
Se busca identificar el tamao que maneja cada bloque y la
cantidad total de registros que existen en el cual se busca la
posicin del registro deseado. Los bloques se manejan de cero en
adelante.
Se busca la capacidad de registros respecto a cada bloque
La longitud del registro y el tamao del bloque dependen de cmo
se construyan al momento de crearlos e implementarlos. Se busca la
cantidad de bloques que se obtendrn en total
Se requiere que se desarrolle varias veces hasta llegar al ltimo
nivel para lo cual el total promedio de accesos seria:
Donde nuevamente el +1 se indica el acceso al archivo o al
registro principal.
Ejemplo: Se tiene un total de 10000 registros y cada bloque fue
diseado para almacenar 68 registros de longitud de 15 bytes. El
primer nivel se obtiene que la cantidad de bloques que maneja es
de:
El primer nivel mantiene 148 y segn las condiciones de una
indexacin multinivel es llegar a un solo bloque por lo que se
genera un segundo nivel.
El segundo nivel manejar 3 bloques pero an se requiere un tercer
nivel para estructurarlo correctamente.
Por lo que este es el tercer nivel y el nivel superior de la
estructura del archivo por lo que los accesos sern:
