java

1

GESTIÓN DE DATOS 2012
- Clase 2 -

2

Búsqueda de información. Manejo
de índices


Cuando se realiza la búsqueda de un dato, se
deben considerar:
•
La cantidad de accesos a disco en pos de
encontrarlo. Costo alto.
•
La cantidad de comparaciones. Costo
relativamente bajo (despreciable).

3

Búsqueda de información. Manejo
de índices


El proceso de búsqueda implicaun análisis de
situaciones en función del tipo de archivo sobre el
que se quiere buscar información:
•
Archivo sin orden preestablecido (peor caso N
accesos).
•
Archivo físicamente ordenado y el argumento
de búsqueda coincide con el criterio de
ordenación (peor caso N accesos).
•
Archivo físicamente ordenado y registros de
longitud fija (peor caso log2 (N) + 1).

4

Búsqueda deinformación. Manejo
de índices




Supongamos ahora que tenemos el problema de
encontrar libros en una biblioteca por autor, título o
tema.
•
Compramos 3 copias de cada libro y 3 edificios de
biblioteca separados. Edificio1: libros ordenados
por autor; edificio 2: libros ordenados por título, y
Edificio 3: libros ordenados por tema (absurdo).
Supongamos que tenemos el problema debuscar un
tema en un libro, ¿cómo lo resolvemos?
•
Recorremos página por página.
•
Utilizamos el índice temático.

5

Búsqueda de información. Manejo
de índices
Índice: Estructura de datos adicional que permite

agilizar el acceso a la información almacenada en un
archivo.




En el índice se almacenan las claves de los registros
del archivo, junto con la referencia de accesoa
cada registro asociado a la clave. Es necesario que
las claves permanezcan ordenadas.
El índice es otro archivo con registros de longitud
fija, independiente de la estructura del archivo
original.

6

Búsqueda de información. Manejo
de índices







Un índice posibilita imponer un orden en un archivo
sin que realmente este se reacomode.
Índice, ¿cómo se genera ymantiene?
Índice primario: Creado a partir de la clave
primaria.
Trabajemos con el siguiente archivo de datos,
organizado con registros de longitud variable.

7

Búsqueda de información. Manejo
de índices
Código

Título

Grupo musical
compositor

Dir. Reg.

Cía.

Interprete

15

WAR

23 Early Morning

A-ha

A-ha

36

SON

13 Just a Like a Corner

Cock Robin

CockRobin

83

BMG

11 Selva

La Portuaria

La Portuaria

118

SON

15 Take on Me

A-ha

A-ha

161

VIR

2310 Land of Confusion

Genesis

Phil Colins

209

VIR

1323 Summer Moved On

A-ha

A-ha

248

AME

2323 Africa

Toto

Toto

275

RCA

1313 Leave of Ney York

REM

REM

313

ARI

2313 Here Come The Rain Aigan

Eurythmics

Annilennox

8

Búsqueda de información. Manejo
de índices






Con los datos anteriores, formamos la clave
primaria con los atributos Cía + Código.
Al crearse el archivo, se creará el índice primario
asociado.
Veamos cómo queda armado en índice primario.

9

Búsqueda de información. Manejo
de índices
Clave

Ref.

AME2323

248

ARI2313

313

BMG11

83

RCA1313275

SON13

36

SON15

118

VIR1323

209

VIR2310

161

WAR23

15

10

Búsqueda de información. Manejo
de índices


Teniendo creado el índice primario, hay que
considerar las siguientes operaciones:
•
Altas.
•
Modificaciones.
•
Bajas.

11

Búsqueda de información. Manejo
de índices




Retomando nuestro ejemplo, ¿cuántos de Uds.
buscarían algrupo musical de la canción “África”
por la clave primaria VIR1323?
No es natural ni intuitivo solicitar un dato por clave
primaria, sino por otros atributos (por ej. nombre de
canción o grupo musical). Estos atributos podrían
contener valores repetidos en el archivo original,
por lo tanto no pueden ser clave primaria.

12

Búsqueda de información. Manejo
de índices




Clave...