IBD
Plan 2003
Clase 4
Archivos - Búsqueda

Búsqueda de información (costo)

# de comparaciones (operaciones en
memoria)
• Se pueden mejorar con algoritmos más eficientes.


Buscar un registro



2
# de accesos (operaciones en disco)
+ rápido si conocemos el NRR (directo)
Secuencia debe buscarse desde el principio
Trataremos de incorporar el uso de claves o
llaves.
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Búsqueda

Búsqueda binaria

Supongamos
• Archivo ordenado por clave
• Registros de longitud fija



3
Búsqueda, partir el archivo a la mitad y
comparar la clave, puedo acceder al medio
por tener long. Fija
Si N es el # de registros, la performance
será del orden de Log2 N (teniendo en
cuenta los accesos)
Se mejora la performance de la búsqueda
secuencial.
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Búsqueda

Algoritmo de búsqueda secuencia

tener en cuenta que es un pseudocódigo NO estructurado
Function Busqueda_Bin ( entrada, llave, #reg)
menor := 1
mayor := #reg
mientras ( menor <= mayor )
intento :=[(mayor+menor )/2]
leo un reg con NRR = intento
armo llave canónica del reg. leído en llave_c
If llave < llave_c
entonces mayor:=intento+1
sino if llave > llave_c
entonces menor:=intento+1
sino devuelve (registro)
fin mientras
devuelve ( ‘no esta’ )
4
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación


La búsqueda binaria acota el espacio para
encontrar información tiene un costo
mantener ordenado el archivo
Primera solución


Llevar el archivo a RAM (vector) y ordenar
Por que RAM y no disco directamente
• El número de corrimientos implica accesos a
disco, muy costoso.
• Primer paso, llevar las llaves a forma canónica
• Algoritmos de ordenación se pueden encontrar en
bibliografía, aparece una variante interesante.
5
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Algunas conclusiones


Búsqueda binaria mejora la secuencial
Problemas
• # accesos baja pero no llega a uno
• Acceder por el NRR requiere una lectura
• Costo de mantener el orden
• Análisis costo beneficio entre costo del orden o costo de
la búsqueda
• Clasificación en RAM solo para archivos pequeños

Mejorar el método de ordenación
• No reordenando TODO el archivo
• Reorganizando con métodos más eficientes (árboles)
6
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Segunda posibilidad de clasificación

No llevar todo el archivo a RAM solo
llevar la llave o clave
• Esto permite clasificar archivos más
grandes
• Algoritmos en la bibliografía

7
Se obtienen mejoras o es la solución
esperada??
IBD - CLASE 4
UNLP - Facultad de Informática
Archivo - Clasificación

Tercera solución
El archivo de datos no cabe en RAM
 Las claves del archivo tampoco caben
en RAM
 La clasificación debe hacerse de otra
forma

• Partir el archivo
• Ordenar cada parte
• Juntar las partes ordenadas
8
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos – Clasificación

Primer paso: establecer las
particiones
• Ventajas
• Permite clasificar archivos grandes (aumenta
el número de particiones)
• Lectura de cada partición es siempre
secuencial
• Lectura de cada partición en orden, escritura
en un nuevo archivo (ambas secuenciales)
• Como determinar el tamaño
• Lo que quepa en memoria RAM
9
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos – Clasificación
R e g is tro s d e s o rd e n a d o s
P a r t ir
O rd e n a r
J u n ta r
R e g is tro s o rd e n a d o s

Ejemplo del método
• Formamos 40 particiones, 1/40 parte del archivo
original.
• Ordena cada parte
• Juntamos las partes
• Estudio numérico
10
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos – Clasificación

Como mejorar la performance
• Achicar el número de particiones
• Intercalar de otra forma (por ej. en más
de un paso, o por otro método de merge)

Particiones
• El tamaño está dado por lo que cabe en
RAM
• Tres posibilidades
• Sort interno
• Selección por reemplazo
• Selección natural
11
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación
•
•
Sort interno: mecanismo ya visto, M registros
que caben en RAM y se genera un archivo de
salida ordenado.
Selección por reemplazo:
•
1.
2.
3.
4.
5.
6.
12
Aumenta el tamaño de las particiones en
promedio al doble
Leer M registros desordenados
Obtener clave menor
Pasar la clave menor al archivo de salida
Reemplazar por otro, si tiene clave menor a la
pasada al arch. de salida dormirlo.
Repetir dos hasta que todos los registros en la
entrada estén dormidos.
Comenzar con una nueva partición despertando
todos los dormidos, desde el paso 2 y hasta
terminar el archivo original
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Algoritmo
N
{# de registros}
buffer
{reg. entrada}
escrito
{reg. ya escritos}
dormido
{reg. dormidos}
ult_llave
{ult.clave pasada}
for i:=1 to M
escrito[i] := true
i := 0
repetir
i:=i + 1
leer buffer[i] de entrada
escrito[i] := falso
hasta (eof(entrada)) o (i = M)
13
mientras not( eof( entrada ) )
for i := 1 to M
if not escrito[i]
then dormido[i]:= false
mientras (haya reg.despiertos)
encontrar clave menor de
buffer y que este despierto
ult_llave:=llave buffer[s]
escrito[s]:= true
dormido[s]:= true
if not eof(entrada)
then leer buffer[s] de entr.
escrito[s]:= false
if ult_llave < buffer[s]
then dormido[s]:=true
end
end
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación
• Algunos datos de selección por reemplazo
• Aumenta el tamaño de cada partición
• Los registros se deben leer de a uno esto es
imposible, se utilizan buffers que ocupan parte
de la RAM
• Selección natural
• Aprovecha el espacio de memoria, necesitamos
algún buffer más pero ahorra memoria
• Los dormidos se pasan a un buffer secundario, y
permiten que entren nuevos elementos del archivo
de entrada, cuando el buffer secundario se llena se
termina de dormir elementos.
• Particiones quedan con más elementos.
14
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación
if not eof(entrada)
then listo:=falso
 Algoritmo
repetir
M,M’
{# reg. y reserva exter.}
if llave reg siguiente >= ult_llave
buffer, escrito, dormido
then escrito[s]:=false
reserva {#reg. actual en reserva}
listo:= true
sin_espacio {flag de reserva}
buffer[s]:=new
elem.
ult_llave
{idem}
else
if
reserva
<
M’
{seteo estado inicial}
then nueva entrada pasa al
for i:= 1 to M
reservorio
escrito[i]:= true
reserva:=reserva+1
i := 0
else sin_espacio := true
Repetir
hasta listo or sin_espacio
i:=i + 1
hasta eof(entrada) or sin_espacio
leer buffer[i] de entrada
sacar los elementos no escritos de buffer
escrito[i]:= falso
en orden, poner escrito en true
hasta eof(entrada) or i = M
{preparar
buffer para la nueva partición}
repetir
if
reserva
> 0
reserva := 0
then
mover
a buffer reg. del reservorio
sin_espacio := falso
y
actualizar
escrito y reserva.
repetir
obtener clave menor y escribirla en if buffer no lleno y not eof(entrada)
then completar buffer
buffer[s]
hasta
escrito
este todo en true
ult_llave := buffer[s]
escrito[s]:= true
15
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Conclusiones

Ventajas
• Interno: particiones del mismo tamaño
• Natural: tiende a producir particiones mayores
• Interno y selección: costo de acceso menor

Desventajas
• Natural: mayor costo en acceso (generar el
archivo intermedio)
• Selección: tiende a generar muchos registros
dormidos.
16
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Intercalación en más de un paso
Solución: agregar pasos intermedios
con archivos temporales para mejorar
la eficiencia
 Ejemplo
 Conclusiones

• Intercalando más de 5 porciones hacer
dos pasos
• El método mejora si se disponen de
varios discos o con varias cabezas
lectoras grabadoras.
17
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Otros métodos de intercalación
• Balanceado de n caminos
• Óptimo
• Multifase

Que estudiaremos
• Eficiencia medida como:
# total de registros leídos
# total de registros ordenados
18
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Balanceado de N caminos
•
Dos conjuntos de buffer
•
•
•
•
Entrada
Salida
#archivos, divididos proporcionalmente en los
buffer de entrada asignado por el SO.
Método
1. C/partición (con M elementos) se acomoda en un
archivo de entrada
2. Merge entre archivos de entrada produciendo
archivos de salida (con M2 registros ordenados)
3. Continuar dos hasta terminar los archivos de
entrada
4. Convertir archivos de E en arch de S y viceversa
5. Repetir 2 hasta formar una partición con todos los
elementos ordenados.
19
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación
 Algoritmo
N
{ tamaño de c/set }
set_entrada { flag indica cual EoS
base tam. set de
salida }
num_arc_salida { # arc. de salida }
num_particion { # part. Generada }
N := F div 2
{ # arch. de E y S }
set_entrada := false
repetir
{preparar los archivos}
cambiar valor de set_entrada
if set_entrada
then abrir arch 1 a N Entrada
abrir arch N+1 a F Salida
tam_set_salida := F – N
base := N + 1
else abrir arch 1 a N Salida
abrir arch N+1 a F Entrada
tam_set_salida := N
base := 1
20
{fase del método}
num_arc_salida := 0
num_particion := 0
repetir
merge partición de c/arch.Entr.
dentro del arch. numerado
(base + num_arc_salida)
num_particion:=num_particion+1
num_arc_salida:=(num_arc_salida
+1) mod tam_set_salida
hasta terminen los arch. de E
hasta num_particion = 1
if set_entrada
then archivo ordenado N+1
else archivo ordenado 1
IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación

Merge óptimo
• 1 archivo de salida, el resto de entrada
• Se hace el merge entre las particiones de entrada
y genera una de salida esto se repite hasta
generar una partición con todos los datos

Merge multifase
• Mayor complejidad inicial en distribuir las
particiones
• Varios conceptos:
21
• Fibonacci
• Particiones dummy
• # de particiones no se adecua con el # de
Fibonacci IBD - CLASE 4
UNLP - Facultad de Informática
Archivos - Clasificación
# Reg.
Leídos
Tamaño
partición
#
partición
40 clasif. En RAM
+ por intercalación en 40 forma
10000
10000
40
40 clasif. + intercalación en varios
pasos
10000
10000
Selec por reemplazo + intercalación en pasos
2500
Idem anterior reg.
Parcialmente
ordenados
2500
método
22
#
desplaza
mientos
Patron
intercalaci
ón
# desp.
Intercal
acion
Tot.
Desplaz
amiento
40
40
1600
1640
40
40
8:8:8:8:8
520
560
15000
27
160
5:5:5:5:5
423
583
40000
10
160
3:3:4
256
416
IBD - CLASE 4
UNLP - Facultad de Informática
Descargar

Introduccion a las bases de Datos