Download Estructuras Basicas de Archivos

UNIDAD 2
ORGANIZACIÓN DE
ARCHIVOS
1
Temario
2.1 Estructuras Básicas de Archivos
2.2 Técnicas de Indexación
2
Estructuras de Archivos
• Una estructura de archivos es una técnica para
agrupar físicamente los registros de un archivo en
dispositivos de almacenamiento secundario.
3
Estructuras de Archivos
Aspectos a Considerar
• Características físicas de los dispositivos de
almacenamiento.
• Sistema Operativo existente.
• Software para la administración de archivos.
• Necesidades del usuario para almacenar y accesar
datos.
4
Estructuras de Archivos
Criterios Importantes
• Acceso rápido para la recuperación de datos.
• Alto rendimiento para las transacciones de
procesamiento.
• Uso eficiente del espacio en disco.
• Protección ante pérdida de datos y fallas.
• Minimización de la necesidad de reorganización de
los datos.
5
Estructuras de Archivos
Organización Lógica de los Datos
• Considera la visión del programador (o
desarrollador) de aplicaciones.
• Un archivo es visto como una colección de registros
estructurados, normalmente, en torno a una clave.
• Es una visión independiente del dispositivo, donde
interesa el uso de los datos más que sus aspectos
físicos.
6
Estructuras de Archivos
Organización Lógica de los Datos
•
•
•
•
•
Recorrer el archivo
Agregar registros al archivo
Eliminar registros del archivo
Modificar valores del archivo
Ordenar el archivo
7
Estructuras de Archivos
Organización Lógica de los Datos
a) Registro: corresponde a la definición de cada uno
de los registros de datos que serán usados dentro
de una aplicación, y cuya extensión determina el
tipo de archivo que lo contiene
Dependiendo de los tipos de registros que un
archivo contenga, éste puede ser de largo fijo o de
largo variable...
8
Estructuras de Archivos
Organización Lógica de los Datos
• Archivo de Largo Fijo: el archivo se compone de
registros del mismo tipo.
• Archivo de Largo Variable:
• El archivo se compone de registros del mismo tipo, pero al
menos uno de los campos tiene un número de ocurrencias
variable.
• El archivo se compone de registros del mismo tipo, pero el largo
de al menos uno de sus campos es variable.
• El archivo se compone de registros del mismo tipo, pero uno de
los campos es opcional en cuanto a su tipo.
• El archivo se compone de más de un tipo de registro.
9
Estructuras de Archivos
Organización Lógica de los Datos
b) Campo o Atributo (clave): ítem de dato que
describe una característica de la entidad
representada por un registro lógico...
Clave Candidata: atributo(s) que no soporta(n) valores
repetidos.
Identificador o Clave Primaria: clave candidata escogida como
clave de acceso principal al archivo.
Clave Alternativa: clave candidata que no es escogida como
identificador.
Clave Secundaria: atributo que permite valores repetidos.
Clave Inteligente: atributo cuyo contenido permite derivar
información adicional de la entidad a la cual pertenece.
10
Estructuras de Archivos
• Las diversas estructuras de archivos existentes se
pueden dividir en tres grupos:
• Archivos Secuenciales: los registros de datos se almacenan en
forma contigua.
• Archivos Directos: los registros de datos se ubican a partir de
una posición, que se obtiene de un atributo que es escogido
como clave hashing.
• Archivos organizados como Árboles: los registros de datos se
guardan en base a un atributo, ordenadamente, según una
relación jerárquica y basada en los valores de dicho atributo.
11
Estructuras de Archivos
Archivos Secuenciales
• Los registros son almacenados en secuencia, uno
tras otro. Características:
• Es la más simple de usar.
• Espacio ocupado es el mínimo, pues sólo se
almacenan los datos.
• Se pueden identificar dos tipos de archivos
secuenciales: desordenado y ordenado.
12
Estructuras de Archivos
Archivos Secuenciales Desordenados
• Los registros se almacenan unos tras otros, según
el orden en que van siendo ingresados
• Operaciones
• Búsqueda: Se realiza en forma lineal.
• Inserción: Se realiza al final del archivo, lo que hace
que la operación sea rápida.
• Eliminación: Se puede presentar de dos formas:
• Física: lo cual implica corrimientos de los datos, para
cubrir la entrada liberada (costoso).
• Lógica: a través de marcas de borrado.
13
Estructuras de Archivos
Archivos Secuenciales Desordenados
Archivo Secuencial Desordenado (factor de bloqueo 4)
14
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Los registros se encuentran almacenados en forma
ordenada (ascendente o descendentemente)
respecto del valor de un campo de ordenamiento.
• Favorece las búsquedas y la generación de listados
ordenados.
• Operaciones
• Búsqueda: Se realiza en forma lineal y/o binaria.
• Inserción: Requiere un corrimiento de los registros para
mantener el orden...
15
Estructuras de Archivos
Archivos Secuenciales Ordenados
Archivo Secuencial Ordenado, ordenado por el campo Nombre
16
Estructuras de Archivos
Archivos Secuenciales Ordenados
• ...el que se puede evitar...
• Dejar los bloques de datos a medio llenar, para
reservar espacio para posibles inserciones futuras.
Mientras no se llenen, habrá desperdicio de memoria.
• Mantener un área de overflow a continuación del área
de datos, con campos punteros que apunten a ésta.
• Incluir a cada bloque de datos un puntero que
direccione a una lista enlazada de bloques de
overflow. Puede aumentar las búsquedas.
• Se considera el archivo real de datos como el archivo
maestro o principal, y se van almacenando en un
archivo de overflow no ordenado. Al actualizar el
maestro, se debe ordenar el archivo de overflow y
luego realizar la mezcla de los archivos.
17
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Eliminación: Se puede presentar de dos formas:
• Física: lo cual provoca grandes espacios libres en cada
bloque.
• Lógica: a través de marcas de borrado.
• En ambos casos, es necesario hacer una
reorganización de los registros.
18
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Ordenamiento Externo:
• Aplicable a archivos que por su tamaño no
pueden ordenarse en memoria principal.
• Consta de dos fases: una fase de ordenamiento
y una fase de mezcla.
19
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Fase de Ordenamiento:
• Se leen datos que son almacenados en
memoria principal, en un área de ordenamiento.
• Usando una rutina de ordenamiento interno
obtiene los registros ordenados, los que son
escritos en dos o más archivos (particiones) en
memoria secundaria.
• Los registros en las particiones quedan
ordenados en forma relativa a cada una de ellas
• Posteriormente se mezclan las particiones.
20
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Fase de Mezcla:
• Se combinan los archivos obtenidos en la fase
anterior, es decir, se mezclan las particiones
generadas en la fase de ordenamiento,
produciendo particiones más grandes hasta
llegar a una sola partición: el archivo ordenado.
21
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Fase de Mezcla:
22
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Algoritmos de Ordenamiento Interno:
• Ordenamiento Interno: consiste en leer M
registros de una vez desde el archivo
desordenado, luego se ordenan a través de un
algoritmo de ordenamiento interno y se generan
particiones de salida. Se asume que M es el
tamaño de la memoria principal disponible
(tamaño del buffer).
23
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Ejemplo: suponer que se tiene un archivo de
entrada desordenado con el siguiente contenido:
109
49
34
68
45
2
60
38
28
47
16
19
34
55
98
78
76
40
35
86
10
27
61
92
99
72
11
2
24
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Al considerar que se tiene un buffer con
capacidad para cinco registros, el resultado es:
34
45
49
68
109
2
28
38
47
60
16
19
34
55
98
35
40
76
78
86
10
27
61
92
99
2
11
72
25
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Algoritmos de Ordenamiento Interno: (cont.)
• Selección por Reemplazo: consiste en leer M
registros, e ir generando archivos de salida
aprovechando algún ordenamiento parcial que
pueda existir en el archivo de entrada. Se asume
que M es el tamaño de la memoria principal
disponible (tamaño del buffer).
26
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Suponer que se tiene un archivo de entrada
desordenado con el siguiente contenido:
109
49
34
68
45
2
60
38
28
47
16
19
34
55
98
78
76
40
35
86
10
27
61
92
99
72
11
2
27
Estructuras de Archivos
Archivos Secuenciales Ordenados
• El resultado de aplicar el algoritmo de selección por
reemplazo es:
34
2
10
2
45
16
27
11
49
19
35
60
28
40
68
34
61
109
38
72
47
92
55
99
76
78
86
98
28
Estructuras de Archivos
Archivos Secuenciales Ordenados
• De esta etapa es importante destacar:
• Al tener particiones grandes, se requerirán menos
mezclas; sin embargo, esto no es el único criterio a
considerar para seleccionar un algoritmo.
• Una ventaja del ordenamiento interno es que genera
particiones del mismo tamaño, excepto la última.
• La selección por reemplazo, en promedio, produce
particiones más grandes que el ordenamiento interno.
29
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Algoritmos para la Mezcla:
• Mezcla N-way balanceada: Las particiones son
agrupadas en tres conjuntos, lo más cercanos posibles
en cuanto al número de registros que contengan. Los
registros de los archivos de entrada son leídos y las
particiones mezcladas son distribuidas en los archivos
de salida. Esto se realiza en varias fases, alternando el
rol de los archivos entre éstas...
30
Estructuras de Archivos
Archivos Secuenciales Ordenados
Inicialmente
Archivo 1
Archivo 2
10 x 1
10 x 1
Después de Fase 1
Después de Fase 2
3x4
Después de Fase 5
1 x 16
Archivo 4
5x2
5x2
1 x 8, 1 x 4
1x8
2x4
Después de Fase 3
Después de Fase 4
Archivo 3
1x4
1 x 20
31
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Algoritmos para la Mezcla: (cont.)
• Mezcla Polifásica: variación no balanceada de la
mezcla N-way....
Archivo 1
Archivo 2
Archivo 3
Inicialmente
Después de Fase 1
13 x 1
6x1
11 x 1
4x1
7x1
Después de Fase 2
2x1
Después de Fase 3
Después de Fase 4
Después de Fase 5
1 x 17
Archivo 4
Lecturas
7x3
21
4x5
3x3
20
2x9
2x5
1x3
18
1x9
1x5
17
1 x 31
31
32
Estructuras de Archivos
Archivos Secuenciales Ordenados
• Algoritmos para la Mezcla: (cont.)
• Mezcla Óptima: Las particiones iniciales son escritas
en archivos separados, así se tiene un conjunto de F
archivos cada uno con una partición. Durante cada fase,
las F-1 particiones más pequeñas son leídas y
mezcladas, y la partición mezclada es escrita en un
archivo de salida. Los archivos de entrada son
removidos del conjunto y los archivos de salida son
agregados. El proceso se repite hasta que el conjunto
contiene un único archivo...
33
Estructuras de Archivos
Archivos Secuenciales Ordenados
Fase
Archivo de
Entrada 2
2:1
Archivo de
Entrada 3
3:1
Archivo de
Salida
21:3
Lecturas
1
Archivo de
Entrada 1
1:1
2
4:1
5:1
6:1
22:3
3
3
7:1
8:1
9:1
23:3
3
4
10:1
11:1
12:1
24:3
3
5
13:1
14:1
15:1
25:3
3
6
16:1
17:1
18:1
26:3
3
7
19:1
20:1
21:3
27:5
5
8
22:3
23:3
24:3
28:9
9
9
25:3
26:3
27:5
29:11
11
10
28:9
29:11
30:20
20
3
34
Estructuras de Archivos
Archivos Secuenciales Mixtos
• Es posible almacenar en un mismo archivo
registros de diferentes tipos (lo que da origen a un
archivo de largo variable).
• Para distinguir los registros de un archivo mixto,
cada registro tiene, además de los campos propios,
un campo llamado tipo_registro, el cual especifica
el tipo de registro.
35
Estructuras de Archivos
Archivos Directos
• Una segunda alternativa para estructurar archivos
se basa en la idea de poder alcanzar un registro en
forma directa, sin tener que accesar los registros
almacenados antes del requerido. Para tal fin,
existen los siguientes tipos de direccionamiento:
• Direccionamiento Directo: absoluto o relativo.
• Direccionamiento Indirecto (hashing).
36
Estructuras de Archivos
Archivos Directos
• Direccionamiento Directo:
• Absoluto: el programa entrega una dirección de
hardware (#cilindro, #pista, #sector) y el método de
acceso ubica el registro en dicha posición.
• Relativo: el programa entrega un número relativo a la
posición del primer registro en el archivo y el método de
acceso ubica el registro.
37
Estructuras de Archivos
Archivos Directos
• Ventajas: del direccionamiento absoluto.
• No existe transformación previa de la clave primaria.
• No existen problemas de colisiones.
• Fácil acceso secuencial, pues las claves pueden ser
asignadas en forma ordenada.
38
Estructuras de Archivos
Archivos Directos
• Desventajas: del direccionamiento absoluto.
• Es difícil que la clave primaria pueda ser una dirección
de hardware (suelen ser códigos inteligentes para el
usuario y no para la máquina).
• Cualquier cambio de hardware o falla de él, significaría
rehacer la asignación de claves.
• Claves deben definirse en base a características físicas
del dispositivo, y no a lo que le conviene al usuario.
39
Estructuras de Archivos
Archivos Directos
• Archivos Relativos: direccionamiento relativo.
• Conjunto de datos que se pueden accesar
directamente, conociendo la posición que tenga un
determinado registro, (posición relativa con respecto al
comienzo del archivo)
• Dicha posición se puede obtener:
• Directamente del valor de un campo del registro (número de
lista en un curso, lugar de llegada, etc.)
• Función sobre un determinado campo del mismo registro
(este esquema presenta el problema de las llamadas
colisiones).
40
Estructuras de Archivos
Archivos Directos
• Archivos Relativos: direccionamiento relativo.
• Antes de cualquier operación de ingreso de datos, es
preciso crear el archivo con tantos registros en blanco
como sean necesarios a futuro.
• Un registro en blanco se puede construir de dos formas:
• Escoger un campo (clave) el cual no puede tener valores
nulos en un registro activo.
• Agregar a cada registro un campo adicional, de tipo lógico,
cuyo valor determine si el registro está activo o no.
41
Estructuras de Archivos
Archivos Directos
• Archivos Relativos: direccionamiento relativo.
• Búsqueda: a través de la posición relativa. En el caso
de que se desee accesar todos los registros (activos)
del archivo, se debe hacer una búsqueda lineal, pero
tomando en cuenta para la salida aquellos registros que
no “estén en blanco”.
• Inserción: a través de la posición relativa.
• Eliminación: a través de la posición relativa. Consiste en
anular el valor del campo (clave) o del campo lógico,
dependiendo del caso, que determina si el registro es
nulo o no.
42
Estructuras de Archivos
Archivos Directos
• Direccionamiento Indirecto: algorítmico o hashing.
• La dirección a ser usada para ubicar el registro se
obtiene con una función de transformación al valor de la
clave primaria.
• El espacio de almacenamiento es dividido es secciones
llamadas buckets, que pueden almacenar uno o más
registros lógicos.
• Un bucket es un bloque del disco o un grupo de bloques
de disco. Está dividido en casilleros de tamaño fijo
denominados slots.
43
Estructuras de Archivos
Archivos Directos
• Direccionamiento Indirecto: algorítmico o hashing.
• En la actualidad, la mayoría de los SABD implementan
sólo este esquema, por lo que en el resto del curso sólo
se tratarán los archivos de tipo hashing.
• Dos tipos de archivos hashing:
• Estático: archivo de tamaño fijo.
• con Expansión Dinámica: archivo de tamaño variable.
44
Estructuras de Archivos
Archivos Directos
• Archivos de tipo Hashing Estático:
• La transformación anteriormente mencionada es una
función hashing que transforma la clave en un número
de bucket relativo.
• Una tabla es mantenida en el encabezado del archivo
para convertir el número de bucket en la dirección de
bloque de disco.
45
Estructuras de Archivos
Archivos Directos
• Archivos de tipo Hashing Estático: Ejemplo.
Nombre del Tema
Intérprete
#Estreno
Crazy in Love
Beyonce & Jay-Z
258
Frantic
Metallica
593
Go to Sleep
God puts a Smile upon your Face
RadioHead
Coldplay
Here we Kum
Hollywood
Just Because
Sálvame la vida
San Miguel
Molotov
Madonna
Jane’s Adiction
Lucybell
Los Prisioneros
287
125
880
1502
468
Show me How to Live
Re-Offender
White Flag
AudioSlave
Travis
Dido
450
1473
901
367
342
• Suponer archivo de 10 buckets h(#estreno) = #estreno
% 10
46
• Así, por ejemplo el
primer registro, de
clave
258
le
corresponde estar
guardado en el
bucket h(258) =
258 % 10 = 8.
• Al repetir lo anterior
con todos los
registros del archivo se obtiene el
siguiente resultado:
47
Estructuras de Archivos
Archivos Directos
• Archivos de tipo Hashing Estático.
• El uso de un archivo hashing permite recuperar los
registros en su base a su clave con un costo a un
bloque (o cercano). No obstante, el precio que se paga
considera dos posibles tipos de problemas:
• Manejo de Áreas Muertas: puede darse que el algoritmo no
genere todas las direcciones disponibles para almacenar los
datos, por lo cual se generan espacios libres que nunca son
direccionados.
• Sinónimos o Colisiones: al aplicar la función hashing puede
generarse una misma dirección a partir de claves diferentes.
Para solucionarlo conviene tener en cuenta las técnicas de
tratamiento de overflow.
48
Estructuras de Archivos
Archivos Directos
• Archivos de tipo Hashing Estático: Manejo de Colisiones.
• Una colisión ocurre cuando el valor del campo hashing
de un nuevo registro a insertar direcciona a una
posición en la cual ya existe un registro
• Esto obliga a que el nuevo registro se deba insertar en
otra posición, a través de una de las siguientes técnicas
de resolución de colisiones:
• Direccionamiento Abierto
• Encadenamiento
• Hashing Múltiple
49
Estructuras de Archivos
Archivos de tipo Árbol
• Técnicas de Manejo de Colisiones:
1. Direccionamiento Abierto: consiste en almacenar el
registro que está en colisión en la siguiente posición
disponible del área de datos.
• La búsqueda del registro se realiza en forma
secuencial a partir de la dirección generada por la
función hashing, hasta:
• Encontrar una entrada vacía.
• Encontrar el fin del archivo.
• Determinar que el archivo está lleno.
50
Estructuras de Archivos
Archivos de tipo Árbol
• Técnicas de Manejo de Colisiones:
1. Direccionamiento Abierto (cont.):
Ventajas:
• Menos espacio con respecto a tener un área de overflow
aparte.
• Dependiendo de la implementación, puede haber un menor
tiempo requerido para acceder al área de overflow, pues
como está incorporada a la misma área de datos, hay menos
cambios de cilindro.
• Uso más óptimo del área de datos, pues se minimizan las
áreas muertas (zonas sin registros).
Desventaja:
• Búsqueda lineal de los registros en colisión.
51
Estructuras de Archivos
Archivos de tipo Árbol
• Técnicas de Manejo de Colisiones:
2. Encadenamiento: varias localizaciones sólo de overflow
son mantenidas haciendo que un bucket de datos
pueda direccionar un bucket de overflow.
• Existen dos tipos de encadenamiento:
• Unificado: cuando el bucket de overflow es compartido
por varios buckets de datos.
• Enlazado: cuando el bucket de overflow es exclusivo de
un bucket de datos.
52
Estructuras de Archivos
Archivos de tipo Árbol
• Técnicas de Manejo de Colisiones:
2. Encadenamiento (cont.):
Ventaja:
• Se conoce con certeza los buckets donde hay que buscar un
registro.
Desventajas:
• Pueden generarse una secuencia de buckets en overflow, si
éste es constante.
• Pueden producirse “zonas muertas” en el mismo área de
overflow.
53
Estructuras de Archivos
Archivos de tipo Árbol
• Técnicas de Manejo de Colisiones:
3. Hashing Múltiple: Consiste en aplicar distintas funciones hashing a los registros que están en colisión hasta
encontrar una posición disponible donde almacenarlo.
• La secuencia en que se aplican las diferentes
funciones hashing debe ser respetada en la búsqueda
posterior de los registros.
54
Estructuras de Archivos
Archivos Directos
• Técnicas de Hashing con Expansión Dinámica.
• Las técnicas anteriores consideran un espacio de
direccionamiento de tamaño fijo...pero lo normal es que
los archivos vayan cambiando su tamaño
constantemente, lo que debe verse reflejado en la
técnica de hashing que se utiliza.
• Existen tres formas básicas para poder implementar
una expansión dinámica del tamaño del archivo,
mediante técnicas hashing:
• Dinámico
• Extendible
• Lineal
55
Estructuras de Archivos
Archivos Directos
• Hashing Dinámico.
• Considera, además del archivo de datos, una estructura
de acceso de tipo jerárquica.
• Similar a una técnica de indexación.
• El número de buckets no es fijo, sino que aumenta o
disminuye según sea requerido.
56
Estructuras de Archivos
Archivos Directos
• Ejemplo de
Archivo Dinámico.
57
Estructuras de Archivos
Archivos Directos
• Hashing Dinámico (cont.).
• El archivo puede empezar con un único bucket; una vez
lleno, si un nuevo registro es insertado, el bucket “entra
en overflow” y se divide en dos buckets.
• Los registros son divididos entre estos dos buckets,
según el valor del bit más izquierdo de sus valores
hashing.
• En este punto se crea una estructura de árbol binario,
llamada directorio o índice. Esta situación se repite
cuanto sea necesario.
58
Estructuras de Archivos
Archivos Directos
• Hashing Extendible.
• Considera, además del archivo de datos, una estructura
de acceso de tipo arreglo, que actúa de modo similar a
un índice.
• El directorio que se usa es un arreglo con 2d direcciones
de buckets (d es la “profundidad global del directorio).
• Cada entrada del directorio direcciona a un bucket, que
contiene una profundidad local d’ (# de bits sobre el cual
se basan los registros contenidos en el bucket).
59
Estructuras de Archivos
Archivos Directos
• Ejemplo de
Archivo Extendible.
60
Estructuras de Archivos
Archivos Directos
• Hashing Extendible (cont.).
• Los primeros d bits más significativos de un valor
hashing son usados como índice al directorio; la
dirección en cada entrada determina el bucket de
almacenamiento.
• No tiene que existir un bucket por cada entrada del
directorio.
61
Estructuras de Archivos
Archivos Directos
• Hashing Lineal.
• No considera una estructura tipo índice como las
anteriores.
• Su uso se basa en la existencia, inicialmente de M
buckets, numerados de 0 a M-1, los cuales van
recibiendo registros de acuerdo a una función hashing
h0.
• En el momento en que alguno de los buckets se llena,
se crea un bucket M en el cual se reparten los datos del
bucket 0, aplicando la función hashing h1.
• Este esquema se sigue repitiendo a medida que el
archivo crece de tamaño.
62
Estructuras de Archivos
Archivos de tipo Árbol
• Árboles: son archivos en las cuales los registros se
organizan en bloques relacionados de forma jerárquica
entre sí, de acuerdo a un cierto orden entre los valores que
contiene cada registro
• En cada uno de los casos se favorece las búsquedas
binarias, respecto de la clave sobre la cual se construyó el
archivo.
• Existen cuatro tipos de árboles posibles de usar en este
ámbito...
63
Estructuras de Archivos
Archivos de tipo Árbol
• Árboles
1. Binarios: tienen un factor de ramificación de 2, es decir,
cada nodo tiene a lo más dos descendientes
inmediatos (hijos).
• La altura mínima de un árbol con N registros es:
 log2 N + 1
• Desventaja: los tiempos de recuperación no son buenos y
requieren un gran esfuerzo para mantener un acceso
eficiente a los datos
64
Estructuras de Archivos
Archivos de tipo Árbol
• Árboles
2. Balanceados de Búsqueda Binaria (AVL): Árboles binarios con restricciones de crecimiento. Inventados como
una solución a los problemas de balanceo encontrados
en los árboles anteriores.
• Se ha establecido que la altura de un AVL con N registros
está entre:
 log2(N+1)  y  1.44.4 log2(N+2) - 0.328 
• Persisten los problemas de búsqueda debido a que aún se
tienen muchos niveles.
65
Estructuras de Archivos
Archivos de tipo Árbol
• Árboles
3. Árboles B: no existen problemas con estos árboles en
cuanto a la recuperación y mantención como los
árboles binarios, pues son árboles multiway con
operaciones de balanceo propias.
• Es el tipo de índice que tradicionalmente se ha
usado en ambientes de bases de datos relacionales.
66
Estructuras de Archivos
Archivos de tipo Árbol B
• Árbol B: se define un árbol B de orden M a aquel árbol que
cumple con las siguientes condiciones:
• Ningún nodo tiene más de M hijos.
• Cada nodo, excepto la raíz, tiene al menos M/2 hijos y a lo más
M hijos.
• La raíz, a no ser que el árbol sólo tenga un único nodo, tiene al
menos 2 hijos.
• Todos los nodos terminales se encuentran en el mismo nivel, es
decir están a la misma distancia respecto de la raíz.
• Un nodo no terminal con K hijos contiene k-1 registros. Un nodo
terminal contiene al menos M/2 - 1 registros y a lo más M-1
registros.
67
Estructuras de Archivos
Archivos de tipo Árbol B
• Árbol B: un nodo de orden M tiene la siguiente estructura:
Puntero1
Registro1
Puntero2
Registro2
…
Punterom-1 Registrom-1 Punterom
donde punteroi apunta a un bloque que contiene registros cuyos valores
son mayores que la clave de registroi-1 y menores que la clave de
registroi.
Así es posible realizar una búsqueda binaria sobre la estructura de
datos y alcanzar los datos.
68
Estructuras de Archivos
Archivos de tipo Árbol B
• Ejemplo de Árbol B,
de orden 4.
m
c
a b
d e
f
i
g h
q
j k l
n o p
t
r s
u v w
69
Estructuras de Archivos
Archivos de tipo Árbol B
• Operaciones: sobre un árbol B.
• Búsqueda: se comienza examinando la raíz para buscar nodo
con el registro requerido.
• Si no es encontrado, comparaciones con claves identificarán
el puntero a seguir hacia el nivel inferior.
• Si es nulo => nivel inferior => registro buscado no está en el
archivo.
• Si no es nulo, accesar el nodo apuntado, el cual pasa a ser la
raíz.
70
Estructuras de Archivos
Archivos de tipo Árbol B
• Operaciones: sobre un árbol B.
• Inserción: los nuevos registros son insertados en un nodo
terminal (hoja).
• Para determinar el punto de inserción, se realiza la misma
operación de búsqueda anterior.
• Si la posición determinada se encuentra dentro de un nodo
totalmente ocupado, ocurre un overflow, lo cual se resuelve
haciendo una división del nodo en tres partes, llevando el
registro del medio hacia el nivel superior para insertarlo en el
nodo padre, dejando a este último con un hijo más.
71
Estructuras de Archivos
Archivos de tipo Árbol B
• Operaciones: sobre un árbol B.
• Eliminación: también se debe realizar desde el nivel de más
abajo hacia arriba.
• Problema: Borrar un registro de un nodo que tiene la cantidad
mínima de registros permitidos (underflow). Soluciones:
• Redistribución - el nodo adyacente al de underflow tiene una cantidad de registros
mayor al mínimo: mover registros entre el nodo adyacente y el padre de tal forma
de no alterar la estructura del árbol.
• Concatenación - no es posible la redistribución: mezcla de nodos, proceso inverso
de la división de un nodo. Cambia la estructura del árbol, incluso puede removerse
la raíz y reducir en un nivel el árbol.
72
Estructuras de Archivos
Archivos de tipo Árbol B
• Variaciones del Árbol B:
•
Árbol B Virtual:
• Para alcanzar un nodo, se debe pasar siempre por la raíz
(con el consiguiente acceso al disco)
• Hay implementaciones en las que el sistema almacena el
nodo raíz en la RAM permanentemente.
• Si hay memoria suficiente, se puede almacenar los nodos del
segundo nivel y más
• Ventajas: se reducen los accesos al disco y por ende, los
tiempos de respuesta.
73
Estructuras de Archivos
Archivos de tipo Árbol B
• Variaciones del Árbol B:
•
Árbol B*:
• Un árbol B tiene la restricción de que tiene estar a lo menos
un 50% lleno, lo que puede ocasionar que la mayoría de los
nodos estén un 50% llenos y un 50% vacíos, desperdiciando
en este caso casi la mitad del espacio de los bloques físicos
ocupados.
• Como una forma de reducir esto, se plantea el árbol B*, el
que impone la restricción de que al menos un 66.6% del nodo
debe estar lleno.
74