TEMA 1

INTRODUCCION A LOS SISTEMAS DE ARCHIVOS...

...o como no matar moscas a cañonazos,

ni tirar paredes con matamoscas :-)

OBJETIVOS DE ESTE CAPITULO:

INDICE TEMA 1.

1.1 Conceptos básicos

Almacenamiento Primario

Almacenamiento Secundario

Algunas definiciones

Entidad

Atributo

Clave Primaria & Secundaria

Registro & Campo. Tipos

Fichero Lógico y Físico

1.2 Tipos de acceso

Secuencial & Directo

Acceso Secuencial Indexado

1.3 Componentes físicos

Disco

Plato

Pista, Cilindro & Sector

1.4 Tipos de organización

Por sectores

Interleave

Fragmentación

Por bloques

1.5. Accesos a disco

Tiempo de desplazamiento

Tiempo de rotación

Tiempo de transferencia

Trasferencia de información

1.6. Operaciones sobre ficheros

Genéricas & Particulares

1. CONCEPTOS BASICOS

ALMACENAMIENTO PRIMARIO & ALMACENAMIENTO SECUNDARIO

n Primario è Es limitado

è Es caro

è No puede compartirse una vez en uso

è Volatil

ALMACENAMIENTO PRIMARIO & ALMACENAMIENTO SECUNDARIO

n Secundario è Mayor tamaño

è Menor precio

è No requiere flujo continuo de energía

ALGUNAS DEFINICIONES

u ENTIDAD

u ATRIBUTO

• REGISTRO

3 de longitud predecible

3 con Indicador de longitud

3 utilización de Fichero índice

3 Utilización de Delimitador

�

• CAMPO

3 de longitud fija

3 de longitud variable

ARCHIVOS

u Puntos de vista:

• FíSICO

• LóGICO

u Conceptos relacionados:

• Clave

3 Primaria

3 Secundaria

u Consideraciones de diseño

• Obtener la información requerida en el primer acceso.

o bien

• Obtener alguna información inicial que reduzca la cantidad de accesos en caso contrario

• Obtener toda la información necesaria de una sola vez.

u Estructura de Archivos �Estructura de Datos

2. TIPOS DE ACCESO

u Por claves Primarias. Tipo de acceso:

• Secuencial

• Aleatorio

3 Directo por posición

3 Directo por clave (Hash)

3   Indexado: secuencial indexado, búsquedas binarias, árboles AVL, árboles B, árboles B+

u Por claves Secundarias

3. COMPONENTES FISICOS

u En acceso Secuencial. (p.ej., unidades de cinta)

• Densidad, velocidad, tamaño del GAP

u En acceso Directo (p.ej., unidades de disco)

• Plato

• Cabeza

• Pista, Sector, espacio

• Cilindro

• Desplazamiento del brazo

• Capacidad

3 del disco

3 del cilindro

3 de la pista

4. TIPOS DE ORGANIZACION

u Por Sectores

• Física o lógicamente adyacentes

• Factor de Intercalación (o �interleave')

• Cúmulos

3FAT

u Por Bloques

• Factor de bloque

• Sobrecarga de control

5. ACCESOS A DISCO

• Tiempo de desplazamiento

• Tiempo de rotación

• Tiempo de trasferencia

6. OPERACIONES SOBRE FICHEROS

u Genéricas

• Apertura

• Cierre

• Lectura

• Escritura

u Particulares

• Asignación

• Posicionamiento

• Posición

• Tamaño

TEMA 2

INDEXACIóN

�Una piedra angular de la teoría de estructura de datos es la

distinción entre estructuras fundamentales y "avanzadas".'

Niklaus Wirth,

�Algoritmos + Estructuras de Datos = Programas'

OBJETIVOS DE ESTE CAPíTULO:

íNDICE TEMA 2.

2.1 Justificación

2.2 Criterios de equilibrio

Árbol perfectamente equilibrado

Árbol AVL

2.3 Árboles B

Concepto

Inserción

Borrado

Cuentas

2.4 Otras organizaciones de árboles B

B*

B+

2.5. índice

2.6. Acceso secuencial Indexado

1. INDEXACIóN.- Justificación

n Formas de trabajo sobre Memoria Principal:

è Tablas

è Listas enlazadas

è Árboles binarios de búsqueda

n Formas de trabajo sobre Memoria Secundaria:

è Ficheros secuenciales

è Ficheros de acceso directo

n   Objetivo: Acceso directo por clave que reduzca el n� de accesos a realizar.

Algunas definiciones

Árbol de Búsqueda:

Las claves del subárbol izquierdo de un nodo son menores, y las del subárbol derecho, mayores, que la del nodo que se trata.

Árbol Ordenado:

� Aquel en que las ramas de cada nodo están ordenadas

Grado:

Número de descendientes directos de un nodo interior

Grado de un Árbol:

Máximo de los grados de todos los nodos del árbol

Árbol Binario:

Árboles ordenados de Grado 2.

2. CRITERIOS DE EQUILIBRIO

n Árbol perfectamente equilibrado

�Para cada nodo, �el número de nodos' del subárbol izquierdo y del derecho difieren como mucho en una unidad'

è Las claves pueden estar ordenadas o no

è Criterio algo �rígido'

n Generación de un árbol perfectamente equilibrado:

- Hay que conocer el número de claves del árbol

- El procedimiento ha de ser recursivo

- No es necesario que el árbol esté ordenado

- Si �N' es el número de claves del árbol, se generan dos subárboles, con:

Ni = N div 2 nodos

Nd = N - Ni - 1 nodos

- Altura máxima del árbol <= log (n) + 1

[JAL1] 

n Árbol equilibrado

è �Para cada nodo, �la longitud' del subárbol izquierdo y del derecho difieren como mucho en una unidad'

è Si además el árbol es binario de búsqueda à Árboles AVL (Adelson-Velskii y Landis, 1962)

è Altura mínima del árbol: log ( N + 1 )

n Inserción en árbol equilibrado AVL

è Situación de desequilibrio. Factor de equilibrio.

è Rotaciones: secuencia de rotaciones de punteros que se intercambian cíclicamente:

à Simple derecha, DD

à Simple izquierda, II

à Doble derecha, ID^(*)

à Doble izquierda, DI^(*)

è Estado de equilibrio de cada nodo:

TYPE

tarbol = ^tnodo

tnodo = RECORD

clave: tclave;

izquierdo, derecho: tarbol;

equilibrio: -1..1;

END;

è Proceso de Inserción :

1.  Seguir el camino de búsqueda hasta ver que la clave no esta en el árbol.

2.  Insertar el nuevo nodo, y obtener los nuevos valores de equilibrio.

3.  Volver por el camino de búsqueda comprobando el factor de equilibrio de cada nodo

è Parámetros que se necesitan :

1.  Árbol donde realizar la inserción

2.  Clave que se quiere insertar

3.  Información de la altura del subárbol (tipo de parámetro ?)

è Casos posibles en la realización:

hi < hd � a�.equilibrio = +1

hi = hd � a�.equilibrio = 0

hi > hd � a�.equilibrio = -1

n Borrado en árbol equilibrado AVL

è Proceso de Borrado:

1.  Búsqueda de la clave.

2.  Estudio del equilibrio del árbol.

è Parámetros que se necesitan:

1.  Árbol donde realizar la inserción

2.  Clave que se quiere borrar.

3.  Información de la altura del subárbol.

è Casos posibles en la implementación:

1.  Borrado de una hoja sin desequilibrio

2.  Borrado de una hoja con desequilibrio

3.  Borrado de un nodo interno sin desequilibrio

4.  Borrado de un nodo interno con desequilibrio

è Caso 2: DD, II, DI, ID,

è Caso 2: DD, II, DI, ID,

è Caso 2: DD, II, DI, ID,

3. ÁRBOLES B

"Al buscar una forma de controlar el crecimiento, el árbol perfectamente equilibrado se deshecha inmediatamente debido al gran esfuerzo que requiere la operación de reequilibrado."

N. Wirth.[1]

▀ Árboles MULTICAMINO: Cada nodo puede tener más de dos ramas.

è Realización:

à Array de registros

à Lista lineal

è Utilización:

à    Construcción y mantenimiento de árboles de búsqueda a gran escala.

�

è División del árbol en subárboles

à Páginas

▀ Árboles B

è El orden del árbol es n

è Todas las páginas, excepto la raíz, tienen entre n y 2n claves

è Cada página es una página-hoja (no tiene descendientes), o tiene m+1 descendientes; m � número de claves de la página

è Todas las páginas-hoja se encuentran al mismo nivel

Supóngase la página del árbol:

�

� � � � �

¿Qué casos pueden presentarse si una clave �x' no se encuentra en esta página?

▀ Inserción de un elemento en un árbol B

è Si la página donde se inserta tiene m > 2n nodos?

è Si " " " tiene m = 2n nodos?

è Declaración de la estructura de una página:

type pagina = record

m: indice;

p0: ref;

e: array [1 .. nn] of item

end;

const nn = 2 * n;

type ref = �pagina;

indice = 0 .. nn;

item = record

clave: integer;

p: ref;

contador: integer

�end;

è Conveniencia de una formulación recursiva?

▀ Algoritmo de Búsqueda e Inserción en un árbol B

Buscar ( x: integer; (* Nodo a insertar/buscar *)

a: tArbol; (* Árbol B *)

var cambio: boolean; (* El árbol ha crecido *)

var u: tItem;) (* Elemento que sube de nivel *)

if a = nil

- copiar �x' en �u'

- cambio := true

else

- buscar x en el array

- si está � operaciones a realizar con la clave

- si no está �

llamada recursiva (x, página siguiente, cambio, u)

if cambio (* se sube un elemento *)

- si m < 2n

- se inserta en esa página

- m := m + 1

- cambio := false

- si m = 2n

�

- divide página

- copiar en u el elemento en el medio

end

▀ Borrado de un elemento en un árbol B

è Casos:

- la clave a borrar está en una hoja

- la clave a borrar no está en una hoja

�

Se sustituye por elementos adyacentes

▀ Número de claves de la página en un árbol B

1.- La información se almacena dentro de la página asociada a las claves

- Estructura para las claves:........................................ 2n _* tamaño clave

- Estructura para la información:.................................. 2n _* tamaño info

- Estructura para los descendientes:...... (2n + 1) _* tamaño descendientes

è Tamaño de la página �

1 + (2n _* Tclave) + (2n _* Tinfo) + (2n + 1) _�* Tdescen =

= (1 + Tdescen) + 2n _* (Tclave + Tinfo + Tdescen)

Tpagina - (1 + Tdescen)

è n � �����������

Tclave + Tinfo * Tdescen

2.- La información se almacena en un TAD independiente (p.ej. un fichero).

- Estructura para las claves:.......................................... 2n _* tamaño clave

- Estructura para las posiciones:.............................. 2n _* tamaño posición

- Estructura para los descendientes: ...... (2n + 1) _* tamaño descendientes

è Tamaño de la página �

1 + (2n _* Tclave) + (2n _* Tposición) + (2n + 1) _�* Tdescen =

= (1 + Tdescen) + 2n _* (Tclave + Tposición + Tdescen)

Tpagina - (1 + Tdescen)

è n � ������������

Tclave + Tposición * Tdescen

▀ Altura de la página de un árbol B

è En el peor caso:

- La raíz sólo tiene una clave

- Todas las demás páginas tienen n claves

Nivel 1 � 1 sola clave[JAL2]  � 2 descendientes

Nivel 2 � 2 pág. con n claves[JAL3]  � 2 _* (n + 1) descen.

Nivel 3 � 2 _* (n + 1) pág. con n claves[JAL4]  � 2 _* (n + 1)² descen.

Nivel 4 � 2 _* (n + 1)² pág. con n claves[JAL5]  � 2 _* (n + 1)³ descen.

.

.

.

Nivel d � 2 _* (n + 1)^d-2 pág. con n claves[JAL6]  � 2 _* (n + 1)^d-1 descen.

è Un razonamiento iterativo:

- Una página tiene �n' claves è �n + 1' descendientes

- La raíz sólo tiene 1 clave

- Un árbol con �x' claves tiene �x + 1' descendientes en el nivel de las hojas

è La altura será aquella que cumpla:

x + 1 � N� de descendientes al nivel de las hojas = 2 * (n + 1) ^{d - 1}

de donde:

d � 1 + log _n*1 ((x + 1)/2)

▀ Árboles B*:

è Concepto de �Redistribución'

è Árboles B*:

Árbol B especial, en el que cada nodo está lleno por lo menos en dos terceras partes (66%). Proporcionan mejor utilización del almacenamiento que los árboles B⁽⁶⁾. La situación se genera cuando se produce una inserción al dividir, de dos páginas a tres en lugar de una a dos.

� Cada página tiene un máximo de m descendientes.

� Todas las páginas, excepto la raíz y las hojas, tiene al menos (2m - 1) / 3) descendientes.

� La raíz tiene al menos dos descendientes, al menos que sea �hoja'.

� Todas las páginas-hoja se encuentran al mismo nivel.

� Una página que no sea hoja, con k descendientes, contiene k - 1 claves.

� Una página-hoja contiene al menos [(2m - 1) / 3] claves, y no más de (m - 1)

▀ Árboles B+: El índice del árbol se almacena en un árbol B separado, que permite encontrar la información, que se encuentra en los registros de un fichero secuencial indexado.

5. INDEXACIóN

n índice è Establece un �Orden' en un fichero

è Puede ser múltiple

è Primera aproximación : tabla de registros

n Operaciones básicas de un fichero Indexado :

è Creación

è Lectura de índice

è Actualización de índice

è Inserción de registros

è Eliminación de registros

è Modificación de registros

TEMA 3

TRANSFORMACIóN DE CLAVES (HASHING)

...o como encontrar, con el mínimo esfuerzo, una clave dada dentro de un conjunto de elementos.

OBJETIVOS DE ESTE CAPITULO:

�

INDICE TEMA 3.

3.1 Transformación de Claves

3.1.1 Hash

3.2 Manejo de Colisiones

3.2.1 Externo

3.2.1.1. Encadenamiento Directo

3.2.1.2. Overflow

3.2.2. Interno

3.2.2.1 Encadenamiento Directo

3.2.2.2 Encadenamiento Vacío

3.2.2.2.1 Inspección Lineal

3.2.2.2.2 Inspección Cuadrática

3.3. Elección de la función de transformación

3.2.1 Método del centro de los cuadrados

3.2.2 Método de la división

3.2.3 Método de desplazamiento

3.2.4 Método de plegamiento

3.4. Factor de carga y efectividad

3.5. Buckets (compartimentos)

1. TRANSFORMACIóN DE CLAVES

Sea un conjunto C:

Dada una clave C₁ de este conjunto, un procedimiento para encontrarla -en el primer intento, si es posible- se basa en lo siguiente:

l Cada elemento del conjunto de claves va a representarse mediante una dirección en memoria

El procedimiento será entonces una aplicación :

H : C � D

Función de Conjunto Conjunto de

Transformación de claves direcciones

El procedimiento puede verse entonces como una tabla:

l y de aquí el nombre de Transformación de Claves.

n HASH:

H : C � D

Se emplea, generalmente, cuando el número de claves es muy grande comparado con el número real de registros que van a manejarse en el fichero.

l El método no es determinista!

Dados C₁, C₂ � C � C₁ �C₂ ;

si H(C₁ ) = H(C₂ ) � Colisión!

2. MANEJO DE COLISIONES

n   Colisión: El lugar en la tabla correspondiente a una cierta clave no contiene el elemento deseado; dos claves corresponden al mismo índice.

l El tratamiento de la colisión puede hacerse usando:

� Almacenamiento externo: el espacio reservado para las colisiones está fuera de los límites de la tabla.

� Almacenamiento interno: utiliza un método de reasignación para calcular un nuevo índice dentro de la tabla.

n   Tratamiento de colisiones externo

1. Encadenamiento directo

Se encadenan todos los elementos cuyas claves generan el mismo índice primario por medio de una lista externa a la tabla; un elemento adicional en cada elemento guarda el puntero a su lista de colisiones.

2. Overflow

Se reserva una parte de la tabla, llamada área de desbordamiento -aproximadamente un 10%- para almacenar aquellos elementos en colisión. En el área de desbordamiento la búsqueda se realiza de forma secuencial.

3. Encadenamiento directo externo en zona de Overflow

En el caso de producirse nuevas colisiones en el área de overflow, ésta se expande dinámicamente:

n   Tratamiento de colisiones interno

1. Encadenamiento directo

Los elementos cuyas claves generan el mismo índice se enlazan a nuevas posiciones, ocupadas por estos elementos, dentro de la misma tabla. Hay que preveer espacio adicional en cada elemento de la tabla para guardar la dirección del siguiente elemento.

2. Encadenamiento vacío

Se buscan otros lugares vacios dentro de la tabla.

Se evitan enlaces, pero hay que realizar una búsqueda secuencial en la tabla.

Asimismo, se produce un agrupamiento de claves secundarias detrás de las primarias.

2.1. Inspección lineal

Busca el siguiente lugar hasta encontrar el elemento buscado o una posición vacía.

Los índices se generan de la siguiente forma:

H ( c ) = d₀

a continuación

h₀ = c � d₀ � d₁ � d₂ � . . .

donde

�

N � tamaño de la tabla

h_i = ( h_{i - 1} + 1 ) MOD N

o bien h_i = ( h₀ + i ) MOD N

Termina cuando, para un d_i , se produce una de estas situaciones:

T[ d_i ] = c -- se encuentra el elemento

T[ d_i ] = vacío -- se encuentra una posición vacía

d_i = d₀ -- la tabla está llena

2.2 Inspección cuadrática

La generación de índices se efectúa:

h₀ = c

h_i = d₀ + colisiones² ( i > 0 )

�

3. ELECCIóN DE LA FUNCIóN DE TRANSFORMACIóN

l Consideraciones a tener en cuenta:

1- La función ha de distribuir las claves de manera uniforme sobre el conjunto de direcciones posibles.

2- La función ha de ser rápida.

l Adicionalmente,

3- Ha de producir pocas colisiones.

4- Ha de ser fácil de calcular

5- Ha de eliminar la información no distintiva de la clave original

l Tamaño de la tabla: un 10% mayor del tamaño necesario

Supongamos una tabla de 7.000 elementos.

-Solo para claves numéricas:

1. Método del centro de los cuadrados

Se multiplica la clave por sí misma, y se toman los dígitos centrales, ajustándolo al rango.

Ej:

clave � 172148

cuadrado � 029634933904

��

dígitos centrales é

ajuste al rango � 3493 * 0,7 = 2445 Dirección

2. Método de la división

Se divide la clave por, bien un número primo ligeramente inferior al tamaño de la tabla o bien por un n� que contenga factores primos menores que 20. La dirección resultante es el resto de la división.

Ej:

clave � 172148

172148 MOD 6997 = 4220

ajuste de rango � 4220 * 0,7 = 2954 Dirección

3. Método de desplazamiento

Los dígitos exteriores se desplazan sobre los centrales, y se suman con éstos.

Ej.

clave � 542422241

��

é

longitud de la dirección

2422

542

54

��

2717

ajuste de rango � 2717 * 0,7 = 1894 Dirección

4. Método de plegamiento

Se eligen varias columnas arbitrariamente, y de forma análoga al caso anterior, se pliega el resto sobre ellas, para hacer después una suma o un OR-exclusivo.

Ej:

clave � 542422241

��

2422

142

45

��

7064

ajuste de rango 7064 * 0,7 = 4944 Dirección

4. FACTOR DE CARGA

n   Factor de carga, a: cociente entre el número de claves que hay en la tabla dividido por el número total de claves. Es una medida del rendimiento de la tabla hash, -número de colisiones que se producen-.

3 Para una tabla vacía:

a = 0

3 Para una tabla vacía:

n

a = ���

n + 1

3 Es directamente proporcional al n� de colisiones.

5. BUCKETS (Compartimentos)

n   �Bloque de registros que se extraen en un acceso a disco cuando comparten la misma dirección'

�

l Empleado en trabajo sobre archivos en disco; menos importante cuando se trabaja sobre memoria

l Un compartimento está formado por uno o más sectores del disco

n   Modo de trabajo:

3 Con la función de Trasformación se obtiene la dirección del compartimento �base', y a partir de ahí, se continua la búsqueda mediante las técnicas conocidas.

n   Ventajas:

3 Minimiza el número de colisiones (nueva colisión � cuando el bucket esté completo.

3 Minimiza el tiempo de acceso a las claves y el espacio utilizado en el almacenamiento.

3El tamaño de la tabla Hash es menor.

TEMA 4

ORDENACIóN EXTERNA

...o como perder menos tiempo, y hacer menor número de accesos a la memoria.

�

INDICE TEMA 4.

4.1 Justificación

4.2 Ordenación por mezcla

4.3. Ordenación externa

4.3.1. Mezcla directa

4.3.2. Mezcla natural

4.4. Intercalación múltiple

1. JUSTIFICACIóN

l Volumen de datos amplio

l Tamaño de memoria limitado

l Objetivo: minimizar el número de accesos a los ficheros

2. ORDENACIóN POR MEZCLA.

l   N ficheros �ordenados' de unen para formar un único archivo ordenado:

A	B	Operación C
Vacio	Vacio	nada
Vacio	No vacio	copiar todos los registros de B en C
No vacio	Vacio	copiar todos los registros de A en C
No vacio	No vacio	bucle a repetir hasta que A o B estén vacios (*)

(*) Operaciones a realizar en este caso:

Leer ( A, ElemA )

Leer ( B, ElemB )

Bucle hasta llegar al final de A o B

Comparar ( ElemA, ElemB )

if ElemA > ElemB

then Escribir ElemB en C

Leer B

else Escribir ElemA en C

Leer A

Introducir el resto de A o B en C

3. ORDENACIóN EXTERNA.

n   MEZCLA DIRECTA

Se ordenan las secuencias de un archivo en grupos de tamaño creciente = 2ⁿ (1, 2, 4, 8, ...):

Sea la secuencia:

22 6 25 48 32 5 12 20 31 35

l Para grupos de tamaño = 1, tenemos:

22 25 32 12 31

�6 48 5 20 35

l Ordenando estas secuencias:

6 , 22 25 , 48 5 , 32 12 , 20 31 , 35

l Agrupando en grupos de tamaño = 2:

6 , 22 5 , 32 31 , 35

25 , 48 12 , 20

l Ordenando estos grupos:

6 , 22 , 25 , 48 5 , 12 , 30 , 32 , 31 , 35

l Agrupando en grupos de tamaño = 4:

6 , 22 , 25 , 48 31 , 35

5 , 12 , 20 , 32

l Ordenando:

5 , 6 , 12 , 20 , 22 , 25 , 32 , 48 31, 35

l La ultima agrupación ( tamaño = 8 ):

5 , 6 , 12 , 20 , 22 , 25 , 32 , 48

31 , 35

l Ordenando:

5 , 6 , 12 , 20 , 22 , 25 , 31 , 32 , 35 , 48

l El procedimiento a seguir es el siguiente:

1- Dividir la secuencia a ordenar en 2 subsecuencias de menor tamaño, cada una la mitad de la secuencia original.

2- Mezclar las dos secuencias de forma ordenada, para generar otra mayor, formada por cinjuntos ordenados de valores con 2⁰, 2¹, 2², ... elementos.

3- Iterar los pasos 1 y 2 hasta que el tamaño del conjunto ordenado (2ⁿ) sea mayor que el número de elemtentos a ordenar.

n   MEZCLA NATURAL

Las secuencias intermedias no tienen tamaño prefijado ni longitud constante. Estas se generan con sus elementos ordenados, separando un elemento nuevo a otra secuencia si no se respeta esta condición.

Se incluyen separadores de secuencia.

l Sea la cadena de numeros:

F1:

3 15 7 17 9 8 14 2 41 24 36 1 13 42 26 35 5 33

Aplicando el método de mezcla natural con tres ficheros, uno original y dos auxiliares (frecuententemente llamados �cintas'), el resultado es:

F2:

3 15 9 2 41 1 13 42 5 33

7 17 8 14 24 36 36 35

�

---

---