Bases de datos - Índices
ÍndicesCurso de Bases de Datos
PorElizabeth León Guzman, Ph.D.
ProfesoraIngeniería de Sistemas
Grupo de Investigación MIDAS
Bases de datos - Índices
Introducción
•Son estructuras de datos especializadas para acelerar la búsqueda de registros deseados en los registros de la base de datos que se almacenan en disco duro.
•Funciona de manera similar como un índice de un libro o un catálogo de una biblioteca: para buscar un registro se hará en un índice para buscar en cual bloque de disco se encuentra.
Bases de datos - Índices
Base de Datos
Colección de archivos
Secuencia de registros
Secuencia de campos
Archivos de BD
Tiene un tamaño fijo (asignado) *
Cada archivos tiene registros de un tipo particular
Diferentes archivos se usan para diferentes relaciones
*También hay registros de longitud variable, pero es más complejo el almacenamiento y manejo.
Bases de datos - Índices
Conceptos
•Llave de búsqueda (Search key): atributo o conjunto de atributos usados para buscar los registros en un archivo.•Archivo de índice: registros (llamados entradas de índice) de la forma
Por lo general son más pequeños que el archivo original
Search- key Pointer
Bases de datos - Índices
•Table scan
•Un table scan es una búsquda en donde se leen todas las
filas de una tabla
•Una tabla que no tenga índices creados, solamente puede
hacer búsquedas a través de un table scan
Bases de datos - Índices
•Indices
•Un índice es un objeto de base de datos que ayuda al servidor
a encontrar un dato más rápidamente
•Estructura de un Indice : Caso de Estudio
llave registro pagina
•PAGE 1001
•Barba
•Karsen
•Sarmiento
•1421, 1
•1876, 1
•1242, 1
•1007
•1305
•1062
•PAGE 1132
•1421, 1
•1129, 3
•1409, 1
•Barba
•Cruz
•Díaz
•Espinosa •1018, 5
•PAGE 1007
•Barba
•Garcia
Hernandez
•1421, 1
•1242, 4
•1242, 1
•1132
•1133
•1127
•PAGE 1305
•Karsen
•
•
•1876, 1
•
•
•1311
•
•
•PAGE 1133
•1242, 4
•1421, 2
•1409, 2
•Garcia
•Gomez
•Gonzalez
• •
•PAGE 1127
•1242, 1
•1241, 4
•
•Hernandez
•Jimenez
•
• •
•PAGE 1241
•Oviedo
•Rodriguez
•Wallace
•Jimenez
•10
•11
•12
•13
•PAGE 1242
•Hernandez
•Sarmiento
•Rodriguez
•Garcia
•14
•15
•16
•17
•PAGE 1421
•Barba
•Gomez
•Rodriguez
•
•18
•19
•20
•
•PAGE 1409
•Díaz
•Gonzalez
•Wallace
•
•21
•22
•23
•
(Más páginas)(Más páginas)
(Más páginas)
•Tabla de autores
•(Datos de la
pagina)
Páginas del
índice
CREATE INDEX indice_autor
ON autor(nombre_autor)
llave registro pagina
Bases de datos - Índices
Categorías de índices
•Índices ordenados: Las llaves de búsqueda están almacenadas de forma ordenada.•Índices B-Tree: Árbol balanceado manejando los caminos desde la raíz a cualquier hoja con la misma longitud•Índices Hash: las llaves de búsqueda están distribuidos de manera uniforme en “cubos”(buckets) o bloques utilizando para su ubicación una función hash.
Bases de datos - Índices
Índices Ordenados
•Índices Densos (Dense index)•Índices Dispersos (Sparse index)•Índices primarios•Índices de Clustering•Índices Secundarios•Índices Multinivel
Bases de datos - Índices
Índices Densos
Este tipo de índices genera una entrada paracada valor de llave de búsqueda (por lo tanto decada registro) en el archivo de datos.
Bases de datos - Índices
Índices Densos: Ejemplo
Índice en el atributo ID de la relación Instructor
Índice en el atributo nom_dept de la relación Instructor ordenada por nom_dept
10101
12121
15151
22222
32343
33456
45565
58583
76543
76766
83821
98345
Biologia
Ciencias de la
computacion
Ing. Eléctrica
Finanzas
Historia
Música
Fisica
10101 dikstra
Ciencias de la
Computacion 65000
12121 Wu Finanzas 90000
15151 Mozart Musica 40000
22222 Einstein Fisica 95000
32343 El Said Historia 60000
33456 Gold Fisica 87000
45565 Katz
Ciencias de la
Computacion 75000
58583 Califeri Historia 62000
76543 Singh Finanzas 80000
76766 Crick Biologia 72000
83821 Brandt
Ciencias de la
Computacion 92000
98345 Kim Ing. Electrica 80000
76766 Crick Biologia 72000
10101 Srinivasan Ciencias de la computación 65000
45565 Katz Ciencias de la computación 75000
83821 Brandt Ciencias de la computación 92000
98345 Kim Ing. Eléctrica 80000
12121 Wu Finanzas 90000
76543 Singh Finanzas 80000
32343 El Said Historia 60000
58583 califeri HIstoria 62000
15151 Mozart Música 40000
22222 Einstein Fisica 95000
33465 Gold Fisica 87000
Bases de datos - Índices
Índices Densos: Ejemplo
Portal Suba
Portal Sur
Portal
Américas
Portal Norte
Portal 80
Portal 20 julio
C4 Portal Suba
G5 Portal Sur
G31 Portal Sur
F4 Portal Américas
B5 Portal Norte
B73 Portal Norte
B12 Portal Norte
D4 Portal 80
k10 Portal 20 julio
Bases de datos - Índices
Índices Dispersos
Contiene registros de índices para solo algunos valores de llaves de búsqueda.
–Aplica cuando los registros están ordenados secuencialmente sobre la llave de búsqueda
Bases de datos - Índices
Índices Dispersos•Para ubicar un registro con el llave de búsqueda K:
–Encontrar en el registro de índice con el valor de llave de búsqueda más largo mayor a K–Buscar el archivo secuencialmente empezando en el registro al cual apunta el registro de índice.
76766 Crick Biología 72000
10101 Srinivasan Ciencias de la computación 65000
45565 Katz Ciencias de la computación 75000
83821 Brandt Ciencias de la computación 92000
98345 Kim Ing. Eléctrica 80000
12121 Wu Finanzas 90000
76543 Singh Finanzas 80000
32343 El Said Historia 60000
58583 califeri HIstoria 62000
15151 Mozart Música 40000
22222 Einstein Fisica 95000
33465 Gold Fisica 87000
76766
32343
15151
Bases de datos - Índices
Índices Dispersos•Para ubicar un registro con el llave de búsqueda K:
–Encontrar en el registro de índice con el valor de llave de búsqueda más largo mayor a K–Buscar el archivo secuencialmente empezando en el registro al cual apunta el registro de índice.
C4 Portal Suba 12
G5 Portal Sur 12
G31 Portal Sur 13
F4 Portal Américas 14
B5 Portal Norte 10
B73 Portal Norte 9
B12 Portal Norte 8
D4 Portal 80 7
k10 Portal 20 julio 23
Portal Suba
Portal Américas
Portal 80
Bases de datos - Índices
Índices Primarios
•Definido en un archivo de datos ordenado bajo un campo llave.•Incluye una entrada de índice para cada bloque en el archivo de datos•Se asume que todos los archivos están ordenados secuencialmente en alguna llave de búsqueda.•Incluye una entrada de índice para cada bloque en el archivo; la entrada de índice tiene el valor del campo llave
Bases de datos - Índices
Índices Primarios
Valor llave
primaria Apuntador
Ángel, Camilo
Alzate, Andrés
Caita, Daniel
Gomez, Carlos
Ortega, José
Nombre (Llave
primaria)Cedula Nacimiento Trabajo Salario
Ángel, Camilo
Álvarez, Laura
…
Acosta, carlos
Alzate, Andrés
Batista, Iván
…
Bonilla, Carlos
Caita, Daniel
Cifuentes, Pedro
…
Cruz, Felipe
Gomez, Carlos
Gonzalez, Camilo
…
Hernandez, Juan
Ortega, José
Ospina, Sebastián
…
Zambrano, Miguel
Archivo del índice
Entradas <K(i), p(i)>
Bases de datos - Índices
Índices Clustering
•Definido en un archivo ordenado.
•El archivo está ordenado en un campo que no es una llave.
•Incluye una entrada de índicedistinta para cada valor delcampo, la entrada apunta alprimer bloque de datos quecontiene el registro con ese valorde campo.
Archivo del índice
Entradas <K(i), p(i)>
id_dept Cedula Nacimiento Trabajo
1
1
…
1
2
2
3
…
3
3
3
3
…
4
4
5
5
…
5
5
Campo de
Clustering Apuntador
1
2
3
5
Bases de datos - Índices
Índices Secundarios•Provee un medio secundario para acceder a un archivo para el cual ya existeun índice primario.•El índice secundario debe ser en un campo que puede ser candidato a llave ytiene un valor único para cada registro, o un campo no llave con valoresduplicados.•Los índices secundarios deben ser índices densos.
Índice secundario en la relación de cuentas bancarias sobre el tercer campo que muestra el saldo de la cuenta.
C4 Portal Suba 12
G5 Portal Sur 17
G31 Portal Sur 13
F4 Portal Américas 14
B5 Portal Norte 13
B73 Portal Norte 13
B12 Portal Norte 8
D4 Portal 80 7
k10 Portal 20 julio 23
7
8
12
13
14
17
23
Bases de datos - Índices
Índices
Multinivel•Si el índice primario no cabe en memoria, el acceso se hace costoso.•Solución: Usar el índice primario en disco como un archivo secuencial y construir un índice disperso sobre el índice primario.•Se puede crear niveles hasta que el índice quepa en un bloque de disco.•Se puede crear sobre cualquier tipo de índice (primario, secundario, clustering)
2
5
8
12
15
21
24
29
35
36
39
41
44
46
51
52
55
58
63
66
71
78
80
82
85
89
2
8
15
24
35
39
44
51
55
63
71
80
85
2
35
55
85
Segundo nivel
Primer nivel Valor llave primaria
Índice de dos niveles
Bases de datos - Índices
Índices B-Tree
•Árboles de búsqueda–Orden del árbol p (cant. apuntadores)–Cada nodo contiene p-1 valores de búsqueda– p apuntadores en el orden –<P1,K1,P2,K2,…,Pq-1,Kq-1, Pq> con q≤p
–Pi es apuntador a nodo hijo o Nulo–Ki es valor de búsqueda para un conjunto ordenado de valores
Bases de datos - Índices
Índices B-Tree
•Árboles de búsqueda1.K1< K2<…< Kq-12.∀ X del sub-árbol apuntado por Pi, se tiene que Ki-1<X<Ki con 1<i<q; X<Ki para i=1; Ki-1<X
para i=q
Bases de datos - Índices
Índices B-Tree
•Árboles de búsqueda de orden p=3
Bases de datos - Índices
Índices B-Tree
•Tiene restricciones adicionales que garantizan que el árbol esté balanceado y que el espacio gastado por la eliminación no sea excesivo.•Permite valores de llave de búsqueda que aparecen solo una vez, elimina el almacenamiento redundante le las llaves de búsqueda.•Las llave de búsqueda en nodos no-hoja, no aparecen en otro lado del árbol.
Bases de datos - Índices
Índices B-TreeCada nodo interno es de la forma
< P1, <K1,Pr1>, P2, <K2,Pr2>,…, <Kq-1,Prq-1>, Pq> donde Pr es el dato del apuntador (apuntador al registro cuyo campo llave de búsqueda es igual a Ki)
Bases de datos - Índices
Hash
•Un bloque es una unidad de almacenamiento conteniendo uno o más registros.•En un archivo de organización hash se obtiene el bloque directamente de su valor de llave de búsqueda usando una función hash.•Los registros con diferentes valores de llave de búsqueda pueden ser mapeados en el mismo bloque, pero el bloque completo debe ser analizado secuencialmente para ubicar el registro.•La función hash es una función desde el conjunto de todos los valores de llaves de búsqueda K al conjunto de todos los bloques direccionados B.
Bases de datos - Índices
Ejemplo de Organización de
archivo Hash
•Hay 10 bloques.•La función de hash retorna la suma de las representaciones binarias de los caracteres módulo 10.
–h(Music) = 1–h(History) = 2–h(Physics) = 3–h(Elec. Eng) = 2
•La representación binaria del i-esimo carácter esta asumida para ser el entero i.
Organización del archivo Hash para la relación instructor, usando nom_dept como llave.
12121 Wu Finanzas 90000
76543 Singh Finanzas 80000
15151 Mozart Música 40000
32343 El Said Historia 80000
58583 Califieri Historia 60000
22222 Einstein Fisica 80000
33456 Gold Fisica 60000
98345 Kim Ing. Electrica 80000
76766 Crick Biologia 72000
10101 Dijkstra Ciencias de la computación 65000
45565 Katz Ciencias de la computación 75000
83821 Brandt Ciencias de la computación 92000
Bucket 1
Bucket 0
Bucket 2
Bucket 3
Bucket 5
Bucket 4
Bucket 6
Bucket 7
Bases de datos - Índices
Funciones hash
•La peor función mapea todos los valores de llave debúsqueda al mismo bloque: hace el tiempo de accesoproporcional al número de valore de llave de búsquedaen el archivo.•La función ideal es uniforme: cada bloque es asignadocon la misma cantidad de número de valores de llavesde búsqueda de todo el conjunto posible de valores.•Por lo general ejecutan cómputos sobre larepresentación binaria interna de la llave de búsqueda.
Bases de datos - Índices
Índices hash
•Organiza las llaves de búsqueda, con su apuntador de registro asociado en un archivo de estructura hash.
•Son índices secundarios.
Índice hash en la relación instructor en el atributo ID
76766 Crick Biologia 72000
10101 Srinivasan
Ciencias de la
computación 65000
45565 Katz
Ciencias de la
computación 75000
83821 Brandt
Ciencias de la
computación 92000
98345 Kim Ing. Eléctrica 80000
12121 Wu Finanzas 90000
76543 Singh Finanzas 80000
32343 El Said Historia 60000
58583 califeri HIstoria 62000
15151 Mozart Música 40000
22222 Einstein Fisica 95000
33465 Gold Física 87000
766766
45565
76543
22222
10101
15151
33465
83821
12121
32343
58583
98345
Bases de datos - Índices
Índices en MySQL
CREATE INDEX nombre_indiceUSING tipo_indiceON nombre_tbl (col_nombre_indice,…)
•El tipo de índice es opcional y puede ser definido entre:
–B-Tree (Motor MyISAM, InnoDB, MEMORY/HEAP)–Hash (MEMORY/HEAP)
Se puede crear un índice sobre más de una columna.
DROP nombre_indice ON nombre_tbl
Bases de datos - Índices
Comandos útiles
•show index from TABLA;
•Explain CONSULTA;
Bases de datos - Índices
Bibliografía
•Elmasri y Navathe: “Fundamentos de Sistemas de Bases de Datos”, 6ª y 4ª edición•Silberschatz−Korth−Sudarshan , “Database System Concepts”, 4ª Edición
Top Related