Ficheros indexados

1
Ficheros indexados Ficheros indexados
Tema 4
4.1. Ficheros secuenciales indexados
4.6. Consideraciones de diseo
4.5. ISAM y VSAM
4.4. Estructuras de rboles
4.3. ndices estticos y dinmicos
4.2. ndices
Ficheros indexados
2
4.1. FICHEROS SECUENCIALES INDEXADOS
Descripcin y organizacin
Puede pensarse en un fichero secuencial indexado como una variante del
fichero relativo no ordenado.
El trmino secuencial indexado se refiere normalmente a los ficheros
relativos ordenados en el que los bloques del ndice estn entremezclados con
los bloques de registros de tal modo que se minimice el tiempo de acceso.
La principal ventaja de un fichero secuencial indexado es que la bsqueda
binaria del fichero relativo ordenado puede ser reemplazada por un rbol de
bsqueda de ndices. Son generalmente ms rpidas que las bsquedas binarias.
El ndice es una estructura que contiene informacin sobr donde se
encuentra un registro con una clave dada. Igual que hay muchas formas de
estructurar ficheros, hay muchas formas de estructurar ndices.
Al contrario que los ficheros relativos ordenados, puede accederse
mediante un ndice.
Al igual que el fichero relativo ordenado, est ordenado en una clave.
Ficheros indexados
3
Estructura del ndice
El ndice de un fichero secuencial indexado est mezclado con los datos para
el fichero. Normalmente, la mayora de los bloques son usados para los datos,
pero algunos son usados para el ndice.
Una buena analoga se encuentra en un diccionario grande. Estos
diccionarios se publican frecuentemente en varios volmenes. Cada volumen
est indexado segn sus lmites correspondientes de acuerdo al rango del
alfabeto que contiene; por ejemplo, A-D, E-M, N-R, y S-Z.
Con cada volumen, puede haber un ndice que localice el punto de partida
para todas las palabras que empiecen por una letra dada.
Dentro de la seccin que contenga todas las palabras comenzando por una
letra, hay un ndice de la forma gua de palabras impreso en el encabezado
de la pgina, mostrando los lmites de la secuencia alfabtica para las
palabras en esa pgina.
Se hace una bsqueda para una palabra dada recorriendo su jerarqua de
ndices hasta que la pgina que contiene la palabra dada se localiza. Slo
entonces es necesario buscar una pgina para la palabra correspondiente y,
puesto que el ltimo nivel del ndice est en la misma pgina, no hay
necesidad de buscar los datos en otro sitio.
Ficheros indexados
4
Index
Block
Data
Block
Data
Block
Overflow
Data
Block
Data
Block
. . .
Overflow
Data
Block
Overflow
Data
Block
Ficheros secuenciales indexados
(Indexed Sequential Files)
Tipos de bloques:
ndice: (Index Block)
De datos primarios (Primary Data Block)
De Overflow (Overflow Data Block)
Ficheros indexados
5
Ficheros indexados
6
Ejemplo de recuperacin

Ficheros indexados
7
4.2. NDICES
Algunos conceptos sobre ndices
Un ndi ce se puede definir como una estructura de datos que contiene una
funcin, donde el argumento de la funcin es una clave y el valor de la funcin
es un nmero de registro. En otras palabras, con un ndice es posible encontrar
un nmero de registro asociado al valor de clave dado.
La funcin hashing del fichero de acceso directo es un mtodo diferente para
encontrar una funcin que traduzca el valor de una clave a un nmero de
registro. Esto no requiere una estructura de datos como un ndice, pero padece
el problema inevitable de los sinnimos.
Adems, la funcin hashing determina el nmero de registro, mientras que el
ndice permite que el valor de la clave y el nmero de registro sean
especificados independientemente.
Mientras que el fichero por s mismo podra considerarse como un ndice, sera
un ndice muy ineficiente si empleramos algoritmos como los vistos en
secuencialidad para encontrar el nmero de registro.
Ficheros indexados
8
Por tanto, un ndice es normalmente una estructura separada del fichero, no
slo lgicamente separada, como con el fichero secuencial indexado, pero
tambin fsicamente separada, como cuando el ndice se localiza en un fichero
propio como en la figura
Ficheros indexados
9
El coste de obtener el nmero de registro del ndice debe ser tan bajo
como sea posible, y ciertamente mucho menor que el coste de encontrar
el/los registro(s) deseado(s) en la bsqueda del fichero, o podra haber
mltiples ndices para el fichero de datos, cada uno con una clave diferente.
La longitud de un registro de ndice debe ser lo ms pequea posible. En
ndices sencillos, cada entrada de ndice consistir en el valor de la clave ms
un puntero a registros de datos, como muestra la figura anterior.
ndices ms complejos tendrn otros campos adems de stos. Los registros
de ndices cortos permiten un factor de bloque grande, que es especialmente
ventajoso en el caso de los ndices.
Puesto que un fichero no puede ordenarse por ms de una clave,
generalmente no es posible indexar bloques, como ocurra en el caso de los
ficheros secuenciales indexados.
En su lugar, cada registro debe ser indexado separadamente. Esto resulta en
un nmero considerablemente mayor de entradas de ndices, pero permite al
fichero de datos ser ordenado de un modo ms conveniente.
Ficheros indexados
10
Cada estructura de ndices tendr un conjunto de algoritmos apropiado a esta
estructura. En algunos casos estos sern idnticos a los que se utilizaban
anteriormente y en otros se necesitarn nuevos algoritmos para usar los ndices.
ndices lineales
El tipo ms sencillo de ndice. Es similar a los ndices que encontramos al final
de los libros. Un ndice lineal es uno en el que los registros del ndice estn
ordenados por el valor de la clave como en un fichero ordenado, con ninguna
estructura adicional. Un ndice as comparte muchas propiedades con un fichero
relativo ordenado, tanto buenas como malas.
Como en los ficheros relativos la bsqueda ser en cierto modo ms rpida para
el ndice que para el fichero correspondiente puesto que el factor de bloque ser
normalmente bastante ms grande para el ndice. Todos los registros del fichero
de datos pueden ser accedidos en el orden de la clave, leyendo el fichero de
ndices en secuencia y accediendo a cada registro de datos al encontrar su
puntero en el ndice.
Una combinacin de estos dos algoritmos puede ser usada para leer algn
subconjunto del fichero donde el subconjunto se base en el rango de valores de la
clave.
Ficheros indexados
11
- Por ejemplo, supongamos que hay un fichero de nminas que tiene un ndice,
entre otros, por salario. Se necesita una lista de todos los empleados ganando
entre $20000 y $25000 por ao.
La capacidad de posicionar eficientemente todos los registros de datos teniendo
un rango de valores de clave puede ser muy til en algunas aplicaciones.
- Desde este punto en el ndice, una lectura secuencial del ndice puede
realizarse hasta que se encuentre el primer salario mayor de $25000. Como se
lee cada entrada de ndice, el puntero se usa para acceder y leer el registro de
nmina correspondiente.
- En cualquier caso, una bsqueda secuencial corta sobre la vecindad ms
inmediata posicionar la entrada del ndice al primer empleado cuyo salario sea
igual o mayor a $20000.
- Una bsqueda binaria del ndice de salario posicionara o bien en la entrada del
ndice de un empleado ganando ahora $20000, o se posicionara en el lugar del
ndice inmediatamente anterior al primer empleado ganando ms de $20000.
Ficheros indexados
12
Adems, como en el fichero relativo ordenado, el ndice lineal es muy
difcil de actualizar. Los registros borrados pueden marcarse en el ndice
reemplazando el puntero por un valor nulo. Sin embargo, no hay ningn
lugar para insertar una nueva entrada de ndice en el orden requerido.
Hay soluciones de compromiso (similares a las usadas por ficheros secuenciales
indexados), que permiten un nmero limitado de entradas a aadir antes de que
una reorganizacin sea necesaria.
Por ejemplo, si un 20% de los slots de registros ndice en cada bloque se deja
vaco, podran aadirse nuevos registros reorganizando los registros ms antiguos.
Cuando un bloque se ha llenado, ser necesario reorganizar el ndice.
El ndice antiguo es descartado y uno nuevo se construye en tres pasos. Primero,
el fichero de datos se lee, y el valor y el puntero de clave son extrados para cada
registro vlido. Esto se aade a un fichero temporal.
Despus, el fichero temporal se ordena por la clave.
Y tercero, los valores del fichero temporal ordenado es copiado a un fichero ndice,
aadiendo la estructura que se necesite.
La reorganizacin es similar a la requerida en un fichero relativo ordenado en el
que se construye un ndice totalmente nuevo. Difiere en que el fichero de datos
es la fuente para el nuevo ndice en lugar de usar el ndice antiguo y cambiar el
fichero.
Ficheros indexados
13
ndices rbol
Un ndice rbol es uno en el que hay una jerarqua de ndices. La raz del primer
nivel de ndices apunta al segundo nivel de ndices. Cada nivel de ndices apunta
a los niveles menores hasta el ms bajo o hasta que los nodos hoja son
alcanzados. Los nodos hoja tienen punteros al fichero de datos slo. El ndice
usado con el fichero secuencial indexado es un ndice rbol.
Algunos conceptos relacionados: rboles heterogneos y homogneos (altura
y fan-out del rbol, aadir y borrar entradas al rbol), ndices rbol-B
(algoritmos para rboles B, variantes de rboles B).
Esta necesidad de reorganizar los ndices es la principal razn para no usar
ndices lineales.
El hecho de que la bsqueda binaria represente el peor caso de bsqueda en
rbol es otra razn para preferir otras estructuras de ndices. Sin embargo, en
aplicaciones donde el ratio en el que se aaden registros sea bajo, la
simplicidad del ndice lineal puede ser valorado frente a otras estructuras de
ndices ms complicadas.

Ficheros indexados
14
4.3. NDICES ESTTICOS Y
DINMICOS
El hashing, como describamos en el tema anterior, es una tcnica
computacional para organizar ficheros.
Los registros en ficheros hasehados pueden almacenarse y recuperarse
rpidamente. La tcnica es computacional en el sentido de que la direccin
de un registro requerido es, en gran medida, computada a partir de los
valores de datos en ese registro.
Indexar es una tcnica basada en estructura para el acceso a registros en
un fichero. Es una tcnica de estructura de datos en el sentido en que una
bsqueda de una estructura de datos produce la direccin requerida.
Una de las desventajas de un fichero hash es que los registros son difciles
de procesar en el orden de la clave. Lo cual podra ser importante si
queremos acceder a todos los registros con claves en un cierto rango.
Ficheros indexados
15
En esta tcnica al fichero de registros principal le sern aadidos uno o ms
ndices. Los ndices pueden ser parte del fichero principal o estar en ficheros
separados, y pueden ser creados o destruidos segn necesidad sin afectar al
fichero principal. Cuando se hacen cambios sobre el fichero principal, deben
realizarse las operaciones de actualizacin apropiadas sobre cualquiera de los
ndices en ese fichero.
Los ficheros de ndices pueden compararse con el ndice o tabla de contenidos de
un libro. Consideremos el ndice de un libro. Consiste en un nmero de entradas,
cada una es un par:
tema, nmero(s) de pgina(s).
Los ndices de un libro se tienen normalmente en orden alfabtico, lo cual hace
sencillo encontrar un tema particular y por tanto las pginas en las que esa palabra
es mencionada. Un fichero ndice es como el ndice de un libro. Los ficheros ndices
contienen normalmente registros de la forma siguiente:
valor de la clave, puntero(s) al fichero principal.
Ficheros indexados
16
Los punteros referencian registros en el fichero principal que tienen el valor
de clave particular. Se puede hablar tambin de una indexacin secundaria,
en la que muchos registros pueden tener un determinado valor de clave
secundaria.
Aunque los ndices para ficheros secuenciales son comunes, los ndices de
ficheros no secuenciales pueden tambin ser indexados. Un fichero secuencial
est tpicamente en secuencia slo con respecto a una clave.
Por ejemplo, un fichero de registros de seguros ordenado por el nmero de pliza
sera no-secuencial con respecto a una clave secundaria como puede ser el
poseedor de la pliza. No es muy probable que en los ficheros hash, tal y como
los hemos visto, exista ningn tipo de orden por ninguna clave.
Sin estructuras de datos, el procesamiento de registros con respecto a una
clave distinta de aquella por la que el fichero ha sido secuencializado es muy
probable que resulte ineficiente.
Excepto en ciertos libros de referencia, los temas en el cuerpo del libro no
aparecen en orden alfabtico. Los libros pueden ser, por tanto, vistos como no-
secuenciales desde el punto de vista del tema. (Ellos sern normalmente
secuenciales desde el punto de vista del nmero de captulo y de seccin).
Ficheros indexados
17
Los ndices ayudan a localizar los temas. En el resto de este tema nos
centraremos ms en la organizacin de ndices en el contexto de ficheros
secuenciales indexados.
Un fichero secuencial, recordemos, es aquel cuyos registros pueden ser
accedidos en orden secuencial, lo cual es normalmente el orden por clave
primaria. Un fichero secuencial indexado es un fichero secuencial al que se le
aade una estructura de ndices.
El propsito del ndice es el de acelerar el acceso a un registro particular.
Normalmente el ndice es efectivo slo cuando el fichero que est siendo
indexado se almacena en un dispositivo de acceso directo. Los ficheros
secuenciales sin indexar, por otro lado, podran ser razonablemente
almacenados en dispositivos secuenciales.
Hay alternativas a indexar como tcnica para conseguir acceso rpido a
ficheros secuenciales para ficheros secuenciales, pero tienen tendencia a ser
lentos o restrictivos comparativamente.
Sin embargo, si el ndice es el medio para conseguir tanto un procesamiento
secuencial como el acceso a un registro individual, entonces una estructura
de rbol es la mejor eleccin.
Ficheros indexados
18
Esto es porque el procesamiento secuencial se consigue por un simple rbol y
la naturaleza de este rbol permite tambin que un registro particular sea
localizado rpidamente. Los ndices que examinaremos estn basados en
rboles.
La organizacin secuencial es aparte del problema de insertar nuevos registros
en el fichero. Los problemas son al preservar la secuencia de registros y al
actualizar el ndice apropiadamente, la estructura del ndice no cambia. Las dos
clases de soluciones a estos problemas son tcnicas de indexacin estticas y
tcnicas de indexacin dinmicas.
Aunque los contenidos de un ndice esttico pueden cambiar conforme
realizamos inserciones y borrados en el fichero principal, la estructura de
ndices no cambia. Generalmente, el algoritmo de insercin usa reas de
desbordamiento. Este mtodo, sin embargo, tiende a llevarnos a una prdida
gradual de eficiencia para las operaciones de bsqueda y actualizacin, y se
requiere un mantenimiento peridico del rendimiento de re-almacenamiento.
Normalmente, esto implica ejecutar un programa que escriba una nueva
versin del fichero principal eliminando listas de desbordamiento. El ndice se
reconstruye durante la reescritura. El sistema IBM ISAM usa estructuras de
ndices estticas.
Ficheros indexados
19
Un ndice dinmico se adapta a los registros que se insertan o se borran
dentro del fichero principal. De algn modo, el mantenimiento de la eficiencia
es una parte integral de los algoritmos de insercin y borrado. No hay
necesidad de ejecutar un programa de mantenimiento peridicamente. Los
mtodos de indexacin dinmica se caracterizan por separar y unir nodos en
un rbol de ndices. El sistema IBM VSAM usa indexacin dinmica.
Tanto los ndices dinmicos como estticos son tiles, dependiendo del tipo
de aplicacin. Compararemos su eficiencia llevando a cabo las operaciones
siguientes sobre los ficheros:
- bsqueda de un registro con una clave dada
- insertar un nuevo registro
- borrar un registro con una clave dada
ndices estticos.
Una aproximacin a la organizacin de un rbol en una estructura de ndices es
para mantener esta estructura fija y tratar las inserciones mediante listas de
overflow y hojas. Como se podr ver, ser til incluir informacin sobre overflows
en el ndice.
Ficheros indexados
20
Organizacin del ndice
Un ndice esttico puede verse como una serie de tablas de tamao fijo. El
ms bajo nivel de la tabla indexa el propio fichero principal, el siguiente nivel
ms alto indexa el nivel ms bajo, y as. La figura (transp siguiente) muestra
un pequeo fichero ejemplo con dos niveles de indexacin.
Un nivel 1 indexa las entradas que llevan a valores de clave ms alto en una
seccin de tres registros del fichero principal junto con un puntero a la seccin.
Una entrada tpica es:
42, <puntero a la seccin con 42 como la clave ms alta>
La eleccin de 3 para el tamao de la seccin del fichero principal es
arbitraria aqu. En la prctica es probable que est relacionada con el tamao
de los registros lgicos y fsicos.
Por ejemplo, si el dispositivo de almacenamiento puede transferir hasta 1024
bytes en un acceso y los regs lgicos son 80 bytes de largos, cada seccin del
fich principal contendr probablemente 12 regs. Por tanto puede leerse una
seccin completa en un acceso a disco.
Ficheros indexados
21
Ficheros indexados
22
El ndice lleva a la clave ms alta en cada registro fsico. En una entrada de
ndice de nivel 2 llevamos, junto con un puntero apropiado, el valor de clave
mayor en cada seccin de tres registros del ndice de nivel 1.
Otra vez ms, la eleccin de tres aqu para el tamao de seccin es arbitraria.
Dadas unas caractersticas de fichero particulares y propiedades del medio de
almacenamiento, es posible calcular el nmero de niveles de ndices y el espacio
total que ocupan.
- Por qu indexamos una seccin por su clave ms alta en lugar de su clave
ms baja? Para contestar a esta pregunta, sigamos la recuperacin de un
registro con clave 28 de la figura. Empezamos en lo alto del rbol con el ndice
de nivel 2. Seleccionamos la entrada de ndice menor con clave mayor o igual
que la clave destino. En este caso seleccionamos el 42. El puntero asociado
apunta a la seccin de nivel 1 que contiene las siguientes entradas:
19
32
42
Ficheros indexados
23
- Usando los mismos criterios de seleccin, seguimos el puntero asociado
con entrada 32 en el ndice de nivel 1. El puntero nos lleva a las direcciones
de la seccin en el fichero principal que contienen
24
28
32
- Cuando buscamos esto, encontramos el registro con clave 28. Si en lugar de
ste, hubisemos estado buscando un registro con clave 29, la bsqueda habra
fallado cuando se encontrase la clave 32.
Tomando la clave ms alta en vez de la ms baja en el ndice, evitamos una
comparacin extra en cada nivel de ndices durante la operacin de bsqueda. Esto
es porque el puntero al valor ms bajo y la clave del valor ms grande juntos
definen un subespacio de bsqueda.
- Por ejemplo, el puntero asociado con la entrada 32 del ndice de nivel 1 apunta
a la seccin que empieza por 24. Cualquier registro con una clave en el rango de
24 a 32 estar en esa seccin. Si tomamos la clave ms baja, tendramos que
mirar a la siguiente entrada de ndice para establecer el lmite superior en el
subespacio.
Ficheros indexados
24
- Se puede ver que esto es cierto dibujando la estructura de la figura y
reemplazando los valores de clave altos con los valores de clave bajos
apropiados. Si volvemos a tracear la bsqueda de la clave 28, veremos
cmo el nmero de comparaciones clave-clave difiere.
Insercin
A continuacin, examinemos la forma en la que el fichero y sus ndices
cambian cuando se hacen inserciones en el fichero principal.
- Insertaremos registros con claves 7, 33 y 18. Estas inserciones pueden
causar condiciones de desbordamiento que habr que resolver.
Insertar 7.
- Cuando insertamos un registro con clave 7, la estructura de ndices nos lleva
a la primera seccin de tres registros en el fichero principal. Estos donde el
registro con clave 7 estara si se encontrara en el fichero. Para preservar la
secuencia de registros, el nuevo registro debe ser insertado despus de uno
con clave 6. Por tanto, el registro con clave 19 se saca de la seccin del
fichero principal y se mete en un rea de overflow. Veamos la nueva
configuracin.
Ficheros indexados
25
Ficheros indexados
26
Asumimos que hay espacio al final de cada seccin de registros en el fichero
principal para un puntero a una lista de registros que han sido sacados de la
seccin. Obsrvese que el procesamiento secuencial del fichero es ralentizado
por la necesidad de hacer un acceso al rea de overflow entre los registros con
claves entre 15 y 24.
Sin embargo, acceder a un registro arbitrario necesita que no sea ralentizado
si modificamos el ndice de nivel 1. Suponemos que adems de tomar la clave
ms 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 esta
informacin podemos decir si buscamos un registro particular en el fichero
principal o en el rea de desbordamiento.
En el caso de nuestro ejemplo de entrada de ndice de nivel 1 para la primera
seccin de fichero principal es ahora:
Ficheros indexados
27
La entrada indica que 15 es la clave mayor en la seccin y que 19 es la clave
ms alta cuando la lista de desbordamiento se toma en cuenta. Para ir
directamente desde el nivel 1 a la lista de desbordamiento apropiada
necesitaremos un puntero desde la entrada del ndice de nivel 1 a la lista. Sin
embargo, en los diagramas siguientes mostraremos los valores de clave en las
entradas de ndice de nivel 1 pero omitiremos punteros a listas de overflow para
evitar que los diagramas se vuelvan confusos de seguir.
Insertar 33.
- La clave 33 cae en los rangos de los registros almacenados en las secciones
de tres registros del fichero principal. Una examen del ndice de nivel 1 indica
que si el registro con clave 33 estuviese ya en el fichero estara en la seccin
tercera; 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 figura
muestra la nueva configuracin. Aunque las dos listas de desbordamiento estn
separadas en los diagramas, no hay ninguna razn por la que no debieran ser
almacenadas intercaladas en el mismo fichero.
Ficheros indexados
28
Ficheros indexados
29
Insertar 18.
-La clave 18 <clave ms alta asociada con la primera seccin del
fichero (19) pero > ltima clave en la seccin del fichero principal (15).
directamente en lista de desbordamiento.( Ahora una recuperacin
de registro con clave 19 es probable que lleve ms tiempo que antes. )
Ficheros indexados
30
Si se dan desbordamientos en estas reas, el procesamiento secuencial es
razonablemente rpido. Sin embargo, qu pasa si hay bastantes inserciones
en una parte del fichero para agotar un rea de desbordamiento de un cilindro
en particular? Tales inserciones cluster inserciones con un pequeo rango de
valores de clave comparados con el rango de claves del fichero como un todo
son un problema para las organizaciones de ficheros indexados secuenciales.
En una organizacin esttica, como la que hemos descrito, resultarn
largas listas de desbordamiento. Una solucin es proporcionar un nmero
de cilindros libres que puedan ser usados, el procesamiento del fichero
tanto secuencial como directo empiezan por requerir movimientos de la
cabeza de disco que consumen un cierto tiempo. El rendimiento se degrada
rpidamente.
Un punto dbil de la organizacin esttica es su potencial de degradacin de
rendimiento conforme se van haciendo las inserciones. En una aplicacin tpica
esperaramos que hubiese ms recuperaciones que inserciones o borrados, por
lo que es importante que sean tan eficientes como resulte posible.
En una organizacin esttica los programas de mantenimiento pueden tener
que ejecutarse peridicamente para restaurar los niveles de rendimiento.
Durante estas ejecuciones es probable que el fichero sea inaccesible.
Ficheros indexados
31
ndices dinmicos.
En contraste, los ndices dinmicos, que tocara ver ahora despus,
pueden cambiar gradualmente su forma con el fin de preservar la
eficiencia. Comparado con los ndices estticos, se puede hacer ms
trabajo cuando un registro se inserta o se borra, pero no hay necesidad
de un mantenimiento peridico separado.
Muchos ndices dinmicos se implementan como rboles. Podemos considerar 4
estructuras de rboles comunes y compararlas en trminos de:
[Link] (mnimo para un nmero dado de registros)
[Link] de mantenimiento
[Link] mximo.
Vamos a ver estas estructuras de rboles en el siguiente apartado.
Los cuatro tipos a los que nos referimos son binarios, AVL, multicamino y
rboles B.

Ficheros indexados
32
4.4. ESTRUCTURAS DE RBOLES
Introduccin
Una de las estructuras de datos fundamentales y muy importantes en
informtica es el rbol. Su importancia viene de su:
Fl exi bi l i dad: Un rbol permite que datos almacenados sean procesados de
diferentes modos de manera relativamente eficiente, por ejemplo, directamente
o secuencialmente. Es una estructura de datos que encaja en situaciones
dudosas en los que no sabes cmo sern finalmente procesados los datos. Es
adems til cuando sabemos de antemano que los datos van a ser procesados
de diferente modo. Un rbol puede no ser la mejor estructura de datos para un
nico propsito, pero su flexibilidad la hace a menudo la mejor para mltiples
propsitos.
Efi ci enci a de bsqueda: Un rbol intenta la bsqueda eficiente de los
datos, para cuando una rama del rbol pueda ser podada en una bsqueda, esto
significa que todos los datos en esa rama no necesitan procesarse ms tarde.
Una estructura de rbol puede a menudo usarse como un mecanismo de filtrado
en localizar un elemento de informacin deseado. Como procedemos a lo largo
de la estructura de rbol, filtraremos los datos no deseados.
Ficheros indexados
33
Natural i dad en l a representaci n: Un rbol es normalmente una forma
natural de representar informacin. Lo que estamos describiendo puede tener
relaciones de padres, descendencia y hermanos que encajan fcilmente en
una estructura de rbol. Un problema se resuelve fcilmente si tenemos una
representacin sencilla.
Poder de representaci n: Un rbol hace a veces posible una aplicacin,
que de otro modo no podra ser.
Los rboles han sido siempre una estructura de datos importante, y es
probable que lo continen siendo por las razones mencionadas.
4.4.1. rboles de bsqueda binarios
Muchas de las razones mencionadas en la introduccin para el estudio de los
rboles son aplicables a los rboles de bsqueda binarios. Un rbol binario es la
estructura de rbol ms sencilla que hay. Como el nombre implica, tiene a lo
sumo dos ramas que emanan de un nodo o coyuntura. Para hacer de un rbol
binario un rbol de bsqueda binario, seguiremos una convencin para
construirlo y procesarlo.
Ficheros indexados
34
Un nodo en un rbol de bsqueda binario se usa tanto para almacenar
datos como para actuar como un marcador de decisiones en la localizacin de
la informacin. En el almacenamiento (o recuperacin) de informacin, el
primer reg se convierte en el nodo raz del rbol.
Si no encontramos una rama vaca, repetimos el proceso con la entrada al
siguiente nivel y comparamos para igual, menor que, o mayor que. El proceso
termina cuando localizamos una rama vaca.
Si clave
insertar
< clave
almacenada
, tomamos la rama izquierda.
Si clave
insertar
< clave
almacenada
, tomamos la rama derecha. Si la rama est
vaca (null), hemos encontrado el lugar para hacer la insercin (o sabemos que
el reg no est en el fich si estamos recuperando).
Al insertar los regs posteriores, se hace una comparacin entre la clave del
registro a insertar y la clave del reg almacenado en el rbol binario. Si las
claves son idnticas, tenemos un reg duplicado (o hemos encontrado el
registro que estbamos buscando para una recuperacin). Si las claves no
emparejan, entonces procedemos.
Un rbol de bsqueda binario es un rbol binario en el que los nodos se usan
tanto para almacenar informacin como para proporcionar la direccin hacia
otros nodos. La informacin se organiza de manera que todas las claves
menores que la del nodo actual se encuentran en el subrbol izquierdo y
aquellas mayores estn en el subrbol derecho.
Ficheros indexados
35
Ejemplo
- Construyamos un rbol de bsqueda binario insertando los nombres de las
ciudades favoritas de un grupo de estudiantes. Las ciudades y su orden de
insercin son
Dallas, Oakland, Pittsburgh, Miami, Chicago, Denver, Boston y Spiveys Corner
El rbol de bsqueda binario despus de las inserciones es el de la figura:
Ficheros indexados
36
Discusin
La profundidad de un rbol de bsqueda binario, como para los rboles en
general, es el mximo nivel de cualquier nodo contenido en l, relativo al nodo raz.
Un fichero secuencial indexado usa un mecanismo de rbol para organizar los
datos para procesamiento tanto secuencial como directo.
Podemos procesar los datos secuencialmente usando uno de los rdenes
estndar para atravesar un rbol binario. Podemos procesar los datos
directamente o secuencialmente con relativa facilidad.
Pero notemos que esta media es considerablemente mayor en pruebas que
las que hacamos con un esquema hashing tpico. Cul es la ventaja? La
flexibilidad.
Saber que la profundidad de un rbol binario de bsqueda es cuatro nos dice que
somos capaces de recuperar un registro sencillo directamente sin hacer ms de 4
pruebas. El nmero medio de pruebas para recuperar cada registro una vez es 2.75.
El raz es el nivel uno y el nivel de cada uno de los restantes nodos se define
recursivamente como un ms que el nivel de su padre. La profundidad del rbol
de bsqueda binario del ejemplo es cuatro, puesto que Denver y Spiveys
Corner estn en el nivel 4.
Ficheros indexados
37
Cules son las diferencias? Con el secuencial indexado, el rbol se usa slo
para propsitos sobre el ndice, y los datos se almacenan en nodos hoja;
mientras que con un rbol de bsqueda binario, el rbol se usa como un
directorio y como una estructura de almacenamiento.
Cul lleva menos trabajo para construirlo? El rbol de bsqueda binario.
Pero cul es la estructura menos eficiente si tienes grandes cantidades de
datos para almacenar? Qu estructura de rbol tiene mayor profundidad? El
rbol de bsqueda binario; de modo que es menos eficiente cuando se realiza
acceso directo de un elemento nico.
Ficheros indexados
38
Y qu hay del procesamiento secuencial? Una vez ms, el rbol de bsqueda
binario es menos eficiente, puesto que moverse arriba y abajo en el rbol lleva
ms trabajo que moverse a lo largo de la estructura de ndices secuencial
indexada.
Veamos que la estructura de un rbol de bsqueda binario depende del orden
de insercin. Cul habra sido nuestro rbol si hubisemos insertado en orden
alfabtico las claves?
Para pequeas cantidades de datos y/o datos que no son procesados
frecuentemente, el rbol de bsqueda binario tiene sus ventajas.
Esta diferencia implica que el rbol de bsqueda binario tendr mayor
profundidad y por tanto llevar ms tiempo de procesamiento tanto para el
procesamiento directo como secuencial.
Por qu es la estructura secuencial indexada ms eficiente para grandes
cantidades de datos? Hay que mirar los factores de bifurcacin. El factor de
bifurcacin de un rbol binario es dos, mientras que de una estructura
secuencial indexada es mucho mayor.
Ficheros indexados
39
Cul es la profundidad mxima de este rbol? Cul es el nmero mximo de
pruebas necesarias para recuperar un elemento? Cul es el nmero medio de
pruebas necesarias para recuperar un elemento? Veamos que la estructura es
un rbol degenerado equivalente a una lista lineal secuencial. Como sabemos,
tal estructura no es eficiente para realizar un acceso directo.
Ficheros indexados
40
Puesto que la profundidad es 8, el nmero mximo de pruebas necesarias
para recuperar un elemento es 8. El nmero medio de pruebas para recuperar
un elemento sencillo es 4.5.
Esta es una tcnica que emplea tiempo de procesamiento de datos adicional
en la insercin, de modo que gastaremos menos tiempo para recuperaciones.
La siguiente estructura de rbol que vamos a considerar pretende eliminar
este inconveniente. Si en cualquier momento el rbol de bsqueda binario no
est aproximadamente equilibrado, realizamos un procesamiento adicional
para equilibrarlo de nuevo.
Con el rbol de bsqueda binario original, slo una profundidad de 4 y 2.75
pruebas de recuperacin son necesarios. Obviamente preferiremos tener un
rendimiento menos dependiente del orden de insercin.
La justificacin es otra vez que nosotros normalmente insertamos un
elemento en una tabla una vez, pero lo recuperamos muchas veces. Esta
variacin del rbol binario de bsqueda que se presentar a continuacin se
llama rbol AVL o rbol de altura equilibrada.
Ficheros indexados
41
Un rbol AVL es un rbol de bsqueda binario en el que los subrboles de
un nodo se mantienen aproximadamente a la misma altura (o profundidad).
Transformaciones en el rbol binario mantendrn su altura equilibrada.
Por esta razn, se llama tambin rbol de altura equilibrada. Como hemos
visto anteriormente, una deficiencia del rbol binario es que el orden de
insercin de los registros puede causar que este rbol se convierta en no-
equilibrado. El rbol AVL nos permite mantener un rbol equilibrado
indepediente del orden de insercin.
Qu queremos decir por un rbol de altura equilibrada? Primero, necesitamos
definir el trmino factor de equilibrio para un nodo. El factor de equi l i bri o de
un nodo es la altura de su subrbol derecho menos la altura de su subrbol
izquierdo. Como antes, el nodo raz est en el nivel uno y cada uno de los otros
nodos estar en el nivel de su padre ms uno. La altura (o profundidad) de un
subrbol es el nivel mximo de cualquier nodo en ese surbol relativo a su raz.
4.4.2. rboles AVL
El rbol AVL toma su nombre de quienes lo originaron, Adelson-Velskii y
Landis.
Ficheros indexados
42
- El nodo E est en el nivel cuatro y la altura del subrbol con F como raz es
dos. Puesto que los nodos A, y E son terminales, todos ellos tienen factores de
equilibrio de 0. F tiene un factor de equilibrio de 1, D +1, B +2. El nodo D tiene
un factor de equilibrio de +1 ya que la altura de su subrbol derecho es dos y la
de su subrbol izquierdo es uno.
En el siguiente
rbol binario
- Un rbol AVL es un rbol de bsqueda binario en el que todos los nodos tienen
un factor de equilibrio de 0 o +1 o 1. El rbol en el ejemplo no est equilibrado,
puesto que el nodo B tiene un factor de equilibrio de 2. Si el nodo E se eliminara,
el rbol resultante sera un rbol AVL.
Ficheros indexados
43
Ojo!: El factor de equilibrio de un nodo est determinado por la altura de sus
subrboles derecho e izquierdo y no por la cuenta del nmero de nodos en
ellos.
Insertar un registro en un rbol AVL empieza justo como en un rbol binario
de bsqueda; entonces los factores de equilibrio para todos los nodos en el
camino desde el nodo insertado a partir del nodo raz han de ser computados.
Nos movemos desde el nodo insertado hacia la raz para atrs con el fin de
intentar emparejar una de las plantilas de no-equilibrados.
Afortunadamente, hay slo dos circunstancias en las que un rbol AVL puede
quedar no-equilibrado (o cuatro, si contamos las dos equivalencias simtricas).
Estas dos (o cuatro) situaciones se muestran en la figura en la que X e Y son
nodos y A, B y C son subrboles cuyas alturas se dan en trminos de h.
Identificar qu casos surgen es una operacin de pattern matching.
Si el rbol resultante no est equilibrado, se realizan una o dos rotaciones
para volver a tener el rbol en equilibrio.
Ficheros indexados
44
rbol AVL, caso I, rotaci n si mpl e (rbol derecho no -equi l i brado).
Ficheros indexados
45
rbol AVL, caso I, rotaci n si mpl e (rbol i zqui erdo no -equi l i brado).
Ficheros indexados
46
rbol AVL, caso II, parte 1 (despl azami ento a l a derecha).
Ficheros indexados
47
rbol AVL, caso II, parte 2 (despl azami ento a l a izqui erda).
Truco: En si tuaci ones del caso I l os si gnos en l os factores de
equi l i bri o de nodos X e Y son l os mi smos, mi entras que l as
del caso II l os si gnos son di sti ntos.
Ficheros indexados
48
Discusin
Como mximo, slo se necesita una transformacin, ya sea una rotacin simple
o doble, para cada insercin de un nodo en un rbol AVL. Realizamos la
transformacin si es necesaria tras cada insercin mejor que esperar hasta que
todos los nodos hayan sido insertados y entones transformar el rbol. Este
procesamiento extra que estamos realizando en el momento de la insercin para
balancear el rbol tendr sus resultados en el momento de recuperar dndonos un
rendimiento mejor. Adems veamos que tenemos limitado el peor caso a O(log
2
n)
para el acceso directo, lo cual es una ventaja.
Al gori tmo 4.1
INSERCION AVL
I. Insertar el registro en el rbol AVL utilizando el procedimiento de insercin en
rbol de bsqueda binario.
II. Ajustar los factores de equilibrio para todos los nodos en el camino desde el
padre 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 la
transformacin apropiada
Como ejercicio: Hacer ejemplo anterior
Ficheros indexados
49
Para facilidad en la implementacin, conforme recorremos el rbol AVL
para determinar la posicin adecuada para insertar un registro, deberamos
mantener dos punteros adems de aquel para recorrer el rbol. Deberamos
guardar aquellos punteros hacia los nodos ms recientes en el camino de
insercin con un factor de equilibrio de 1 y su padre.
El puntero siguiente para el nodo con el factor 1 se necesita para identificar
el nodo cuyo campo enlace debe modificarse para unirse al subrbol
transformado en el resto del rbol ya que el subrbol transformado puede tener
un nodo raz diferente despus de la transformacin.
Todas las situaciones del desequilibro del rbol se indican con factores de
equilibrio de 2 del nodo raz del rbol no-balanceado. Por tanto, slo un nodo que
tuviera un factor de equilibrio de 1 antes de la insercin es candidato para ser el
nodo raz de un subrbol sin balancear. Si no existe un nodo en el camino de
insercin con un factor de equilibrio de 1, sabemos que podemos insertar un
registro sin encontrar un rbol sin balancear.
El nodo con tal factor de equilibrio identifica un subrbol potencialmente no-
equilibrado. Sabemos que slo se necesita una transformacin de un rbol no
balanceado para volver a equilibrarlo. Cuando insertamos un registro, un factor
de equilibrio puede cambiar como mucho en 1 (puesto que estamos
aadiendo slo un registro).
Ficheros indexados
50
Necesitamos actualizar los factores de equilibrio de todos los nodos en
un rbol AVL despus de una insercin? No, afortunadamante, la regin de
modificacin se localiza slo en el subrbol que no se encuentra
equilibrado. Por qu esto? Vase que las cuatro (dos) transformaciones
reducen la profundidad del subrbol en uno.
4.4.3. rboles B
El rbol B es una de las estructuras de datos ms importantes en
informtica por sus caractersticas de versatilidad y rendimiento. Es una
buena eleccin para el almacenamiento de datos que deben ser accedidos
tanto directamente como secuencialmente. Comer describe el rbol B como
omnipresente. Esta omnipresencia es resultado de su utilidad. De dnde
viene la B? El origen de este trmino no est claro, podra venir de balanced
(balanceado o mejor equilibrado), o broad(ancho)o bushy(espeso, poblado).
Uno de sus creadores se llamaba Bayer y trabajaba para Boeing.
Cuando insertamos un nodo tal que nos lleva a un desequilibrio,
aumentamos la profundidad del rbol en uno. De modo que despus de una
transformacin, el efecto es que la profundidad del rbol no ha cambiado
como resultado de la insercin; por tanto, ninguno de los otro factores de
equilibrio son afectados.
Ficheros indexados
51
La nica cosa de la que seguro no viene la B es de binary (binario). Un rbol
binario tiene un factor de bifurcacin (nmero de ramas que salen de un nodo)
nunca mayor de 2, mientras que un rbol B no tiene lmite terico. El mayor
factor de bifurcacin es una consecuencia de almacenar mltiples registros por
nodo. Por tanto, en contraste con los rboles binarios de bsqueda
considerados, un rbol B es un rbol de bsqueda multicamino.
En trminos de su formacin, las estructuras de rbol que hemos visto hasta
aqu han crecido de arriba abajo; es decir, la altura del rbol crece insertando un
nuevo nodo en la parte baja del rbol. El nodo raz permanece igual pero los
nodos terminales cambian conforme nuevos elementos se aaden. Con un rbol
B, los nuevos registros se insertan en el nivel hoja, pero es el nivel raz o copa
del rbol la que cambia si el rbol B debe incrementarse en altura. Una ventaja
del patrn de crecimiento bottom-up (de abajo a arriba) es que preserva
automticamente un equilibrio a la estructura sin necesidad de rotaciones o
transformaciones como en los rboles AVL o los IPR.
Este equilibrio coloca un lmite superior en el peor caso de rendimiento para
acceder a un registro sencillo. Puesto que el factor de bifurcacin es normalmente
mayor para un rbol B que para un rbol AVL o IPR, su profundidad es menor para el
mismo nmero de registros. Cuanto menos profundo sea significar menos pruebas
de recuperacin, lo que por tanto significa un rendimiento mejorado.
Ficheros indexados
52
Tambin vamos a ver (muy por encima) no slo los rboles B, sino tambin dos
de sus variantes el llamado B# y el B+. ojo! La terminologa para los rboles B
no es muy uniforme; por lo que hay que leer las definiciones con mucho cuidado
cuando usemos otras fuentes de informacin sobre rboles B.
La composicin de un nodo de rbol B es similar a un bucket o bloque de registros
en el que se contiene adems mltiples entradas. El nmero de registros que deben
almacenarse en un nodo es dependiente del orden de capacidad. El orden de
capacidad y otras restricciones en un rbol, B se especifican en su definicin formal.
Se dice que cada nodo en un rbol B de orden de capacidad d tiene:
Defi ni ci n :
Cd claves 2d (excepto el raz que tiene entre 1
y 2d claves)
d +1 punteros 2d +1
(excepto el raz que tiene entre 2 y 2d +1 punteros)
CTodos los nodos hoja estn en el mismo nivel.
Ficheros indexados
53
Todos los nodos excepto el raz deben tener una utilizacin de almacenamiento
de al menos el 50%. Los punteros en un nodo apuntan a los nodos
descendientes (en el siguiente nivel ms bajo) del rbol B; ya que los nodos hoja
no tienen descendientes, sus punteros estarn a NULL (representado por ). El
nmero de punteros en un nodo que no sea hoja es uno mayor que el nmero de
registros almacenados en el nodo. De esta definicin entonces, un rbol B de
orden de capacidad uno tiene nodos con una o dos claves y dos o tres punteros,
representndolo as:
Aunque solo ilustramos el campo clave en la porcin del registro de un nodo,
hay que tener en cuenta que el registro entero est almacenado ah. Cuando un
nodo se llena, se separa en dos nodos y el registro del medio de un conjunto de
registros, compuesto de los existentes en el nodo y aquel que vamos a insertar,
se eleva (se empuja) hacia el prximo nivel ms alto. El registro del medio se
escoge basndose en el orden de la clave.
Ficheros indexados
54
Al gori tmo 4.2
INSERCIN RBOL B
I. Recorrer el rbol B como un ndice para localizar el nodo hoja adecuado para
insertar un nuevo registro. Si es menor, ir a la izquierda; si es igual el registro est
duplicado; si es mayor y existe otro registro a la derecha, repetir las comparaciones
anteriores para menor e igual con ese registro; sino, toma la rama de la derecha.
II. Si hay espacio disponible, insertar el nuevo registro en su posicin lexicogrfica
en el nodo hoja, sino mientras exista una condicin de desbordamiento
A. Si un nodo desbordado es un nodo raz, crear un nuevo nodo raz en una
posicin padre del actual nodo raz.
B. Separar el nodo desbordado en dos nodos.
C. Elegir el registro del medio basndose en el orden lexicogrfico de entre los
registros que tenemos y el nodo desbordado. Elevar el registro medio a su
nodo padre y colocarlo en su posicin lexicogrfica correcta.
D. Colocar los registros cuya ocurrencia lexicogrfica est antes del registro
medio en uno de los nodos y colocar los nodos restantes en otro nodo.
E. Poner los campos puntero en el nodo padre hacia el que el registro medio es
elevado. Poner el puntero a la izquierda del registro elevado hacia el nodo con
la mitad lexicogrficamente ms baja de los registros divididos. Poner el campo
puntero a la derecha del registro elevado hacia el nodo con la mitad ms alta
de los registros divididos.
Ficheros indexados
55
Ejempl o
- Empecemos con el rbol B de orden de capacidad uno. Para los datos,
usaremos nombres de animales de tres letras (en ingls), nicamente para
escribir lo mnimo posible.
Cat, ant, dog, cow, rat, pig y gnu
- Primero insertamos cat, lo cual nos da
- Entonces aadimos ant; aun tenemos espacio para un nodo, por lo que
separar no es necesario. Reorganizamos los dos registros dentro del nodo
para mantener un orden alfabtico y tenemos:
- A continuacin, aadimos dog. Esto causa una condicin de desbordamiento.
Cul es la clave en el registro medio? Es cat, el cual entonces es elevado al
siguiente nivel ms alto. El nodo en el nivel hoja est dividido en dos nodos y
creamos un nuevo nodo raz con cat en l- Esta separacin aumenta la altura del
rbol B en uno, pero veamos que el crecimiento es en lo alto del rbol. El rbol B
entonces se convierte en:
Ficheros indexados
56
(Los punteros apuntan a los nodos no a los campos dentro de los nodos).
- El registro con cow como clave se aade ahora. Para encontrar el nodo
adecuado para esta colocacin, recorremos el rbol B usando un procedimiento
similar a aquel que se usa para insertar en un rbol binario. Comparamos la
clave del registro que estamos insertando con la clave del registro ms a la
izquierda en el nodo raz.
* Si la comparacin es menor que, tomamos la rama izquierda.
* Si es igual, tenemos un registro duplicado, o hemos encontrado el registro que
estbamos buscando en la recuperacin.
* Si la comparacin es mayor que, entonces comparamos con la clave del
siguiente registro en el nodo. Y entonces repetimos el proceso de comparacin.
- Seguimos el puntero a la izquierda del registro con la clave con la que estamos
comparando hasta una comparacin menor que con xito. Si tenemos una
comparacin mayor que con la ltima (ms a la derecha) clave de uno nodo,
tomamos la rama ms a la derecha que sale desde ese nodo.
Ficheros indexados
57
- Siguiendo este proceso con cow, lo insertamos en el nodo que contiene a dog.
La clave para el siguiente registro es rat. Esta corresponde con el nodo hoja con
cow y dog; de modo que es promovida al nivel raz. El nodo hoja original se
separa en dos nodos. Puesto que hay espacio en el nodo raz para dog, no es
necesario separar ms. El rbol B entonces tiene esta apariencia:
- Detalle importante: todos los registros se insertan en nodos hoja. Slo
siendo subido desde un nivel ms bajo un registro es insertado en un nodo que
no sea hoja.
A continuacin aadimos [Link] que pig es lexicogrficamente mayor que cat,
entonces comparamos con dog. Una vez ms tenemos un resultado mayor
que pero puesto que dog es el ltimo registro en el nodo, tomamos una rama
derecha que apunte al nodo que contiene rat. Hay espacio en ese nodo, de
modo que la insercin se completa. El rbol B se queda:
Ficheros indexados
58
- El ltimo registro es gnu y su clave. Este registro nos lleva al nodo hoja con
pig y rat. Este nodo est lleno, por lo que dividimos. Pig se mueve al nivel raz,
y el nodo hoja se divide en dos nodos. Ya que el nodo raz est lleno, no hay
espacio para el registro que se ha ascendido. El nodo raz debe separarse en
dos nodos, un nuevo nodo raz (y nivel) se crea. El nivel del rbol B aumenta
en uno. El rbol B final queda como indica la siguiente figura.
Ficheros indexados
59
Debido a que el rbol B es una estructura de datos tan importante, incluimos
otro ejemplo para fortalecer la comprensin de los mecanismos ms bsicos.
Los datos para este ejemplo son numricos. Empleamos un orden de capacidad
mayor, dos, en este segundo ejemplo tendremos ms datos. Los pasos de
insercin se ilustran en la figura que se explica por s sola (ver fotocopias).
Hay muchas caractersticas interesantes sobre los rboles B resultantes. Veamos
que las estructuras de rbol estn balanceadas, y que no se necesitan rotaciones.
Adems, el balanceo del rbol no era dependiente del orden de insercin de los
registros como suceda con el rbol binario de bsqueda.
Di scusi n
Podemos recuperar un registro sencillo recorriendo el rbol como hacamos en
la insercin. Si encontramos un puntero nulo antes de encontrar un
emparejamiento, eso significa que el registro no se encuentra en el rbol, B y
esta circunstancia terminara el proceso de bsqueda. Un rbol B es una
estructura para almacenar grandes cantidades de informacin; por tanto, los
nodos del rbol B normalmente se colocan en almacenamiento secundario.
Ficheros indexados
60
Una prueba de recuperaci n para un rbol B se define como un acceso
a un nodo, no a un registro.
En el rbol B de la figura se necesitaban tres pruebas para recuperar gnu,
mientras que dos pruebas se necesitan para recuperar el registro con clave
150 en el rbol final de la otra figura. Puesto que un rbol B est equilibrado,
el peor caso de rendimiento de recuperacin est limitado por su altura, que
se especifica por
Altura log
d
( (n+1) / 2 )
Para d > 1, donde n es el num de regs almacenados en el rbol B. Puesto que
la altura del rbol B es O(log
d
n), el peor caso de rendimiento de recuperacin
es entonces O(log
d
n). Un rbol B de orden de capacidad 50 que contiene un
milln de regs requiere como mucho cuatro pruebas de recuperacin para
localizar un reg. El peor caso de rendimiento de recuperacin para un rbol B es
menor que lo que sera en un rbol AVL o IPR ya que el rbol B tiene un mayor
factor de bifurcacin.
Cuando se accede a un nodo, su contenido se copia a memoria principal. La
bsqueda siguiente que puede ser necesaria para localizar un registro con un
nodo es insignificante cuando comparamos con el tiempo requerido para acceder
al nodo en almacenamiento secundario.
Ficheros indexados
61
Podemos adems procesar los datos del rbol B secuencialmente recorriendo
los nodos del rbol en inorden. Puesto que tenemos ms de dos caminos el orden
es izquierda, nodo, puntero, nodo, puntero, ..., o siguiendo las lineas alrededor
del permetro del rbol B como se muestra.
Empezando con el nodo ms profundo a la izquierda, en este caso A, los nodos
se procesan en el camino hacia dentro de la estructura ms que un camino hacia
fuera, o en este diagrama, en un camino hacia arriba ms que hacia abajo.
Ficheros indexados
62
nmero de slotsde almacenamiento disponibles
nmero de registros almacenados
Esto es bsicamente el packing factor de un rbol B. Para un rbol B como el
de la figura, la utilizacin de alm 7/14, o del 50%. En el rbol B de la otra figura,
la utilizacin del espacio de la estructura final es incluso menor 17/36 o del 47%
- puesto que el nodo raz no est ni siquiera medio lleno. A utilizacin del
almacenamiento es la ms pequea inmediatamente despus de dividir. Una
ventaja del rbol B# que veremos despus es su mayor utilizacin del espacio.
Al tracear los caminos del permetro alrededor de las estructuras finales
de los dos rboles B ejemplo obtenemos un orden lexicogrfico de lo datos en los
nodos. Tal orden es apropiado para un procesamiento secuencial.
Cul es la utilizacin de almacenamiento para el rbol final de orden uno? La
utilizacin de almacenamiento del rbol B es:
BORRADO
El borrado, como cabra esperar es el opuesto a la insercin. Cuando
eliminamos un reg de un nodo, debemos mantener tanto las restricciones de
un rbol B para una utilizacin mnima del espacio como la estructura de
ndices para recuperar los registros
Ficheros indexados
63
Si el registro borrado est en un nodo hoja y la restriccin de mnima
capacidad se mantiene, ningn otro nodo en el rbol est afectado por el
borrado. Si el registro borrado, sin embargo, es un nodo no-hoja, necesitamos
mover un registro desde el nodo hoja hacia la posicin del registro borrado para
mantener una clave con la que comparar cuando buscamos el ndice.
rbol es B#
Una observacin sobre los ejemplos de insercin en el rbol B fue que el
espacio de utilizacin era ligeramente por debajo del 50% despus de la divisin
final. Este es un porcentaje relativamente bajo que significa que ms de la mitad
del almacenamiento no est siendo usado. Debido a las restricciones de la
capacidad minimal, el 50% es el utilizacin de espacio ms baja para todos los
nodos excepto el raz. Como resultado, la utilizacin de almacenamiento es sobre
todo ligeramente por debajo del 50%: la utilizacin de almacenamiento mxima
es el 100%, pero esa utilizacin no se dara a menudo con datos aleatorios.
Ficheros indexados
64
Podemos mejorar el espacio de utilizacin de la estructura del rbol B?
S, una forma de conseguir un incremento es postponer la divisin durante la
insercin puesto que la divisin reduce la utilizacin del espacio. Dividir
puede adems aumentar la profundidad del rbol B, lo cual afectar
negativamente al rendimiento de recuperacin. Llamamos a esta versin del
rbol B rbol B#, es una variante del rbol B*.
Un rbol B# es un rbol B en el que las operaciones de divisin e insercin
se procesan de un modo que postpone la divisin y como resultado posee una
mayor utilizacin del espacio y un rendimiento de recuperacin ms rpido.
Retrasa la divisin y con ello, da un espacio de utilizacin minimal de
aproximadamente 2/3. Los procesos de recuperacin y borrado funcionan como
en el rbol B. La idea bsica de rbol B# es para (1) postponer la divisin
redistribuyendo los registros del nodo desbordado en hermanos adyacentes y
(2) cuando es necesario dividir, convertir de dos a tres nodos. Estas
modificaciones mantienen los nodos mucho ms utilizados.
La diferencia principal entre el rbol B# y el rbol B * es que el nodo raz en
un rbol B* es mayor que los otros nodos en el rbol y puede contener 4d+1
registros. Todos los nodos de un rbol B# son del mismo tamao, de modo que
es esencialmente un rbol B con un algoritmo de insercin modificado.
Ficheros indexados
65
rbol es B+
Un rbol B+ es una variante de un rbol B. Como el nombre implica, tiene sus
ventajas sobre un rbol B normal.
Obtenemos un rbol menos profundo con una estructura B+ al incrementar el
nmero de claves que podemos almacenar por nodo. Puesto que normalmente
tenemos un lmite en el tamao del nodo (por ejemplo, el tamao de la pgina
fsica), conseguimos este aumento almacenando slo los campos clave en los
nodos no terminales del rbol. Puesto que los campos clave son slo un
subconjunto del registro entero, podemos almacenar ms de stos en una
cantidad fija de espacio reservada para un nodo.
Una segunda ventaja es que no es necesario movernos hacia arriba y hacia abajo
por los nodos del rbol en inorden para obtener un orden lexicogrfico de los
datos, de modo que el procesamiento secuencial es ms rpido. Entonces
podemos mejorar los procesamientos de un rbol B tanto el secuencial como el
directo usando un rbol B+.
Una ventaja es que es normalmente menos profundo que un rbol B con los
mismos datos, lo que significa que se necesitan menos pruebas para un acceso
directo.
Si almacenamos slo los campos clave de los nodos no-hojas, dnde se
encuentran los registros reales almacenados? Los almacenamos en los nodos hoja.
Ficheros indexados
66
Los nodos no-terminales actan entonces como un ndice en los nodos
terminales que contienen los datos. En contraste con un rbol B, un rbol B+
tiene la estructura de ndices distinta de la estructura de almacenamiento. Un
resultado de este cambio de estructura es que cada uno de los registros requiere
el mismo nmero de pruebas para localizarlo en una recuperacin de acceso
directo ya que todos los registros estn almacenados al mismo nivel.
Un rbol B+ es un rbol B en el que los registros de datos estn
contenidos en nodos terminales, y los nodos no-terminales, que slo
contienen valores de claves, forman un ndice en los nodos de datos.
Otros Ejemplos

Ficheros indexados
67
4.5. ISAM y VSAM
Ficheros ISAM (Indexed Sequential Access Method)
Para buscar registros en un fichero que es dinmico (es decir, donde hay
muchas inserciones y borrados) un fichero no ordenado no es bueno, un fichero
ordenado degenera rpidamente. Una solucin a este problema es mantener
una tabla de bsqueda, o ndice, para los registros.
Del mismo modo en el que pocos informticos escribirn rutinas de ordenacin
para ficheros grandes, es tambin poco probable que ellos programen
estructuras de ndices. Existen muchos programas disponibles que son muy
buenos. La mayora son sistemas de administracin de base de datos incluyendo
rutinas de ordenacin y utilidades de rboles B y tablas hash. El sistema de
ficheros VAX (Virtual Address eXtention) incluye elecciones elaboradas de
ficheros indexados. Los mainframes de IBM ofrecen VSAM que es una utilidad
de rbol B+. Para usar estos productos de manera inteligente, deberamos
aprender cmo trabajan y qu rendimiento hay que esperar.
ISAM es una organizacin de ficheros y una tcnica de procesamiento usada
para acceder a registros en un orden secuencial lgico o en un orden aleatorio
lgico en base a una clave, o identificando un elemento de datos, de los
registros de datos individuales.
Ficheros indexados
68
El ndice ms sencillo es una lista en orden del valor de la clave normalmente
un campo del registro (como puede ser el nmero de la seguridad social de un
paciente en un hospital) y las direcciones de los registros con valores de clave
dados. A veces esto se llama ficheros invertidos. Sin embargo, esto es difcil de
mantenerse por s mismo, ya que la lista entera ha de desplazarse cuando se
aaden nuevos registros.
Para solucionar este problema, muchas estructuras de ficheros se han
intentado, pero slo dos estructuras han resistido el test del tiempo y se usan
para ficheros dinmicos.
Estas dos estructuras son los rboles B+ y el hashing. Algunos otros mtodos,
como los rboles AVL y los rboles binarios de bsqueda, no se han usado nunca
para ficheros grandes. Otros, como el ISAM, se usaron pero se han encontrado
inferiores a los rboles B+ de modo que se usan muy raramente.
Ficheros indexados
69
Sin embargo, en el pasado se usaron extensivamente, particularmente en
sistemas IBM. Este mtodo ahora se considera inferior a los rboles B+, pero
quedan algunos pocos ficheros ISAM. A veces los sistemas que han sido
cambiados a rboles B+, tales como el sistema de administracin de base de
datos INGRES, todava llaman a su estructura de ndices ISAM, con el fin de
cambiar la interfaz de usuario lo menos posible. Esto es, la organizacin de
ficheros etiquetada como ISAM hoy puede que no sea la tradicional IBM ISAM,
pero puede estar implementada como un rbol B+.
Ficheros indexados
70
Este mtodo usa un fichero de datos secuencial y un ndice secuencial.
Divide el espacio del soporte en tres zonas: rea de Datos, rea de
ndices y rea de Desborde, las cuales se subdividen en otras segn la
estructura de los soportes. Los datos se organizan en pistas y stas en
cilindros lgicos
La pista 0 de todos los cilindros se reserva para crear los llamados
ndices de pistas y alguna ms para los excedentes del cilindro (al final).
Cuando se llene una pista se pasa a la siguiente pista libre de ese mismo
cilindro (se va rellenando cilindro a cilindro). Al rellenar una pista se crea en
el ndice de pista una entrada con la clave de mayor orden de esa pista y un
puntero a esa pista.
ISAM
Al llenar un cilindro, en el rea de ndices se crea una entrada en el
ndice de cilindros con la clave de mayor orden y un puntero al cilindro.
Ficheros indexados
71
Puede existir un tercer ndice, el ndice maestro, muy pequeo que
apunta al ndice del cilindro.
La mejora que obtenemos con este mtodo es que al poder llevar
una pista entera a memoria principal se trabaja ms rpido; si al hacer
una insercin excedo el tamao de la pista el/los registro/s excedente/s
va/n a las pistas del rea de excedentes del cilindro.
Tratamiento de los registros excedentes.
Pueden al macenarse en una zona (un cilindro o ms) exclusiva para ellos.
Otra forma sera reservar pistas para los registros excedentes al final de cada
cilindro. Por ltimo una tercera forma consiste en una mezcla de las dos
anteriores, es decir tener pistas al final de los cilindros y una zona exclusiva.
Esta 3 forma es la ms utilizada, ya que la 1 presenta el inconveniente
de tener que hacer movimientos de las cabezas del disco para acceder a
los excedentes, y la 2, aunque no tiene este problema tiene otros dos
inconvenientes: que se puede agotar el espacio reservado o bien que por
miedo a que esto ocurra se desaproveche mucho espacio en el soporte.
Ficheros indexados
72
Para l ocal i zarl os segn qu tcnica empleemos tardaremos mucho
(bsqueda secuencial, ndice de pistas para los Excedentes). La tcnica
ms empleada consiste en que en el ndice de pistas cada entrada sean en
realidad dos entradas, una para los registros almacenados normalmente, y
otra para los Excedentarios.
Por tanto cada entrada estar compuesta por una entrada N que ser un
puntero a la pista y como clave la mayor de la pista, y una entrada O que
tiene un puntero a la menor entrada correspondiente a esa pista que est
en el rea de Excedentes y como clave la mayor de dichos Excedentes
Para no tener muchos excedentarios se suelen crear registros falsos
hacia el final de las pistas. Tienen dos funciones: si llega un registro con
la misma clave que uno falso simplemente sobreescribimos el falso y si no
el que saldra sera uno falso que no amplia la zona de excedentes. Esta
es la nica forma de dejar huecos que se puede emplear en ISAM.
Ficheros indexados
73
Vista general de un fichero ISAM
R
memoria primaria
Mem. secondaria
61
10 20 50 61 101
30 40 45
D C A
1 3 10
A B A
11 20
C D
51 55 57
A D B
65 70101
E B C
120150
A D
50
D
60
B
61
A
a
b c
i h g f e d
Registros de descripcin part
PART #
PART-Type
Clave primaria
Ejemplo : Estructura de un secuencial indexado (con cadena de desbordamiento)
Ficheros indexados
74
Por qu interesan este tipo de ficheros en general?
Mtodo de acceso secuenci al
Soportado por cualquier sistema capaz de emplear ficheros como E/S.
Simplemente lee/escribe registros uno tras otro, en un orden fsico.
Cuando se crea un registro ha de aadirse al final del fichero.
Si orden, insertar registros es ms complicado (reorganizacin o desbordamiento).
Para buscar tambin bsqueda secuencial.
Modificaciones igualmente costosas.
Mtodo de acceso al eatori o
Ms flexible
Se pueden escribir en cualquier lugar del fichero conociendo la posicin relativa
o nmero de registro del registro buscado.
As, un registro particular puede ser recuperado usando una rutina aleatoria para
calcular el nmero de registro para la clave del registro.
Modificaciones igualmente costosas.
Ambas organizaciones son ideales para usos particulares. Pero para algunas
aplicaciones donde necesi tamos acceder a l os regi stros secuenci al o
al eatori amente medi ante sus cl aves asoci adas, ISAM proporciona una
aproximacin mucho ms directa.
Ficheros indexados
75
Hay dos estructuras de datos principales en un fichero ISAM: el
fichero de ndices y el fichero de datos.
El Fichero ndice
El Fichero de Datos
Contiene registros ndice que proporcionan punteros asociados a registros de
datos basados en un elemento nico e identificador en cada registro
denominado clave.
Puede haber mltiples niveles de ficheros ndice. En este caso el nivel de
ndice ms alto llamado a veces ndice maestro, apunta al siguiente nivel
inferior que apunta al siguiente nivel inferior y as.
El nivel ms bajo apunta a los registros de datos. Podra haber tambin ndices
secundarios que proporcionan acceso a los registros de datos a travs de una
clave secundaria como puede ser un nombre o una descripcin.
El fichero de datos contiene registros de datos, cada cual con su clave nica.
El fichero de datos puede estar en orden de clave o en un orden secuencial
fsico segn la implementacin de ISAM.
Ficheros indexados
76
La estructura del fichero ISAM proporciona mucha ms flexibilidad
que otras organizaciones y se prestan mejor a aplicaciones
sofisticadas de tiempo real e interactivas
C Consultas
La primera aplicacin de los ficheros ISAM que viene a la mente es la de
consultar. Una consulta proporciona la habilidad de recuperar informacin
asociada con un registro nicamente introduciendo la clave de registro.
Por ejemplo, en un sistema de control de inventariado, el administrador
podra querer la capacidad de ver cunto stock hay antes de realizar un
pedido.
Usando una estructura de fichero ISAM, se podra escribir un programa para
solicitar un nmero de item desde el operador, recuperar el correspondiente
registro del fichero ISAM, y visualizar la informacin sobre el status del
stock en la pantalla.
Ficheros indexados
77
2 Edicin (insercin)
Un elemento de datos en un fichero podra ser la clave de un fichero ISAM.
Si este es el caso, siempre que se introduzca un elemento de datos debera
verificarse su validez inmediatamente haciendo una bsqueda de la clave en
ISAM.
Por ejemplo, en una aplicacin de nminas los registros de las pagas
semanales contendrn el nmero de empleado. Conforme se escribe el
nmero de empleado ste puede usarse como la clave para buscar en el
fichero maestro de empleados. Si no hay ninguna coincidencia, el operador
puede informar inmediatamente de que el nmero de empleado no es
vlido.
Ficheros indexados
78
C Actualizacin (modificacin)
Posiblemente la aplicacin ms til de las estructuras de fichero ISAM es la
actualizacin en tiempo real. Un registro puede actualizarse inmediatamente
conforme cualquier transaccin lo altere haciendo que la informacin actual
est disponible en una base de tiempo real.
Esto podra usarse normalmente en conjuncin con las consultas.
Por ejemplo, en un sistema de contabilidad, los pagos podran aplicarse
directamente a las cuentas asociadas realizando una recuperacin del
registro mediante clave (nmero de cuenta), restando el pago del balance,
y reescribiendo el registro. Cualquier consulta sobre el status de una cuenta
podra mostrar el balance como el de aquel punto temporal, incluso si el
pago se ha aplicado slo unos cuantos segundos antes.
Ficheros indexados
79
Ficheros VSAM (Virtual Storage Access Method)
Ya hemos visto los llamados mtodos de acceso tradicionales. Cada uno de
ellos han estado presentes desde hace muchos aos, a pesar de los
inconvenientes que pudieran poseer.
Una de las versiones ms tempranas de un interfaz comn para realizar la
E/S se incorpor a un producto conocido como VSAM.
Ficheros indexados
80
Antes de este producto, un usuario tena que aprender un interfaz para
pedir acceso ISAM a los registros y otro interfaz para realizar E/S secuencial
estndar, y as. Esta situacin era obviamente ms difcil para mantener y
escribir programas.
Otro punto que concierne est relacionado con el hecho de que las
organizaciones de ficheros que se discutan antes necesitaban funcionalidad, an
juntas con cada tipo de fichero traan algunas penalidades significantes. Por
ejemplo, vimos cmo los ficheros secuenciales podan leerse rpidamente, quizs
la ms rpida de todas las organizaciones, aun no hay capacidad de acceso
aleatorio.
Por tanto, una de las rupturas que se consiguieron con VSAM y productos
similares fue el dar un gran paso en estandarizar el interfaz usuario/programacin
hacia los mtodos de acceso y el sistema de ficheros bsico.
Los ficheros relativos proporcionaban al usuario un acceso aleatorio a los
registros de datos extremadamente rpido, las claves eran todava enteros nicos.
Adems, se usaban las celdas de longitud fija incluso si los registros del fichero se
declararan como de longitud variable. De manera alternativa, los ficheros relativos
proporcionan tanto acceso aleatorio como secuencial. Sin embargo, el rendimiento
de los mtodos de acceso secuenciales depende de si los registros en el fichero
son densos o no-densos.
Ficheros indexados
81
Los ficheros directos valores de claves normales (es decir, no
restringidos nicamente a valores enteros). Adems, hacan un mejor uso del
espacio de disco del fichero que los ficheros relativos. Sin embargo,
hacindolo as, los ficheros directos quitan al usuario la capacidad de realizar
acceso 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 del
usuario. Es ms, el usuario ya no tiene que conocer detalles tcnicos del
dispositivo 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 registro
puntero en el nivel ms bajo del ndice, el cual es denso). Adems, los datos de
usuario 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 registros
de datos usando valores de clave normales y acceso secuencial a los datos. En
cambio, el usuario tiene que saber mucho sobre las caractersticas tcnicas del
dispositivo que est siendo usado., ya que la ubicacin del fichero est relacionada
directamente con las capacidades del cilindro y la pista de una unidad especfica.
Adems, utilizando reas de desbordamiento, si el usuario acta de manera
errnea en el diseo y ubicacin del fichero, el rendimiento se degrada
dramticamente.
Ficheros indexados
82
VSAM Using a Key-Sequence Data Set (KSDS) Structure
Ficheros indexados
83
VSAM File Example Using Customer Numbers
Ficheros indexados
84
VSAM Split Internal Example
Ficheros indexados
85
Hay tres modos de organizacin:
Uno para ficheros secuenciales (ESDS)
Otro para ficheros de acceso directo o registros de direccin calculada
(RRDS)
Otro para ficheros secuenciales indexados (KSDS)
RRDS =Conjunto de datos de registro relativo.
ESDS =Conjunto de datos en secuencia de entrada.
KSDS =Conjunto de datos en secuencia de clave.
Los tres modos se diferencian de ISAM en que son i ndependi entes
del hardware o soporte. VSAM independiza las unidades de
transferencia del soporte. Su unidad de transferencia son los intervalos
de control, los ficheros son mucho ms transportables que los de ISAM.
Los intervalos se agrupan en reas de control (puede ser o no un cilindro).
KSDS - Key Sequence Data Set.
ESDS - Entry Sequence Data Set.
RRDS - Relative Record Data Set.
[Link]
Ficheros indexados
86
Dentro de los intervalos de control se pueden dejar espacios libres al final
de los mismos y en un rea puede haber intervalos completamente vacos.
KSDS permite que el ndice est organizado como un rbol B+.
El tamao de un rea de control suele estar definido por el sistema, lo
que se permite es definir el nmero de intervalos que se quiere que estn
vacos. Podemos definir la longitud de los intervalos de control.
rea de Datos + rea de ndices = Cluster
En el rea de ndices se tendr un rbol B+. Cada nodo del rbol ser un
intervalo de control. En las hojas se encuentran todas las claves y los nodos
de las hojas estn enlazados por punteros. Las hojas forman lo que se
llama conjunto de secuencias. Los elementos de dicho conjunto son los
nodos con entradas que sern: como clave la mayor contenida en un
intervalo de control del rea de datos, y un puntero a ese intervalo del rea
de datos.
Ficheros indexados
87
Cuando hay varios intervalos vacos habrn nodos que lo indiquen y un
puntero a esos intervalos.
El acceso directo se hace con la bsqueda en el rbol. El acceso
secuencial se hace empleando los punteros horizontales que enlazan las
hojas del ndice.
Los registros de datos pueden ser de longitud fija o variable, y al
principio de cada intervalo hay unos caracteres de control que indican el
nivel de ocupacin (interesa al hacer un recorrido secuencial).
Al eliminar un registro los que estn a su derecha se movern a la
izquierda dejando siempre los espacios libres al final del intervalo. Y si
algn intervalo quedara vaco aparecer en el conjunto de secuencias
como una entrada de vaco (esto se llama reclamacin dinmica de
espacio libre).
Ficheros indexados
88
Este proceso (junto a otros que no vamos a estudiar) evitan la
necesidad de tener zonas de excedentes.
El inconveniente que tiene con respecto a ISAM es que hay que dejar
ms espacios libres, a cambio el localizar los registros es mucho ms
rpido.
Aunque hemos discutido muchos mtodos diferentes para organizar y
estructurar los datos, aun tenemos que descubrir una forma en la que
podamos tener todos los beneficios mencionados antes, aun teniendo
unos pocos inconvenientes. VSAM y otros mtodos de acceso integrados
de su poca han tomaron los pasos ms importantes para resolver el
dilema de una vez por todas.

Ficheros indexados
89
4.6. CONSIDERACIONES DE DISEO
Consideraciones de rendimiento
Puesto que las aplicaciones tienen a utilizar ficheros indexados frecuentemente,
es importante comprender los puntos relacionados con el rendimiento y qu
podemos hacer para mejorar este rendimiento. La operacin WRITE es la
operacin de registros que lleva ms tiempo completar.
Esto es porque debe aadir fsicamente un registro a una estructura de fichero
ya existente. Recordemos que la clave del rendimiento total est directamente
relacionado con el nmero real de operaciones de E/S que se pueden realizar.
Cuntas se realizan para aadir en el caso de un fichero indexado?
Como puede verse en la tabla el nmero de operaciones de E/S que tienen
lugar para una peticin del usuario aparentemente simple puede ser bastante
grande.
Ficheros indexados
90
Ficheros indexados
91
Esto es lo que cuenta para una variacin en la velocidad, o en el tiempo de
respuesta, .. Estas operaciones de E/S escondidas son la causa de las cuestiones
de rendimiento.
Una segunda consideracin en cuanto al rendimiento est relacionada con el
nmero y uso de los buffers de E/S en memoria principal. Cuantos ms hay, los
bloques ms frecuentemente usados pueden salvarse en de los buffers y no
necesitan ser reledos hasta una peticin de usuario.
El aspecto ms crtico que determina el rendimiento es el nmero de niveles en
el ndice. Este valor restringe al nivel ms alto de rendimiento posible, ya que
requiere muchas operaciones de E/S para recorrer el rbol entero. El nmero de
niveles est relacionado directamente con el tamao de bloque, registros de datos
de usuario, y tamao de la clave. Cuantos ms registros, o bien los registros de
datos de usuario o los registros de ndices, que pueden encajar en un bloque, ms
pequeo el camino del ndice ser al final.
La cantidad de memoria principal ubicada en los buffers de E/S tendr un efecto
en la cantidad de memoria real que se agota. Sin embargo, si la memoria no es un
gran problema, es mejor ubicar de algo ms en los buffers de E/S de lo que se
considera normal.
Ficheros indexados
92
Si el procesamiento READ_NEXT se realiza a menudo por el usuario, el usuario
debe considerar otras alternativas. Por ejemplo, si todos los ndices encajan en uno
o ms cilindros del disco, el mtodo de acceso podra simplemente considerar
almacenar la informacin en el ndice en un conjunto contiguo de cilindros para
minimizar el tiempo de bsqueda.
Finalmente, el rendimiento de la operacin READ_NEXT es menor que en la
lectura secuencial de todos los registros en un fichero secuencial.
Tcnicas de poblacin de ficheros
Con un fichero indexado, no es necesario aadir registros al fichero en una
secuencia especfica. La razn para esto es que la estructura del ndice ser
siempre reconstruida dinmicamente si se requiere algn cambio. Este es un
cambio dramtico desde un fichero ISAM, cuando si nosotros diseamos mal la
estructura de ndices tenemos que volver a crear los ficheros enteros.
Sin embargo, hay formas en las que el rendimiento del proceso de poblacin del
fichero, as como la utilizacin del espacio, puede mejorarse. Recordemos que en
cualquier momento un registro de datos nuevos se aade al fichero y por tanto un
registro ndice ha de aadirse al nivel 1 del ndice, puede suceder una divisin de
bloque.
Ficheros indexados
93
Puesto que este es un proceso que consume un cierto tiempo, sera beneficioso
si la mayora de este control se evitara. Se puede si, y slo si, ordenamos todos
los registros de datos por valor de claves primarias ascendente.
Entonces, conforme se va poblando el fichero, habr cero divisiones de
bloques slo se aadirn los nuevos bloques al nivel existente. Otro beneficio
de este procedimiento es que los bloques de ndice en el nivel 1 sern rellenados
ms o menos lo mismo. Por ello, el espacio entre ndices ser mejor utilizado.
Reorganizacin de ficheros
Por qu tenemos que reorganizar ocasionalmente los ficheros directos e ISAM?
Fundamentalmente, hay dos razones:
1. Cuando el nmero de registros de datos de usuario vlidos en el rea de
desbordamiento del fichero sea alto, el rendimiento como lo percibe el usuario
ser inaceptable. Reorganizar el fichero elimina las reas de desbordamiento y por
tanto el nivel de rendimiento mejora.
Ficheros indexados
94
2. La segunda razn es relativa al hecho de que no hay una forma fcil en la
que reclamar el espacio de registro borrado. Las aplicaciones que borran
muchos registros acabarn con un tamao de fichero mucho mayor del que
tendran en caso de que slo hubiese registros vlidos en el fichero. Por ello,
reorganizando el fichero, todo el espacio perdido debido a registros borrados
se recaptura. Esto adems tiende a mejorar el rendimiento porque el fichero
es ms pequeo, por tanto se reducen el nmero de SEEKs requeridos.
Los ficheros indexados no tienen rea de desbordamiento, y por tanto, por
esta 1 razn no se aplica. Sin embargo, ya que los regs se aaden siempre
en el end-of-file, no hay intento de reutilizar el espacio del registro borrado
automticamente. Y por tanto, la 2 razn se aplica directamente a los fichs
indexados, quizs aun ms de modo que cualquier otro de los tipos de fichs
que se han visto hasta ahora.
Cmo puede saber el usuario cundo hay muchos regs borrados en el fich?
No hay una forma sencilla de conocerlo que no sea escribir un programa
utilidad especial para examinar todos los regs en el fich.
Ficheros indexados
95
Si hay una diferencia importante, quizs habra que hacer una
reorganizacin. Como un mnimo, el usuario podra entonces determinar
cuntos regs hay actualmente en el fich y qu porcentaje del fich antiguo
consiste en regs borrados.
Puesto que este tipo de programa no ser normalmente facilitado por el
vendedor del producto, el usuario tendra que escribirlo. De modo alternativo,
si el usuario supiera aproximadamente cuntos regs deberan estar en el fich
en un momento dado, el usuario podra calcular el tamao potencial del fich y
comparar ese tam con el tam actual del fich.
Aspectos de diseo
Un fichero indexado representa una mejora sobre las organizaciones de
ficheros discutidas hasta aqu en que ofrece ms funcionalidad al programa
de usuario que ninguna otra de las organizaciones de ficheros. Sin embargo,
esta ganancia no viene sin costes y efectos laterales.
Ficheros indexados
96
Para calcular el nmero de niveles que se generarn, necesitamos realizar los
siguientes pasos:
1.- Estimar el nmero de regi stros de datos de usuari o que habrn en el
fichero en un periodo que nosotros elijamos.
2.- Estimar el tamao del regi stro de datos de usuario medio, incluyendo la
estructura por encima necesaria del mtodo de acceso.
3.- Calcular el nmero de bl oques requeridos para soportar el nmero
estimado de registros de datos de usuario calculado en los pasos 1 y 2. Este
clculo define el nmero total estimado de bloques requeridos en el rea de
datos primaria del fichero.
4.- Dado que hay un registro de ndices por registro de datos, estimar el nmero
total de bl oques de ndi ce de ni vel 1 requeridos para soportar los punteros
hacia los registros de datos.
Clculo del tamao de fichero
5.- Puesto que por encima del nivel 1 hay justamente un registro puntero por
cada bloque en el ndice, calcular cuntos bl oques se necesi tarn en
todos l os ni vel es restantes de la estructura de ndices. Parar cuando haya
solo un bloque de ndices en un nivel particular, porque este ser entonces el
bloque raz de la estructura de ndices.
Ficheros indexados
97
Costes frente a beneficios
Como sucede siempre que hay que resolver compromisos, hay siempre
algunas ganancias as como puntos negativos. La tabla compara la organizacin de
ficheros indexados con otros tipos de ficheros discutidos hasta ahora.
El acceso secuencial a los registros es ms lento que en los fichero
secuenciales.
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 el
fichero en el nivel 1.
Costes:
Nunca se usa un rea de desbordamiento.
El rendimiento del acceso aleatorio es consistente y predecible desde el punto de
vista del usuario.
Beneficios:
Se proporciona tanto un acceso aleatorio rpido como un acceso secuencial
razonable de los registros de datos.
Puede permitirse cambiar las claves en una operacin UPDATE.
La estructura del fichero se construye dinmicamente y crece dinmicamente
conforme el fichero se expande.
Ficheros indexados
98
PCs frente a mquinas grandes
El principal problema de los usuarios de PCs era las limitaciones de espacio
disponible y los ciclos CP (es decir, el poder de procesamiento del
microcomputador). El fichero indexado lleva asociado una cantidad considerable
de la estructura adicional al fichero.
Sin embargo, proporciona al usuario la capacidad de acceso tanto aleatorio
como secuencial para los registros de datos de usuario. Puesto que el ndice se
reorganiza solo dinmicamente, el camino hacia un registro de datos especfico
siempre se mantiene ptimo. Por tanto la estructura de fichero indexado es
bastante 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. Por
tanto, los ficheros indexados proporcionan a los usuarios una pieza importante
y con funcionalidad sin efectos negativos aparentes.
Ficheros indexados
99

Ficheros indexados
100
File Systems. Structures and algorithms Thomas R. Harbron, Prentice-Hall,
1988
Files and Databases: An Introduction Peter D. Smith G. Michael Barnes
Addison-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