UA

Unidad 1: Planificación del

Almacenamiento e Indexación

Bases de Datos Avanzadas, Sesión 2-3:

Estructuras Índices

Iván González Diego

Dept. Ciencias de la Computación
Universidad de Alcalá

1
 INDICE
UA

 Introducción.
 Clasificación
 Índices Secuenciales (ordenados)
 Árboles B+
 Árboles B
 Índices Asociativos
 Índices Multiclave
 Retícula
 Asociación Dividida
 Mapas de Bits
Referencias: Silberschatz 4ª Ed. Pp 249 - 315
Elmasri, 3ª Ed. Pp 105 - 181
2
 Indización de datos
UA

 Mejorar el tiempo de búsqueda de los datos de la base de datos.

 Existen dos tipos básicos
• Ordenados ⇒ basados en la disposición ordenada de valores
• Asociativos (hash) ⇒ distribución uniforme de valores por funciones
hash entre cajones (buckets).

 Criterios de valoración:
• Tipos de acceso: búsqueda único valor o rango de valores.
• Tiempo de acceso: tiempo en buscar un elemento de datos o varios
• Tiempo de inserción: buscar + actualizar
• Tiempo de borrado: buscar + actualizar
• Espacio adicional requerido por el índice.
 Coste de Buscar datos (C)= Coste Buscar Índice (Cindice) +
Coste Buscar archivo de Datos (Cdatos)
3
 Clasificación de índices
UA

 Consideraciones respecto al campo de búsqueda.

 V(A)  número de valores diferentes para el campo A en archivo / tabla
 nR  número de registros del archivo (tabla) R

 Archivo - Ordenado respecto al campo de búsqueda  primario

Datos - No ordenado respecto al campo de búsqueda  secundario

 Valores del campo: - Campo clave  1 valor dentro del archivo / tabla
- Campo no clave  valores repetidos

 nRi  número registros en el índice (nunca entradas/valores duplicados)

 Registro índice  Valor campo + Puntero (a Registro datos ó Bloque)

LRi = LK + LPB ó LRi = LK +LPR

4
 Clasificación de índices
UA

 Clasificación:

• Primario + campo clave  nRi = V(A) = nR

• Primario + campo no clave  nRi = V(A) ( sólo se apunta al primero)

• Secundario + campo clave  nRi = V(A) = nR

• Secundario + campo no clave  cajones punteros  nRi = V(A) (se apunta a

cada cajón)
Cajones de punteros contienen siempre Punteros a
Registro

5
 Estimación registros/bloques a recuperar
UA
del archivo de datos (Cdatos)
 Número registros a recuperar  nrc

 Si el campo es clave  nrc=1  leer un bloque del archivo datos.

 Si el campo no es clave  nrc= Nv * nR / V(A)

donde Nv Nº valores diferentes que cumplen la condición

• Si el archivo datos ordenado (primario)  leer nrc / fR bloques datos

• Si el archivo no está ordenado (secundario)  leer nrc bloques datos (peor caso)

6
 Estimación registros/bloques a recuperar
UA
del archivo de datos (Cdatos)

 Ejemplo: fR =2 (registros /bloque), nR=6, bR=3, σ campo=A(R) ?

Archivo de datos

Campo Campo
A A
A B
A A
A V(Campo)=2 A
B B
B A

Primario (Ordenado) Secundario (No Ordenado)

nrc=6 / 2=3 reg. nrc=6 / 2=3 reg.
Leer = 3 / 2 =2 bl. datos Leer = 3 bl. datos

7
 Índices secuenciales (Índice ordenado)
UA

 El índice es un archivo secuencial que siempre está ordenado.

 Dos tipos básicos:
• Índice Primario
– archivo datos ordenado respecto a una clave de búsqueda.
– Suele ser la clave primaria pero no tiene por qué.
– Índice primario ≠ índice sobre clave primaria.
– Otro nombre: índice con agrupación (cluster index)

• Índice secundario
– Archivo datos no ordenado respecto a la clave de búsqueda.
– Otro nombre: índice sin agrupación (non cluster index)

8
 Índices secuenciales: Primarios
UA

 Índice primario:

• Los ficheros se ordenan secuencialmente a partir de una

clave de búsqueda principal.

• Estos archivos se llaman archivos secuenciales indexados.

• Muy utilizados en bases de datos que exigen procesamiento

secuencial y acceso directo a sus registros

• Condicionan ciertos tipos de indexación ⇒ índice disperso.

Índice denso

9
 Índices secuenciales: Primarios
UA

 Ejemplo:
Archivo de datos (bR)
LRi = LK + LPR

nRi

Índice (bRi)

Cindice= log2 (bRi)

 Registro índice: valor de la clave de búsqueda + punteros a

registros con ese valor de la clave de búsqueda.
 Puntero a registro: numero de bloque + offset dentro del bloque10
 Índices secuenciales: Densos
UA

 Índice Denso:

• Se crea un nuevo registro índice para cada valor de la clave

de búsqueda en el archivo.

• El registro índice contiene la clave de búsqueda y un puntero

al primer registro de la base de datos con ese valor

• Destaca que esta aproximación es correcta si los ficheros de

la base de datos están ordenados con la estructura del índice
primario.

11
 Índices secuenciales: Densos
UA

 Su funcionamiento es sencillo: Al realizar una búsqueda en la base de

datos de accede al índice y se busca el elemento que coincida con la
clave de búsqueda.
 Una vez encontrado, se puede acceder de forma directa al registro que
contiene esa información, y a partir de ese registro, si hay otros con la
misma clave de búsqueda, aparecerán a continuación.

Cindice= log2 (bRi)

12
 Índices secuenciales: Dispersos
UA

 Índice Disperso:

• Sólo se crea el registro índice para ciertos valores  una

entrada por cada bloque del archivo de datos

• Al igual que los densos ⇒ cada registro índice contiene un

valor de la clave de búsqueda y un puntero al primer registro
con ese valor de clave

• Utilizan menos espacio al no almacenar todas las claves de

búsqueda

• Menor mantenimiento para las inserciones y borrados.

• Se basan en los índices primarios. 13

 Índices secuenciales: Dispersos
UA

 Para localizar un registro:

• Se busca la entrada del índice con el valor más grande que sea
menor ó igual al valor que se está buscando.
• Una vez encontrado ⇒ se pasa a recorrer la base de datos hasta
encontrar el registro exacto que se busca.

Cindice= log2 (bRi)

14
 Índices secuenciales: Multinivel
UA

 Índices Multinivel  Hacer índices dispersos sobre índices de 1

nivel (los anteriores). Como si fuese un árbol hasta el nivel dado.

• Se utilizan para grandes cantidades de datos.

• Utilizan bloques de índices, generando una estructura en árbol con

dos niveles de indirección.

• Cada bloque de índices corresponde normalmente con un bloque de

disco ⇒ se optimizan al máximo los accesos.

• El bloque principal ó índice externo se suele cargar en la memoria

principal o en la memoria de intercambio, al ser el más utilizado.

• Dependiendo de la cantidad de datos, se puede aumentar el nivel de

indirección.
15
 Índices secuenciales: Multinivel (N niveles)
UA

Nivel 1(bRi1=3) Archivo datos (bR=5)

N=2
A 1
B 2
1
Nivel 2(bRi2=2) 3
A 3

LK+LPR B 4
1
5
A 5

LK+LPB B 6
5
7 C 7
9 C 8

9 D 9
B 10

Cindice= log2 (bRiN) + N-1= log2 (2) + 2-1 LR 16

 Índices secuenciales secundarios
UA

 Los índices secundarios están estructurados de manera diferente

a los primarios.
 Es necesario mantener referencias a todos los registros de una
clave de búsqueda ⇒ Siempre Densos
 Los índices secundarios sobre claves candidatas son similares a
los índices primarios, excepto que los registros apuntados por los
valores del índice no se encuentran almacenados de forma
secuencial.
 Se suelen utilizar bloques de punteros asociados a cada una de
las claves de búsqueda.

17
 Índices secuenciales secundarios
UA

Archivo de Datos (bR)

Archivo Índice (bRi)

LK+LPB
LR
LPR Cindice= log2 (bRi) + bcaj
Cajones de Punteros (bcaj)
18
1 cajón tiene nRi / V(campo) Punteros
 Ejemplos
UA

 Ejemplos de índices secuenciales:

Ejemplos_indices_secuenciales.ppt

19
 Índices de Árbol B+
UA

 Los archivos secuenciales indexados tienen problemas a la hora

de realizar búsquedas ⇒ a medida que crece el fichero se va
degradando el rendimiento.

 Las estructuras de índice de árbol B+ mantienen su eficiencia a

pesar de la inserción y borrado de datos.

 Los árboles B+ son estructuras arbóreas equilibradas, donde los

caminos de la raíz a cada nodo hoja es fijo

 Cada nodo no hoja tiene entre n/2 y n hijos, donde n se fija

para cada árbol en particular.

20
 Índices de Árbol B+
UA

 Nodo típico de Árbol B+, Pi  puntero , Ki  valor campo , Ki < Ki+1

B (bloque)

 n punteros (grado de salida):

• Intermedios son punteros a bloques
• Hoja son punteros a registros ó bloques.
 n-1 valores de la clave de búsqueda
 Nodos hoja contengan al menos (n-1)/2 valores.
 Nodos intermedios al menos n/2 punteros
 Nodo raíz al menos 2 punteros.
 Característica árbol: balanceado.
21
 Índices de Árbol B+
UA

 Diseño de los nodos

 Nodo intermedio / Raíz  Punteros a bloque + valores campo
B
PB1 K1 PB2 K2 … PBn-1 Kn-1 PBn

n*LPB + (n-1)*LK ≤ B
 Nodo hoja  Punteros a registro o bloque + valores campo + puntero a
bloque
B
PR1 K1 PR2 K2 … PRnh Knh PB
nh*(LPR + LK) + LPB ≤ B

LPR /LPB  longitud puntero a registro /bloque (bytes)

LK  longitud de campo de búsqueda del índice (bytes)
22
 Índices de Árbol B+
UA

 Estructura de ejemplo de un árbol B+

 Cada nodo del árbol contiene n punteros a bloques, junto con n-1 claves
de búsqueda. N=3 niveles, n=3 punteros en cada nodo

n=3

n=3

nh=2

nRi=V(campo) = 6, Número nodos hojas= bhojas= nRi / nh = 6/ 2 = 3

Número nodos intermedio 1= bhojas/ n = 3 / 3 = 1 , es la raíz ya.
Cindice = N = 2 niveles en esta estimación. 23
 Índices de Árbol B+
UA

PR1 PR2 Daimiel PB

Índice primario + campo no clave

Cindice = N
24
 Índices de Árbol B+
UA

PB1 Barcelona PB2 Daimiel PB3 Nodo hoja

PR1 PR1
PR2
Archivo datos
Cajones Punteros
(bcaj un cajón) C-101 Daimiel 500
C-212 Bracelona 750
C-110 Daimiel 600

Índice secundario + campo no clave  cajones punteros

Cindice = N + bcaj
25
 Ejemplos
UA

 Ejemplo de árboles B+

Ejemplos_arboles_Bmas.ppt

26
 Archivos de índices de Árbol B
UA

 Son similares a los árboles B+ excepto que el árbol B elimina el

almacenamiento redundante de los valores de la clave de
búsqueda.
 Esta operación se realiza añadiendo un campo más a los nodos
internos del árbol, y eliminando por tanto esos datos de los nodos
hojas finales, lo que crea una reestructuración completa del árbol

m*LPB + (m-1)*(LK+LPR )≤ B , nodo Intermedio 27

 Archivos de índices de Árbol B
UA

 En los árboles B es más complicado el borrado, pero más simple

la inserción.

28
 Ejemplo
UA

 Say we insert record with key = 25

n=4
leaf

10
20
30
 Afterwards:

20
–

–
10

25
30 29
 Asociación Estática
UA

 Es una técnica basada en la utilización de funciones de

asociación.

 Sea K el conjunto de los valores de clave de búsqueda.

 Se B el conjunto de todas las direcciones de los cajones.
 Una función h es una función de K a B tal que:
h(k)=B
 Igual que archivos hash, pero es un índice. Mismas propiedades
 Los cajones guardan valor del campo + Punteros
 Los cajones están todos creados (estáticos).

30
 Índices asociativos
UA
Archivo Datos (bR)
LR

Cajón desbordamiento (overflow)

h = (suma de dígitos cuenta) mod 7

H(C-217)  (2+1+7) mod 7 = 3 (cajón 3)
Cajón bc
Cindice = leer cajones = bC 31
LRi=LK+LPR
 Ejemplo
UA

 Ejemplo de índices asociativos:

ejemplos_indices_asociativos.ppt

32
 Asociación Dinámica
UA

 Las técnicas de asociación estática tienen el problema de que

poco a poco la base de datos va aumentando su tamaño ⇒
irremediablemente se llegan a situaciones de desbordamiento.

 Las técnicas de asociación dinámica permiten paliar esos

problemas ⇒ modificando la función de asociación
dinámicamente para acomodarse al aumento o disminución de la
base de datos.

 En esta parte del tema se estudiará la estructura asociativa

general dinámica.

33
 Asociación Dinámica
UA

Número de cajones = 2i

Dirección cajón 0 cajón 0,

Dirección cajón 1
Dirección cajón 2

Dirección cajón 3

Cindice= Cleer tabla direcciones + Cleer cajón 34

 Asociación dinámica: Ejemplo
UA

 Ejemplo asociación dinámica:

ejemplos_indices_asociativos_dinamicos.pptx

35
 Definición de índices en SQL
UA

 La normal SQL no permite el control de los índices de la base de

datos.

 Aún así, la mayoría de sistemas permiten la gestión de índices:

 Ejemplos:

• Create index <nombre-indice> on <nombre-relación> (<lista-

atrbutos>)
• Create index indice-s on sucursal(nombre sucursal).
• Create unique index indice on tabla(clave-unica).
• Drop index <nombre-indice>

36
 Accesos Multiclave
UA

 Muchas consultas realizadas a la base de datos constan de

condiciones en varios índices:

Select * from tabla where Campo1>10 and Campo2<7

 Para este tipo de casos se puede:

• Usar primero el índice Campo1 y luego el Campo2

• Usar primero el Campo2 y luego el Campo1
• Hacer la intersección de ambos índices con las condiciones
dadas.

37
 Archivos en Retícula
UA

 Son archivos que intrínsecamente sitúan la información para su

uso con múltiples índices.

 Se basan en la utilización de escalas lineales.

 Las celdas de los archivos en retícula apuntan a los cajones de

datos.

 Si se desean utilizar n índices en la retícula, se crearán arrays de

retícula n-dimensionales.

38
 Archivos en Retícula
UA

Punteros Bloque (LPB) , (n1+1)*(n2+1)

LK1

n1

bc

LK1+LK2+LPReg

n2
LK2

Rejilla
Cindice = CLeer Rejilla + CLeer Cajones LRejilla= n1*LK1+n2*LK2+(n1+1)*(n2+1)*LPB bytes 39
BRejilla= LRejilla/ B bloques
 Índices en Retícula: Ejemplo
UA

 Ejemplo de índice en retícula:

ejemplos_indices_rejilla.pptx

40
 Asociación dividida
UA

 Es un tipo de asociación donde se asignan valores de la función

hash a las claves compuestas, y a partir de ellas se lleva a cabo
la indexación.

 La clave hash se divide en tantos segmentos como claves

individuales se utilicen para generar la clave principal.

101 111

Campo1 h1 h2

Campo2 41
Cindice = Cleer cajones
 Asociación dividida: Ejemplo
UA

 Ejemplo asociación dividida:

ejemplos_asociacion_dividida.ppt

42
 Índices de Mapas de Bits
UA

 Índices especializados para la consulta sencilla sobre varias claves.

 Registros numerados secuencialmente empezando de 0

Lmapa = nR bits
 Número de mapas de cada campo  V(campo)
 Cada mapa tiene nR bits. bmapa = (Lmapa/8) / B
 Leer secuencialmente los registros
Número mapas = V(campo)
 Para contar tuplas

Cindice = Cleer mapas bits

43
 Índice Mapa de Bits: Ejemplo
UA

 Ejemplo mapa de bits:

S03-U1-ejemplos_indices_bitmap.ppt

44