PDF de programación - Tema 8. Estructuras de datos en memoria secundaria

Sistemas de Información II
Tema 8. Estructuras de
datos en memoria
secundaria

Bibliografía:
Elmasri y Navathe: “Fundamentos de Sistemas de Bases de

Garcia-Molina, Ullman y Widom: “Database systems: the

complete book”. Prentice-Hall (Capítulos 12 y 13).

Datos”

3ª edición, 2002 (Capítulo 6).

Carlos Castillo

UPF – 2008

1

Indexación

Índice

Datos

Consulta

Índice

Datos

Respuesta

2

Indexación

Índice

Estructura que permite encontrar
rápidamente un registro de datos

Requerimientos

Bajo sobrecosto (overhead) en espacio
Alta velocidad de búsqueda
[Opcional] Alta velocidad de inserción
[Opcional] Alta velocidad de borrado

3

Índices en ficheros

secuenciales

4

Fichero secuencial

10 | Juan
20 | Pedro
30 | Diego
40 | Ana
50 | María
60 | Iván

Bloques

Persona(idpersona int, nombre char(12))
Asumimos bloque es de tamaño 32 bytes

(anormalmente pequeño)

5

Índice denso

10 B1R1
20 B1R2
30 B2R1
40 B2R2
50 B3R1
60 B3R2
Índice

10 | Juan
20 | Pedro
30 | Diego
40 | Ana
50 | María
60 | Iván

Datos

Todos los elementos están en el índice

6

Otro ejemplo índice denso

Datos (19 bytes)

Índice (4 ints)

0         1        
0123456789012345678
JUANPEDRODIEGOTOMAS

0
4
9
14

Veloz en la recuperación
de registros por número

ej.: recuperar registro 2

7

Índice disperso

10 B1R1
30 B2R1
50 B3R1

Índice

10 | Juan
20 | Pedro
30 | Diego
40 | Ana
50 | María
60 | Iván

Datos

Sólo algunos de los elementos están en el índice

Densidad del índice = claves indexadas / claves totales
8

Índice primario

Índice sobre el atributo según el cual están
ordenados los elementos, con el primer
elemento de cada bloque

Es un índice disperso

Aaron, Ed
B1
Adams, John B2
...
Wright, Pam Bn

Bloque 1
Aaron, Ed – Acosta, Marc

Bloque 2
Adams, John – Akers, Jan

...

Bloque n
Wright, Pam – Zimmer, Byron
9

Cálculo costo acceso

sin índice

Datos

Número de registros
Tamaño del bloque
Tamaño del registro R = 100 bytes

r = 30,000 registros
B = 1,024 bytes

¿Costo búsqueda binaria?

Elementos por bloque = R/B ~ 10
Bloques totales = r / 10 = 3,000 bloques
Costo búsqueda binaria = log2(3000) ~ 12

10

Cálculo costo acceso

con índice

Datos

r = 30,000 registros
B = 1,024 bytes

Número de registros
Tamaño del bloque
Tamaño del registro R = 100 bytes
Tamaño de la clave
V = 9 bytes
Tamaño del #bloque P = 6 bytes

¿Costo búsqueda binaria?

Tamaño del índice: (V+P)*3,000 = 45,000
Número de bloques: 45,000/1,024 = 44
Búsqueda binaria = log2(44) ~ 6 + 1 = 7

11

Desventajas de este índice

Inserción y borrado son costosos
Solución:

Inserción: desbordamiento de bloques
Borrado: marca de “borrado” por elemento

12

Índice de agrupación

Registros ordenados por un campo que
no es único.
Ej.: cod_aero, num_vuelo

Cod_aero Bloque
AAR
LAN
QAT
VAR

B1
B1
B2
B3

Bloque 1
AAR, 222
AAR, 333
LAN, 444

Bloque 2
LAN, 555
LAN, 666
QAT, 777

Bloque 3
VAR, 888

13

Índice de agrupación con

bloques separados

Se reserva espacio en cada bloque

Bloque 1
AAR, 222
AAR, 333
#
next #

Bloque 2
LAN, 444
LAN, 555
LAN, 666
next 3

Cod_aero
Bloque
AAR
LAN
QAT
...

1
2
4

Bloque 3
LAN,777
#
#
next #Bloque 4
QAT,888
QAT,999
#
next #

14

Índice secundario

Se construye sobre un campo que no
es clave primaria
Es un índice denso (cada registro tiene
un lugar en el índice)

15

Índice secundario,
sobre campo único

Ej.:

Pais( id_pais, nombre_pais )

nombre_pais
Argentina
Argelia
Burundí
Camerún
Chad
...

id_bloque
3
1
3
2
2

Bloque 1
1, Francia
2, Argelia
3, Suecia

Bloque 2
4, Camerún
5, Chad
6, México

Bloque 3
7, Burundí
8, Noruega
9, Argentina

16

Índice secundario,

sobre campo no-único
Ej.: Persona( dni, nombre, apellido )
Bloque 1
x, Anna, x
x, Joan, x

Bloque 2
x, Jordi, x
x, Anna, x

Bloque 3
x, Joan, x
x, Jordi, x

1
B1R1, B2R2

nombre id_indice
Anna
Joan
Jordi
Xavier

1
2
3
4

2
B1R2, B3R1

3
B3R2, B2R1

Se utiliza un nivel intermedio de indirección

17

Índices multinivel

18

B-Tree

“Block-tree”

[Bayer & McCreight, 1972]

Árbol balanceado
Típicamente (mínimo) 3 niveles
Variante B+ es más popular

19

Nodo hoja (externo)

34

82

95

Al registro 34

Al siguiente hermano

Al registro 82

Al registro 95

20

Nodo interno

21

52

75

x < 21

75 <=x

75

21 <= x < 52

21

52 <=x < 75

52

21

B-Tree

13

7

23 31 43

2

3

5

7 11

13 17 19

23 29

31 37 41 43 47

22

Búsqueda en B-Tree

Buscar un elemento

Nodo hoja: búsqueda binaria entre los
punteros
Nodo interno: búsqueda binaria y
descender por el nodo apropiado

Búsqueda de elementos dentro de un
rango (WHERE x > 10 AND x < 20)

23

Reglas del B-Tree

La raíz tiene 1 elemento (2 punteros) al
menos
Todas las hojas están al mismo nivel
Existe una ocupación mínima (no sólo
máxima)

En nuestros ejemplos es 1

Existe una ocupación máxima (en este
caso k=3)

24

Insertar (cid:28) 12(cid:29) en B-Tree (trivial)

13

7

23 31 43

2

3

5

7 11 12 13 17 19

23 29

31 37 41 43 47

25

Insertar (cid:28) 40(cid:29) en B-Tree

13

7

23 31 43

2

3

5

7 11

13 17 19

23 29

43 47

31 37

40 41

26

Insertar (cid:28) 40(cid:29) en B-Tree (cont.)

13 40

7

23 31

43

2

3

5

7 11

13 17 19

23 29

43 47

31 37

40 41

27

Borrado de (cid:28) 7(cid:29) en B-Tree

13

7

23 31 43

2

3

5

7 11

13 17 19

23 29

31 37 41 43 47

28

Borrado de (cid:28) 7(cid:29) en B-Tree (cont.)

13

5

23 31 43

2

3

5 11

13 17 19

23 29

31 37 41 43 47

29

Borrado de (cid:28) 11(cid:29) en B-Tree

13

5

23 31 43

2

3

5 11

13 17 19

23 29

31 37 41 43 47

30

Borrado de (cid:28) 11(cid:29) en B-Tree (cont.)

13

5

23 31 43

2

3

5

13 17 19

23 29

31 37 41 43 47

31

Borrado de (cid:28) 11(cid:29) en B-Tree (cont.)

13

13

23 31 43

2

3

5

13 17 19

23 29

31 37 41 43 47

32

Borrado de (cid:28) 11(cid:29) en B-Tree (cont.)

23

13

31 43

2

3

5

13 17 19

23 29

31 37 41 43 47

33

Contenidos del B-Tree

Un B-Tree de orden k (datos por nodo)
y altura h, ¿cuántos elementos puede
tener?

34

Hashing

35

Función de Hashing

N claves en un

dominio de tamaño D

h(.)

N << D

Típicamente
enteros entre
0 y M

Con M > N

36

Función de hashing típica

int hashfunction(char *s) {

int i;
for( i=0; *s; s++ ) {

i = 131*i + *s;

}
return( i % M );

}

37

Ejemplo simple

http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables

38

Colisión: solución con

lista enlazada

http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables

39

Colisión: solución con

linear probing

http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables

40

Hashing en memoria

secundaria

Se usa M pequeño (M < N)
Cada bucket de la tabla de hashing es
uno de los M bloques
Se admiten k colisiones, k=registros
por bloque
Los bloques pueden tener punteros a
bloques para desbordamiento
Cuando se llena (M*k) puede ser muy
lento hacer rehashing

41

Hashing extensible

La función de hashing tiene x bits
Se ocupa primero 1 bit => sólo 2
buckets
Cuando se produce overflow, se
reorganiza para ocupar 2 bits => 4
buckets
La tabla de hashing crece
dinámicamente duplicando su tamaño

42

Resumen

Los SGBD ocultan una alta complejidad
Conocer cómo se organizan cada motor
de bases de datos ayuda a obtener
mejor eficiencia
Índices generan sobrecosto en espacio
y sobrecosto en tiempo al modificar los
datos => usar responsablemente

43