vsams rendimiento

7/29/2019 vsams rendimiento

1/25


2/25

Ficheros indexados 5 Ficheros indexados 6

Ejemplo de recuperacin

Ficheros indexados 7

4.2. NDICESAlgunos conceptos sobre ndices

Un ndice se puede definir como una estructura de datos que contiene unafuncin, donde el argumento de la funcin es una clave y el valor de la funcines un nmero de registro. En otras palabras, con un ndice es posible encontrarun nmero de registro asociado al valor de clave dado.

La funcin hashing del fichero de acceso directo es un mtodo diferente paraencontrar una funcin que traduzca el valor de una clave a un nmero deregistro. Esto no requiere una estructura de datos como un ndice, pero padeceel problema inevitable de los sinnimos.

Adems, la funcin hashing determina el nmero de registro, mientras que elndice permite que el valor de la clave y el nmero de registro seanespecificados independientemente.

Mientras que el fichero por s mismo podra considerarse como un ndice, seraun ndice muy ineficiente si empleramos algoritmos como los vistos ensecuencialidad para encontrar el nmero de registro.


Por tanto, un ndice es normalmente una estructura separada del fichero, noslo lgicamente separada, como con el fichero secuencial indexado, perotambin fsicamente separada, como cuando el ndice se localiza en un ficheropropio como en la figura


3/25


4/25


5/25


6/25


7/25

Ficheros indexados 25 Ficheros indexados 26

Asumimos que hay espacio al final de cada seccin de registros en el ficheroprincipal para un puntero a una lista de registros que han sido sacados de laseccin. Obsrvese que el procesamiento secuencial del fichero es ralentizadopor la necesidad de hacer un acceso al rea de overflow entre los registros conclaves entre 15 y 24.

Sin embargo, acceder a un registro arbitrario necesita que no sea ralentizadosi modificamos el ndice de nivel 1. Suponemos que adems de tomar la clavems alta en cada seccin de fichero principal o su lista de desbordamiento,adems toma la clave ms alta en la seccin de fichero principal. Con estainformacin podemos decir si buscamos un registro particular en el ficheroprincipal o en el rea de desbordamiento.

En el caso de nuestro ejemplo de entrada de ndice de nivel 1 para la primeraseccin de fichero principal es ahora:


La entrada indica que 15 es la clave mayor en la seccin y que 19 es la clavems alta cuando la lista de desbordamiento se toma en cuenta. Para irdirectamente desde el nivel 1 a la lista de desbordamiento apropiadanecesitaremos un puntero desde la entrada del ndice de nivel 1 a la lista. Sinembargo, en los diagramas siguientes mostraremos los valores de clave en lasentradas de ndice de nivel 1 pero omitiremos punteros a listas de overflow paraevitar que los diagramas se vuelvan confusos de seguir.

Insertar 33.

- La clave 33 cae en los rangos de los registros almacenados en las seccionesde tres registros del fichero principal. Una examen del ndice de nivel 1 indicaque si el registro con clave 33 estuviese ya en el fichero estara en la seccintercera; su clave es mayor que la clave mayor grabada para la segunda seccin.

- Por tanto, el nuevo registro es insertado en la tercera seccin. La figuramuestra la nueva configuracin. Aunque las dos listas de desbordamiento estnseparadas en los diagramas, no hay ninguna razn por la que no debieran seralmacenadas intercaladas en el mismo fichero.



8/25


9/25


10/25


11/25


12/25


rbol AVL, caso I, rotacin simple (rbol izquierdo no -equilibrado).


rbol AVL, caso II, parte 1 (desplazamiento a la derecha).


rbol AVL, caso II, parte 2 (desplazamiento a la izquierda).

Truco: En situaciones del caso I los signos en los factores deequilibrio de nodos X e Y son los mismos, mientras que lasdel caso II los signos son distintos.


Discusin Como mximo, slo se necesita una transformacin, ya sea una rotacin simpleo doble, para cada insercin de un nodo en un rbol AVL. Realizamos latransformacin si es necesaria tras cada insercin mejor que esperar hasta quetodos los nodos hayan sido insertados y entones transformar el rbol. Este

procesamiento extra que estamos realizando en el momento de la insercin parabalancear el rbol tendr sus resultados en el momento de recuperar dndonos unrendimiento mejor. Adems veamos que tenemos limitado el peor caso a O(log2n)

para el acceso directo, lo cual es una ventaja.

Algoritmo 4.1

INSERCION AVL

I. Insertar el registro en el rbol AVL utilizando el procedimiento de insercin enrbol de bsqueda binario.

II.Ajustar los factores de equilibrio para todos los nodos en el camino desde elpadre del registro recientemente insertado y el nodo raz.

III. Si todos los factores de equilibrio ajustados son 0,o 1, entonces terminar,

sino determinar si es una situacin de caso I o caso II y entonces realizar latransformacin apropiada

Como ejercicio: Hacer ejemplo anterior


13/25


14/25


15/25


16/25


17/25


18/25


19/25


20/25


21/25


Los ficheros directos valores de claves normales (es decir, norestringidos nicamente a valores enteros). Adems, hacan un mejor uso delespacio de disco del fichero que los ficheros relativos. Sin embargo,hacindolo as, los ficheros directos quitan al usuario la capacidad de realizaracceso secuencial a los registros de datos.

Finalmente, los ficheros indexados se deshacen de las reas de desbordamiento,y aun proporcionan acceso aleatorio y secuencial a los registros de datos delusuario. Es ms, el usuario ya no tiene que conocer detalles tcnicos deldispositivo en el que el fichero reside ese da. Sin embargo, el acceso secuencial ha

de tomar un nivel de indireccin para traer los datos (es decir, va el registropuntero en el nivel ms bajo del ndice, el cual es denso). Adems, los datos deusuario no se mantenan en orden secuencial por valores de claves ascendentes.Por tanto, el rendimiento del acceso secuencial de un fichero indexado era menor

que el de un fichero ISAM.

Los ficheros ISAM proporcionan al usuario tanto el acceso aleatorio a los registrosde datos usando valores de clave normales y acceso secuencial a los datos. En

cambio, el usuario tiene que saber mucho sobre las caractersticas tcnicas deldispositivo que est siendo usado., ya que la ubicacin del fichero est relacionadadirectamente con las capacidades del cilindro y la pista de una unidad especfica.

Adems, utilizando reas de desbordamiento, si el usuario acta de maneraerrnea en el diseo y ubicacin del fichero, el rendimiento se degradadramticamente.


VSAM Using a Key-Sequence Data Set (KSDS) Structure


VSAM File Example Using Customer Numbers


VSAM Split Internal Example


22/25


23/25


24/25

Costes frente a beneficios


25/25


Como sucede siempre que hay que resolver compromisos, hay siemprealgunas ganancias as como puntos negativos. La tabla compara la organizacin deficheros indexados con otros tipos de ficheros discutidos hasta ahora.

El acceso secuencial a los registros es ms lento que en los ficherosecuenciales.

La cantidad de espacio tomada por el ndice es mayor que en un fichero ISAM,puesto que hay un registro ndice por cada registro de datos de usuario en elfichero en el nivel 1.

Costes:

Nunca se usa un rea de desbordamiento.

El rendimiento del acceso aleatorio es consistente y predecible desde el punto devista del usuario.

Beneficios:

Se proporciona tanto un acceso aleatorio rpido como un acceso secuencialrazonable de los registros de datos.

Puede permitirse cambiar las claves en una operacin UPDATE.

La estructura del fichero se construye dinmicamente y crece dinmicamenteconforme el fichero se expande.


PCs frente a mquinas grandes

El principal problema de los usuarios de PCs era las limitaciones de espaciodisponible y los ciclos CP (es decir, el poder de procesamiento delmicrocomputador). El fichero indexado lleva asociado una cantidad considerablede la estructura adicional al fichero.

Sin embargo, proporciona al usuario la capacidad de acceso tanto aleatoriocomo secuencial para los registros de datos de usuario. Puesto que el ndice sereorganiza solo dinmicamente, el camino hacia un registro de datos especficosiempre se mantiene ptimo. Por tanto la estructura de fichero indexado esbastante adecuada para los entornos microcomputador.

El mundo de los mainframes tiende a ser menos limitado en espacio de disco,y el poder de procesamiento de estas mquinas tiende a ser bastante alto. Portanto, los ficheros indexados proporcionan a los usuarios una pieza importantey con funcionalidad sin efectos negativos aparentes.



File Systems. Structures and algorithms Thomas R. Harbron, Prentice-Hall,1988

Files and Databases: An Introduction Peter D. Smith G. Michael BarnesAddison-Wesley Publishing Company

File Structures. An analytic approach Salzberg, Prentice-Hall Intl, 1988

File Organization & Processing Alan L. Tharp, John Wiley & Sons, 1988

File Systems. Dessign and Implementation Grosshans, Prentice-Hall, Inc

REFERENCIAS

Documents

vsams rendimiento