Almacenamiento Y Direccionamiento De Datos

1
II. Indexación y
asociación

Indexación y
asociación

2
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

2
II. Indexación y
asociación

1. Conceptos básicos
• Un índice de BD es similar al índice de un libro.
▫ Las palabras de índice están ordenadas, lo que
hace fácil la búsqueda deltérmino que se esté
buscando.
buscando.
▫ El índice es mucho más pequeño que el libro, con
lo que se reduce aún más el esfuerzo necesario
para encontrar las palabras en cuestión.

• También puede ser comparado con la ficha de
una biblioteca (búsqueda por autor, por título,
etc.)
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociaciónestática

Asociación
dinámica

3
II. Indexación y
asociación

Tipos básicos de índices
• Índices ordenados. Estos índices están
basados en una disposición ordenada de los
valores.
valores.
• Índices asociativos (hash índices). Estos
índices están basados en una distribución
uniforme de los valores a través de una serie de
cajones (buckets).
▫ El valor asignado a cada cajón estádeterminado
por una función, llamada función de asociación
(hash function).
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

4
II. Indexación y
asociación

Técnicas de indexación y asociación
• Existen varias técnicas de indexación y
asociación que deben ser valoradas de acuerdo a
los
los siguientescriterios:
▫
▫
▫
▫
▫

Tipos de acceso
Tiempo de acceso
Tiempo de inserción
Tiempo de borrado
Espacio adicional requerido.
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

5
II. Indexación y
asociación

2. Índices ordenados
• Cada estructura de índice está asociada con una
clave debúsqueda concreta.
▫ Si el archivo que contiene los registros está ordenado
secuencialmente, el índice cuya clave de búsqueda
especifica el orden secuencial del archivo es el índice
primario o índice con agrupación (clustering indices)
▫ Los índices cuyas claves de búsqueda especifican un
orden diferente del orden secuencial del archivo se
llaman índices secundarios o índices sin
agrupación (nonclustering indices).
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

6
II. Indexación y
asociación

Índice primario
• Los archivos con índice primario según una
clave de búsqueda se llaman archivos
secuenciales
secuenciales indexados.
• Se emplean en aquellas aplicaciones que
demandan unprocesamiento secuencial del
archivo completo así como un acceso directo a
sus registros.
• Generalmente el índice primario es la clave
principal.
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

7
II. Indexación y
asociación

Clave de búsqueda:
Nombre-Sucursal

Archivo secuencial para losregistros cuenta
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

8
II. Indexación y
asociación

Índices densos y dispersos
• Un registro índice o entrada del índice
consiste en un valor de la clave de búsqueda y
punteros
punteros a uno o más registros con ese valor de
la clave de búsqueda.
• Elpuntero a un registro consiste en el
identificador de un bloque de disco y un
desplazamiento en el bloque de disco para
identificar el registro dentro del bloque.
Conceptos
básicos

Índices
ordenados

Archivos y
Arboles B+

Archivos y
Arboles B

Asociación
estática

Asociación
dinámica

9
II. Indexación y
asociación

Índice denso
• Aparece un registro índice por cada...