Almacenamiento e indexacinSilberschatz, A., Korth, H.F., Sudarshan, S., Fundamentos de Bases de Datos, 5 edicin, Madrid, 2006 Pons, et al. Introduccin a las Bases de datos, Thomson, 2005

Marta Zorrilla Universidad de Cantabria

Tabla de contenidosIntroduccin Medios de almacenamiento fsico Mtodo de acceso a datos El gestor de disco del SO El gestor de archivos del SGBD Representacin de la base de datos en el nivel interno Indexacin y asociacin Organizacin de registros en archivos Organizacin secuencial Indexacin Fichero secuencial indexado ndices densos y dispersos ndices jerrquicos o multinivel ndices B y B+ Asociacin Hashing esttico y dinmico Comparacin entre indexacin ordenada y hashing Definicin de ndices en SQL

2

Lecturas recomendadasBsicas Cap. 11 y 12. Silberschatz, A., Korth, H.F., Sudarshan, S., Fundamentos de Bases de Datos, 5 edicin, Madrid, 2006. Cap. 13 y 14. Elmasri, R., Navathe, S.B., Fundamentos de Sistemas de Bases de Datos, 3; edicin, Pearson Education, 2008. Cap. 1. Pons, O. et al. Introduccin a los sistemas de bases de datos. Paraninfo. 2008 Complementarias Delaney, Kalen. Inside Microsoft SQL server 2005 : the storage engine. 2007. England, Ken. Microsoft SQL server 2000 performance optimization and tuning handbook. 2001.

3

IntroduccinSGBD: almacenar grandes cantidades de informacin de forma permanente y de manera eficiente. Nivel interno expresa las operaciones sobre los datos en trminos de actuacin sobre unidades mnimas de almacenamiento denominadas pginas de BD. Provee al administrador del gestor mecanismos para optimizar el almacenamiento y el acceso a datos. Nivel fsico se encuentra implementado en el sistema operativo, proporciona al gestor una capa de abstraccin sobre el hardware. El nivel interno del gestor realiza el acceso a los medios de almacenamiento mediante llamadas a los servicios del sistema de archivos proporcionado por el SO.Programa Programa 11 Programa Programa 22 Programa Programa nn

4

Vista A

Nivel Lgico

Sistema Gestor de Bases de Datos (SGBD)

Nivel Interno

Dispositivos de almacenamientoVelocidad Velocidad de acceso de acceso (ns) (ns) Cach Cach Memoria principal Memoria principal Memoria flash Memoria flash Discos magnticos Discos magnticos Discos pticos Discos pticos Cintas magnticas Cintas magnticas 10-6 10-5 10-4 5-10 8-150 >1000 10 0.1 0.5 1 10-3 0.5 *10-3 10-3 Coste Coste ($/Mb) ($/Mb) Capacidad Capacidad (Mb) (Mb) 0-10 1-104 1-104 104 - 105 102 - 104 102 - 106 Volatilidad Volatilidad

5

Si Si No No No No

Coste: coste de adquisicin entre capacidad de almacenamiento Fiabilidad: tiempo medio entre fallos Prdida de datos ante fallos de alimentacin y cadas del sistema Fallos fsicos del dispositivo de almacenamiento

Cach y memoria principalCach: la forma de almacenamiento ms rpida y costosa; voltil; gestionada por el hardware del sistema. Memoria principal: Acceso rpido (10s a 100s de nanosegundos) Generalmente demasiado pequea (o demasiado costosa) para almacenar la base de datos completa Normalmente se utilizan capacidades de unos pocos Gigabytes. Las capacidades han crecido y los costes por byte han disminuido de manera constante y rpida Voltil : el contenido de la memoria principal normalmente se pierde si se produce un fallo de alimentacin o una cada del sistema.

6

Memoria flashLos datos se mantienen ante un fallo de alimentacin Los datos se pueden escribir una sola vez en una posicin, pero una posicin se puede borrar y escribir de nuevo Pueden soportar slo un nmero limitado de ciclos de escritura/borrado. El borrado se tiene que hacer sobre bancos enteros de memoria La lectura es aproximadamente tan rpida como la de memoria principal Pero la escritura es lenta (pocos microsegundos), el borrado es an ms lento El coste por unidad es similar al de la memoria principal Ampliamente utilizado en dispositivos embebidos tales como cmaras digitales tambin conocida como EEPROM (Electrically Erasable Programmable Read-Only Memory)

7

Discos magnticosLos datos se almacenan en discos giratorios, y que se leen/escriben magnticamente Es el principal medio de almacenamiento de datos a largo plazo; tpicamente almacenan bases de datos enteras. Los datos se deben mover de disco a memoria principal para acceder a ellos, y escritos de nuevo hacia el disco si se modifican Los accesos son mucho ms lentos que a memoria principal Acceso directo es posible leer datos de disco en cualquier orden, al contrario que en las cintas magnticas Las capacidades actuales llegan hasta a cientos de GB Mucha mayor capacidad y menor coste/byte que la memoria principal/flash Crece de manera constante y rpida con las mejoras tecnolgicas (factor de 2 a 3 cada 2 aos) Sobrevive a fallos de corriente y cadas del sistema Los fallos de disco pueden destruir datos, pero son muy infrecuentes

8

Almacenamiento pticoNo-voltil, los datos se leen pticamente de un disco giratorio utilizando un lser Los medios ms comunes son CD-ROM (640 MB) y DVD (4.7 a 17 GB) Los discos pticos de una-escritura, muchas lecturas (WORM) se utilizan para almacenamiento de archivos (CD-R y DVD-R) Tambin existen versiones de mltiples escrituras (CD-RW, DVD-RW, y DVD-RAM) Las lecturas y escrituras son ms lentas que en los discos magnticos Juke-box: son sistemas con un nmero elevado de discos extrables, unos pocos lectores y un mecanismo para la carga y descarga automtica de discos. Permiten el almacenamiento de grandes volmenes de datos

9

Cinta magnticaNo voltil, se utiliza principalmente para copias de seguridad (recuperacin frente a fallos de disco) y para archivo de datos Acceso secuencial mucho ms lento que el disco Capacidad muy alta (hay cintas de 40 a 300 GB) Las cintas se pueden extraer del dispositivo El almacenamiento es mucho ms barato que en disco, pero los dispositivos son caros Existen jukeboxes de cintas para el almacenamiento de cantidades masivas de datos Cientos de terabytes (1 terabyte = 109 bytes) hasta un petabyte (1 petabyte= 1012bytes)

10

JerarquaAlmacenamiento primario (registro temporal de datos)

11

Almacenamiento secundario o en lnea (almacenamiento persistente) Almacenamiento terciario o fuera de lnea (copias de seguridad)

Discos magnticosEl nivel interno organiza el almacenamiento y el acceso a la BD en los discos magnticos atendiendo a su estructura. Un disco duro est constituido por un conjunto de discos magnticos (platos) insertados en un eje de rotacin Sobre cada una de las caras del disco se ubica una cabeza de lectura/escritura dotada de movimiento transversal. Cuando el disco est en funcionamiento, rota y con los cabezales es posible acceder a cualquier punto de cada una de las caras de los discos. Cada disco est compuesto por un conjunto de pistas concntricas que a su vez se dividen en sectores, los cuales representan la unidad mnima de almacenamiento (512 bytes) Para acceder a un sector es preciso indicar el cilindro, el n de sector en ese cilindro y el plato que lo alberga El cilindro est constituido por la i-ava pista de todos los platos. A nivel de SO puede utilizarse un mltiplo de sectores contiguos que se denomina bloque como unidad de E/S

12

Discos magnticos (cont.)Controlador de discos hace de interfaz entre el sistema informtico y el hardware concreto de la unidad de disco. Acepta comandos de alto nivel para leer o escribir un sector Inicia acciones tales como mover el brazo del disco a la pista adecuada y leer o escribirlos datos Calcula y aade checksums a cada sector para verificar que los datos se leen de nuevo correctamente Asegura la correcta escritura leyendo el sector despus de escribirlo Realiza la reubicacin de sectores defectuosos Permite conectar varios discos a una mquina Interfaces ATA, IDE, SCSI, Fibre Channel Las unidades de disco suelen disponer de una memoria cach para agilizar las transferencias entre disco y buses E/S

13

Tasa de transferencia: ATA-5: 66 MB/sg. SCSI-3: 40 MB/sg. Canal de fibra: 256 MB/sg.

RAID (Redundant Arrays of Independent Disks)Tcnicas de organizacin de disco que gestionan una gran cantidad de discos, proporcionando la imagen de un solo disco de: Gran capacidad y alta velocidad utilizando varios discos en paralelo, y Alta disponibilidad almacenando datos de forma redundante, de tal manera que los datos se pueden recuperar an cuando un disco falle El paralelismo en un sistema de disco tiene dos objetivos principales: Equilibrar la carga de varios accesos de pequeo tamao para incrementar las prestaciones Paralelizar accesos de gran tamao para reducir el tiempo de respuesta. Generalmente, se realiza a nivel de bloque, con n discos, el bloque i de un fichero va al disco (i mod n) + 1 Las peticiones de diferentes bloques se pueden ejecutar en paralelo si los bloques estn en discos distintos Una peticin de una secuencia grande de bloques puede utilizar todos los discos en paralelo Niveles de RAID: 0 a 6

14

Niveles de RAIDNivel 0: No redundancia Aplicaciones de alta velocidad donde no sea crtico la prdida de informacin Nivel 1: Buen comportamiento en escritura Discos espejo

15

Nivel 5: Paridad distribuida con bloques entrelazados

Eleccin de RAIDFactores a tener en cuenta Coste Prestaciones: Nmero de operaciones de E/S por segundo, y ancho de banda durante la utilizacin normal Prestaciones durante un fallo Prestaciones durante reconstruccin de disco que fall Incluido el tiempo que se tarda en reconstruir el disco que fall El nivel 1 proporciona unas prestaciones de escritura mucho mejores que el nivel 5 El nivel 5 requiere al menos 2 lecturas de bloque y dos escrituras de bloque para escribir un solo bloque, mientras que el nivel1 slo requiere dos escrituras de bloque El nivel1 es mejor para entornos de muchas actualizaciones, tales como discos de histricos (logs) El nivel 5 es preferible para aplicaciones con baja tasa de actualizacin y grandes cantidades de datos El nivel 1 es preferible para todas las dems aplicaciones.

16

Mtodo de acceso a la BDLa descripcin de la arquitectura de tres niveles culmina con la expresin de los datos a nivel interno en trminos de archivo, registro y campo almacenado. Un archivo se organiza lgicamente en pginas (8KB) que es la unidad de almacenamiento que utiliza el gestor de BD para operaciones de E/S y de bloqueo. Cada una de estas pginas, puede contener desde una fraccin de registro a varios registros dependiendo del tamao de pgina. A nivel de SO, cada una de estas pginas est integrada por varios fragmentos denominados bloques de SO. Un bloque est compuesto por uno o varios sectores de disco. Archivo almacenado Pgina 1Bloque 0 P1 P2 Pedro Mara Prez Garca P5

17

Pgina 2Bloque 3 Ana Sez Unidad de disco

Bloque 1 P3 P4 Pedro Mara Lucas Coz

Bloque 4

Sector 4

Sector 1

Sector 3

Sector 2

Mtodo de acceso a la BD (cont.)El mtodo de acceso a la BD describe de qu manera se transforma un registro almacenado, en una representacin fsica a nivel de almacenamiento secundario El acceso a los registros puede hacerse de dos formas: Secuencial o DirectaMtodo de acceso directo (recuperacin de registros) 1. Solicita pgina/s almacenada/s Gestor de Gestor de consultas consultas SGBD SGBD 6. Pginas solicitadas 2. Solicita bloques al SO Gestor de Gestor de disco del disco del SO SO 5. Bloques solicitados 3. Operacin de E/S al disco BD almacenada 4. Sectores solicitados

18

Gestor de Gestor de archivos del archivos del SGBD SGBD

Para insertar, actualizar y borrar, el gestor de archivos tendr que recuperar las pginas del archivo involucradas y operar con ellas para modificarlas o incluso aadir ms pginas.

Gestor de disco del SOLa mayora de los gestores interacta con el sistema de almacenamiento secundario a travs de los servicios proporcionados por el gestor del disco implementado por el SO El gestor del disco se encarga de: Organizar la informacin en trminos de conjuntos de bloques, lo que constituye un fichero Gestionar el espacio libre Adems proporciona los siguiente servicios: Crear / eliminar un fichero de SO Recuperar un bloque de un determinado archivo Aadir un bloque Reemplazar un bloque Eliminar un bloque

19

Gestor de archivos del SGBDSe encarga de trasladar las representaciones en trminos de campos, registros y archivos a representaciones en trminos de bloques y conjuntos de bloques comprensibles para el gestor de disco del SO La organizacin de los datos debe perseguir que el tiempo de recuperacin de los mismos se minimice Estos requisitos de flexibilidad y eficiencia descartan a los gestores de disco de SO y hace que los SGBD incorporen su gestor de archivos con las siguientes funciones: Crear un archivo almacenado, lo que conlleva asociar al archivo un conjunto de pginas e identificarlo (cabecera) y tambin eliminarlo. Recuperar, aadir, modificar y eliminar un registro Un fichero del SO puede contener ms de un archivo almacenado.

20

Los registros almacenados integrantes de un archivo

almacenado han de organizarse de forma que el gestor de archivos pueda recuperar todos ellos de forma secuencial, por tanto habr de conocer a travs de la cabecera la ubicacin del primer registro y cada registro debe proporcionar informacin para acceder al siguiente.

Representacin de la BD a nivel internoLa misin del nivel interno es traducir las estructuras del nivel conceptual a otras estructuras intermedias ms cercanas al almacenamiento real de los datos (nivel fsico) de forma que el n de operaciones E/S resulte mnimo. Error: cada tabla corresponde a un archivo. Generalmente los SGBD agrupan los registros del mismo conjunto de tems a nivel conceptual de manera que puedan recuperarse conjuntamente cuando se lea un bloque. El nivel interno est constituido por un conjunto de pginas en las que se van ubicando los registros. Si las pginas contienen registros del mismo tipo, se dice que el agrupamiento es intra-archivo. La ms frecuente y eficiente. Si las pginas ubican registros de distintas tablas, se denomina interarchivo. Es buena si se almacenan los datos de una entidad fuerte con sus registros asociados (pedidos con su detalle)

21

PginaPara que el gestor de archivos pueda localizar en qu pgina de la BD se encuentra el registro almacenado y la ubicacin dentro de la pgina, se utiliza la informacin que registra el RID (Record Identifier). El RID almacena el nmero de pgina en la que se encuentra el registro almacenado y un puntero a una posicin, dentro de un vector de direcciones de la pgina, que contiene la direccin de comienzo del registro almacenado en dicha pgina.

22

RID

Pg. offset

La cabecera de una pgina contiene, al menos: El nmero de registros El final del espacio libre de la pgina La localizacin y tamao de cada registro Los registros se pueden mover dentro de la pgina para mantenerlos contiguos sin espacio libre entre ellos; se debe actualizar la entrada de la cabecera. Pginas diferentes para tipos LOB (generalmente el contenido se almacena en pginas independientes de las pginas de datos)

Jerarqua del nivel internoEl nivel interno puede variar de un SGBD a otro. Generalmente, el nivel interno lo implementan con varios niveles de abstraccin y jerarquizan sus datos. Oracle: una BD consta de uno o varios espacios de tablas ( tablespaces) que se organizan en uno o varios ficheros del SO. Cada tablespace se divide en segmentos (de datos, de ndices, etc.) y cada segmento en extensiones y cada una de estas es en un conjunto de bloques continuos. Informix: se organiza lgicamente en dbspaces, tbspaces, extents y chunks SQL Server: particin, pginas y extensiones

23

No existe relacin directa archivo almacenado / fichero fsico ya que todos los conjuntos de pginas irn almacenados en uno o varios ficheros fsicos del SO. El nivel interno es el que se encarga de absorber esta diferencia.

Organizacin de registros en archivosEn montculos (HEAP): El registro se coloca en cualquier parte del archivo en el que haya suficiente espacio. Los registros no se ordenan. Generalmente hay un archivo por relacin (tabla). Organizacin secuencial: Los registros se guardan en orden secuencial segn el valor de la clave de bsqueda de cada uno. Organizacin asociativa (HASH): Se calcula una funcin de asociacin (hash) para algn atributo de cada registro. El resultado de la funcin de asociacin especifica el bloque del archivo en el que se debe colocar el registro.

24

Organizacin secuencialLos registros se almacenan manera secuencial, en base al valor de la clave de bsqueda de cada registro. Estos se vinculan mediante punteros, lo que agiliza la bsqueda. Acceder a un registro determinado requiere pasar obligatoriamente por todos los registros que le preceden Tiempo de consulta: O(n) Problema si hay muchos registros!!!

25

CLAVE: nombre

Organizacin secuencial (cont.)Borrado: se utiliza la cadena de punteros para reorganizar los registros del bloque Insercin (imagen): se localiza la posicin donde se inserta el registro Si hay espacio libre se inserta all Sino hay espacio libre, se inserta el registro en un bloque de desbordamiento En cualquier caso, se debe actualizar la cadena de punteros Se necesita reorganizar el fichero de vez en cuando para recuperar el orden secuencial Secuencial Poco eficiente

26

Se requieren estructuras adicionales que aceleren las bsquedas y disminuyan los bloques de disco a transferir.

Consideraciones previasNinguna de las tcnicas de direccionamiento es la mejor en trminos absolutos Evaluacin de las estructuras de datos utilizada para agilizar las bsquedas se realizan en base a: El tiempo de acceso a los datos, medido en nmero de registros accedidos bajo dos condiciones: Bsqueda por valor de clave Bsqueda por rango (intervalo) en la clave Nmero de accesos a disco en operaciones de insercin y borrado de datos El espacio de almacenamiento que ocupan respecto a la informacin que indexa.

27

IndexacinMecanismos de indexacin empleados para acelerar el acceso a los datos deseados. Por ejemplo, el ndice de un libro Clave de bsqueda atributo, del conjunto de atributos, empleado para buscar registros en un archivo. Un archivo de ndices consta de registros (denominados entradas de ndice) de la formaCLAVE DE BSQUEDA PUNTERO

28

Los archivos de ndices generalmente son ms pequeos que el archivo original Dos clases bsicas de ndices: ndices ordenados: las claves de bsqueda se almacenan de forma ordenada ndices asociativos: las claves de bsqueda estn distribuidas uniformemente en cajones, empleando una funcin de asociacin.

ndices ordenadosLas entradas de ndices se almacenan ordenadas sobre el valor de la clave de bsqueda. Por ejemplo, el nombre de la sucursal. ndice primario: en un archivo ordenado secuencialmente, es el ndice cuya clave de bsqueda determina el orden secuencial del archivo. Tambin denominado ndice con agrupacin (cluster) La clave de bsqueda de un ndice primario es generalmente, pero no necesariamente, la clave primaria. Solo puede haber uno por relacin ndice secundario: un ndice cuya clave de bsqueda determina un orden diferente del orden secuencial del archivo. Tambin llamado ndice sin agrupacin. Archivo secuencial indexado (ISAM): archivo secuencial ordenado con un ndice primario.

29

ndice densondice denso Registro del ndice que aparece por cada valor de la clave de bsqueda del archivo.ndice primario denso Fichero secuencial por campo nombre

30

RID

Clave de bsqueda

ndice no densondice disperso: slo contiene registros del ndice para algunos valores de la clave de bsqueda. Aplicable cuando los registros estn ordenados secuencialmente sobre la clave de bsqueda (ndices primarios) Para localizar un registro con valor K de la clave de bsqueda: Encontrar el registro del ndice con mayor valor de clave de bsqueda < K Bsqueda secuencial del archivo, empezando por el registro al que apunta el registro del ndice Menos espacio y menores costes de mantenimiento para las inserciones y los borrados. Generalmente ms lento, para localizar registros, que el ndice denso.

31

Ejemplo de ndice dispersondice primario no denso

32

Se alcanza buen equilibrio estableciendo un ndice disperso con una entrada del ndice por cada bloque en el archivo, que se corresponda con el menor valor de la clave de bsqueda en el bloque.

ndice multinivelAunque se usen ndices dispersos, puede que el tamao del mismo sea muy grande para cargarlo en memoria principal, lo que har que haya que almacenarlo en disco y aumentar las operaciones de E/S. Para reducir el nmero de accesos a disco, se puede tratar el ndice como un archivo secuencial y construir un ndice disperso sobre el ndice con agrupacin. ndice externo un ndice disperso de ndice primario ndice interno el archivo del ndice primario Si incluso el ndice externo es demasiado grande para cargarse en memoria principal, siempre se puede crear otro nivel de ndice. Reducen el nmero de accesos a disco cuando se busca por la clave, reducindose a n accesos a disco ( n niveles de jerarqua) pero Al insertar o borrar del archivo, se deben actualizar los ndices a todos los niveles. Algunos diseadores dejan espacio en cada uno de los bloques para insertar nuevas entradas, ndices multinivel dinmicos, que generalmente se implementan mediante rboles B y B+

33

ndices multinivel (Cont.)

34

ndice disperso ndice denso

Actualizacin de ndices: borradoSi el registro borrado era el nico registro del archivo con su valor de clave de bsqueda concreto, la clave de bsqueda se borra tambin del ndice. Algoritmo de borrado del ndice de un solo nivel: ndices densos el borrado de la clave de bsqueda es similar al borrado del registro del archivo ndices dispersos Si el ndice no contiene un registro ndice con el valor de la clave de bsqueda, no hay nada que hacer. Si existe una entrada para la clave de bsqueda en el ndice se borra, reemplazando la entrada en el ndice con el siguiente valor de la clave de bsqueda en el archivo (ordenado por clave de bsqueda). Si el valor de la siguiente clave de bsqueda tiene una entrada del ndice, se borra la entrada en vez de reemplazarla.

35

Actualizacin de ndice: insercinInsercin de ndices de un solo nivel: Realizar una bsqueda empleando el valor de la clave de bsqueda que aparece en el registro a insertar. ndices densos si el valor de la clave de bsqueda no aparece en el ndice, insertarlo. ndices dispersos si el ndice almacena una entrada por cada bloque del archivo, no es necesario hacer ningn cambio al ndice, a menos que se cree un nuevo bloque. En este caso, se inserta en el ndice el primer valor de la clave de bsqueda en el nuevo bloque. Los algoritmos de inserciones multinivel (as como en el borrado) son una extensin de los algoritmos de un solo nivel

36

ndices secundariosFrecuentemente, se quieren encontrar todos los registros cuyos valores en un cierto campo (que no es la clave de bsqueda del ndice primario) cumplen alguna condicin. Ejemplo: encontrar todas las cuentas con un determinado saldo o rango de saldos Se puede tener un ndice secundario con un registro del ndice por cada valor de la clave de bsqueda; el registro del ndice apunta a un cajn que contiene punteros a todos los registros actuales, con ese valor particular de clave de bsqueda.

37

ndices primarios y secundariosLos ndices ofrecen importantes ventajas en la bsqueda de registros. Cuando se modifica un archivo, se debe actualizar cada ndice del Actualizar los ndices implica sobrecargas en la archivo modificacin de la base de datos. Los ndices secundarios han de ser densos con una entrada en el ndice por cada valor de la clave de bsqueda y un puntero a cada registro del archivo. La bsqueda secuencial empleando ndices primarios es eficiente, pero utilizando un ndice secundario es costosa, pues cada acceso a un registro puede requerir un nuevo bloque del disco (no ordenado secuencialmente). Los ndices multinivel reducen el nmero de accesos a disco cuando se busca por la clave, pero es costoso su mantenimiento. Algunos diseadores dejan espacio en cada uno de los bloques para insertar nuevas entradas, lo que denominan ndices multinivel dinmicos, que generalmente se implementan mediante rboles B y B+

38

ndices B+Inconvenientes de los archivos secuenciales indexados: El rendimiento baja cuando el archivo crece, dado que se crean muchos bloques de desbordamiento. Es necesario reorganizar peridicamente todo el archivo. ndices B+ Ventajas Se reorganiza automticamente por s mismo con pequeos cambios locales, a pesar de las inserciones y los borrados. No es necesario reorganizar todo el archivo para mantener el rendimiento. Inconvenientes inserciones extras sobrecarga de borrados Gasto de espacio en disco mayor. Las ventajas de los rboles B+ superan a los inconvenientes, por lo que se emplean ampliamente. Los ndices de rbol B+ son una alternativa a los archivos secuenciales indexados.

39

ndices B+ (cont)Un rbol B+ es un rbol con raz que satisface las siguientes propiedades: Todos los caminos, desde la raz a las hojas, tienen la misma longitud Cada nodo que no es ni raz ni hoja, tiene entre [n/2] y n hijos. Un nodo hoja tiene entre [(n1)/2] y n1 valores Casos especiales: Si la raz no es una hoja, tiene al menos 2 hijos. Si la raz es una hoja (es decir, no hay otros nodos en el rbol), puede tener entre 0 y (n1) valores. Dado que las conexiones entre nodos se hacen mediante punteros, los bloques lgicamentecercanos no necesitan estar fsicamente prximos.

40

Estructura de un nodo B+Nodo

41

Ki son los valores de la clave de bsqueda Pi son los punteros a los hijos (para nodos no hoja) o a los registros o cajones de registros (para nodos hoja). En un nodo las claves de bsqueda estn ordenadas K1 < K2 < K3 < . . . < Kn1

Nodos hoja en rboles B+Para i= 1, 2, . . ., n1, el puntero Pi apunta a un registro del archivo con valor de clave de bsqueda Ki, o a un cajn de punteros a los registros del archivo con valor de clave de bsqueda Ki. Slo es necesaria una estructura de cajones si la clave de bsqueda no es una clave primaria. Si Li, Lj son nodos hoja e i < j, los valores de clave de bsqueda de Li son menores que los de Lj Pn apunta al siguiente nodo hoja, ordenado por clave de bsqueda. Permite el encadenamiento secuencial del archivo

42

RID

Nodos no hoja en rboles B+Los nodos que no son hoja forman un ndice disperso multinivel sobre los nodos hoja. Para un nodo no hoja con n punteros: Todas las claves de bsqueda en el subrbol al que apunta P1 son menores que K1 Para 2 i n 1, todas las claves de bsqueda en el subrbol al que apunta Pi, tienen valores mayores o iguales que Ki1 y menores que Kn1

43

Ejemplos B+B+-tree para archivo cuentas (n = 3)

44

B+-tree para archivo cuentas (n = 5)

Los nodos hoja deben tener entre 2 y 4 valores ( (n1)/2 y (n 1), con n= 5 ). Los nodos que no son hoja, excepto la raz, deben tener entre 3 y 5 hijos (n/2 y n ) La raz debe tener al menos 2 hijos.

rboles B+: consultaConsulta: Procesar una consulta es recorrer el rbol, desde la raz hasta algn nodo hoja. Si hay K valores de clave de bsqueda en el archivo, el camino no es mayor que logn/2(K). Un nodo es generalmente del mismo tamao que un bloque de disco, tpicamente 4 KB, y n suele estar entorno a 100 (40 bytes por entrada de ndice (clave (32 bytes) + puntero (8 bytes))). Con 1 milln de valores de clave de bsqueda y n = 100, como mximo log50(1.000.000) = 4 nodos son accedidos en una bsqueda. Un rbol B+ generalmente es bajo y ancho, a diferencia de los binarios Log2(1.000.000) = 20 nodos

45

rboles B+: insercinEncontrar el nodo hoja en que aparecera el valor de la clave de bsqueda Si el valor de la clave de bsqueda ya est en el nodo hoja, se aade el registro al archivo y, si es necesario, se inserta un puntero en el cajn. Si el valor de la clave de bsqueda no est all, se aade el registro al archivo principal y, si es necesario, se crea un cajn. Entonces: Si hay espacio en el nodo hoja, insertar el par (valor de la clave, puntero) De lo contrario, dividir el nodo. Tomar los n pares (valor de la clave, puntero) de forma ordenada (incluyendo el que se est insertando). Situar el primer n/2 en el nodo original y el resto en un nodo nuevo. Sea p el nuevo nodo, y sea k el menor valor de la clave en p. Insertar (k, p) en el padre del nodo que se est dividiendo. Si el padre est lleno, dividirlo y propagar la divisin hacia arriba. La divisin de los nodos se lleva a cabo hacia arriba, hasta encontrar un nodo que no est lleno. En el peor de los casos, el nodo raz se puede dividir incrementando la altura del rbol en 1.

46

Ejemplo insercin en B+B+ antes y despus de aadir Cadiz

47

rboles B+ : borradoEncontrar el registro a borrar y eliminarlo del archivo principal y del cajn (si est presente) Eliminar (valor de la clave de bsqueda y puntero) del nodo hoja si no hay ningn cajn, o si se ha quedado vaco. Si el nodo tiene demasiadas pocas entradas debido a la eliminacin y las entradas en el nodo y un hermano encajan en un solo nodo, entonces Insertar todos los valores de claves de bsqueda de los dos nodos en un solo nodo (el de la izquierda) y borrar el otro. Borrar el par (Ki1, Pi),donde Pi es el puntero al nodo borrado, desde su padre, empleando recursivamente el procedimiento anterior.

48

Ejemplo de borrado en B+Borrado de Pamplona

49

Organizacin de archivos con rboles B+El inconveniente de la organizacin de archivos secuenciales es su degradacin en el rendimiento cuando el fichero crece. La solucin: Uso de rboles B+ para almacenar tanto los ndices como los datos. Los nodos hoja en una organizacin de archivos de rbol B+ almacenan registros, en vez de punteros. Dado que los registros son ms grandes que los punteros, el nmero mximo de registros que se pueden almacenar en un nodo hoja es menor que el nmero de punteros en un nodo no hoja. Sin embargo se requiere que los nodos hoja estn llenos hasta la mitad. La insercin y el borrado de registros (de datos) se gestionan de la misma manera que la insercin y el borrado de las entradas en un ndice de rbol B+.

50

Ejemplo de rbol B+ de datos

51

Es importante la buena utilizacin del espacio, dado que los registros emplean ms espacio que los punteros. Para mejorar la utilizacin del espacio se puede implicar ms nodos hermanos en la redistribucin durante las divisiones y las mezclas y no solo al de la izquierda.

ndices sobre cadenas de caracteresProblemas: Las cadenas pueden ser de longitud variable Y pueden ser largas, lo que produce rbol con muchos niveles Solucin: trabajar con compresin del prefijo Los nodos internos trabajan con prefijos y no con la clave completa Mantener suficientes caracteres para crear un rbol eficiente E.j. Silas y Silberston pueden separarse por Silb

52

Archivo de ndices BSimilar a B+, pero elimina el almacenamiento redundante de los valores de la clave de bsqueda. Esto optimiza el espacio de almacenamiento pero dado que las claves de bsqueda no aparecen en los nodos intermedios, es necesario incluir un campo adicional para un puntero por cada clave de bsqueda de un nodo interno.

53

rbol B

rbol B+

Archivo de ndices B (cont.)Ventajas de los ndices de rbol B: Pueden usar menos nodos que el correspondiente al rbol B+. Algunas veces es posible encontrar el valor de la clave de bsqueda antes de alcanzar el nodo hoja. Inconvenientes de los ndices de rbol B: Slo se encuentran previamente pequeas fracciones, de entre todos los valores de las claves de bsqueda Los nodos no hoja son ms grandes, por lo que se reduce el grado de salida. De este modo, los rboles B tienen generalmente mayor profundidad que los correspondientes rboles B+ La insercin y el borrado son ms complicados que en los rboles B+ La implementacin es ms costosa que los rboles B+. Generalmente, las ventajas de los rboles B no superan los inconvenientes.

54

ndices sobre varias clavesConsulta: select numero_cuenta from cuentas where oficina = Pamplona and saldo = 1000 Posibles estrategias para procesar la consulta: 1. Usar el ndice sobre nombre de oficina para localizar los registros de Pamplona y comprobar las de saldo = 1000. 2. Usar el ndice sobre saldo= 1000 y luego oficina=Pamplona. 3. Usar independientemente ambos ndices y tomar la interseccin. La opcin 3 es la que usa ambos ndices pero pudiera ser una mala opcin si hubiera muchos registros en ambos consultas independientes y luego la interseccin fuera de pocos registros. Si la consulta es frecuente crear ndices por ambos campos. Solucin: ndices sobre claves compuestas Mapas de bits ndices R (extensin de B+ que contempla varias dimensiones)

55

Claves de bsqueda duplicadasLa creacin de cajones de punteros en los nodos hoja para anotar los registros que contienen ese valor de clave plantea complicaciones en rboles B+. Alternativas: Si los cajones se almacenan en pginas separadas es necesario ms operaciones E/S (mala idea) Anotar la lista de punteros con cada clave: Requiere cdigo extra para manejar listas Mayor coste para el borrado de un registro No supone mayor coste en consultas Gasto de espacio adicional bajo Hacer una clave nica con el valor de clave y un atributo nico adicional Almacenamiento extra para las claves Codificacin sencilla para inserciones y borrados Ampliamente utilizado

56

SQL Server 2005Tabla del catlogo: sysindexes

57

ndice cluster

ndice no cluster

SQL Server 2005Tabla del catlogo: sysindexes

58

Las pginas Mapa de asignacin de ndices (IAM, Index Allocation Map) asignan las extensiones de un archivo de la base de datos utilizadas por un montn o por un ndice

Heap

Asociacin estticaLa asociacin permite localizar registros sin utilizar la estructura de ndices Un cajn es una unidad de almacenamiento que contiene uno o ms registros (generalmente un cajn es un bloque de disco). En una organizacin de archivos asociativa se obtiene el cajn de un registro directamente desde su valor de clave de bsqueda, empleando una funcin de asociacin. La funcin de asociacin h es una funcin desde el conjunto de todos los valores de claves de bsqueda K, hasta el conjunto de todas las direcciones de cajones B. La funcin de asociacin se emplea para localizar registros para accesos, inserciones y borrados. Los registros con diferentes valores de claves de bsqueda pueden asociarse al mismo cajn; de este modo, para localizar un registro, se ha de recorrer secuencialmente el cajn entero. Tcnica eficiente para la bsqueda por clave pero no por rangos.

59

Ejemplo de organizacin de fichero Hashrelacin cuenta, utilizando nombre-sucursal como clave

60

Hay 10 cajones La representacin binaria del carcter i-simo se asume que sea el entero i. La funcin de asociacin devuelve la suma de las representaciones binarias de los caracteres mdulo 10 Por ejemplo, h(Navacerrada) = 5 h(Ronda) = 3 h(Galapagar) = 3

Funciones HashUna funcin hash mala es aquella que asocia todos los valores de las claves de bsqueda al mismo cajn; esto hace que el tiempo de acceso sea proporcional al nmero de valores de claves de bsqueda en el archivo. La funcin de asociacin ideal debe ser uniforme, es decir, que asigne a cada cajn el mismo nmero de valores de claves de bsqueda, desde el conjunto de todos los valores posibles. La funcin de asociacin ideal es random; as cada cajn tendr asignado el mismo nmero de registros, independientemente de la distribucin real de los valores de las claves de bsqueda en el archivo. Las funciones de asociacin tpicas realizan clculos sobre la representacin binaria interna de la clave de bsqueda.

61

Gestin de desbordamiento de cajonesEl desbordamiento de cajones puede producirse por Insuficientes cajones Desviacin en la distribucin de los registros. Esto puede tener lugar por dos razones: mltiples registros tienen el mismo valor de clave de bsqueda la funcin de asociacin elegida produce una distribucin no uniforme de los valores de las claves Aunque se puede reducir la probabilidad de desbordamiento de cajones, no se puede eliminar y se gestiona empleando cajones de desbordamiento.

62

Gestin de desbordamiento de cajones (2)Cadena de desbordamiento los cajones de desbordamiento de un determinado cajn se encadenan juntos en una lista enlazada. Se denomina asociacin cerrada. Una alternativa, denominada asociacin abierta, que no emplea cajones de desbordamiento, no es adecuada para aplicaciones de bases de datos. Estas generalmente utilizan el siguiente cajn disponible, lo que presenta problemas tanto en la insercin como en el borrado. .

63

ndices asociativosLa asociacin no slo se puede emplear en la organizacin de archivos, sino tambin para la creacin de estructuras de ndices. Un ndice asociativo organiza las claves de bsqueda, con sus punteros de registros asociados, en una estructura de archivos asociativa.

64

ndice asociativo de la clave de bsqueda nmero de cuenta

Deficiencias de la asociacin estticaEn la asociacin esttica la funcin h asocia valores de claves de bsqueda a un determinado conjunto B, de direcciones de cajones. Las bases de datos crecen con el tiempo. Si el nmero inicial de cajones es demasiado pequeo, disminuir el rendimiento debido al nmero de cajones de desbordamiento que se requerirn. Si se anticipa el tamao del archivo para algn momento del futuro, se desperdiciar inicialmente espacio. Si disminuye la base de datos, nuevamente se desperdiciar espacio. Una opcin es la reorganizacin peridica del archivo con una nueva funcin de asociacin, pero es muy costoso. Estos problemas se pueden evitar empleando tcnicas que permitan que el nmero de cajones se modifique dinmicamente.

65

Comparacin de la indexacin ordenada y la asociacinRespecto a las consultas La asociacin es mejor cuando se consulta por clave (el tiempo es uniforme y no proporcional al logaritmo del n de valores). Los B+ son ms eficientes para las consultas por rangos. Generalmente, los SGBD implementan la organizacin de los archivos con indexacin ordenada (B+) y utilizan tcnicas de asociacin para los archivos temporales creados durante el procesamiento de las consultas.

66

Mapas de bitsSon un tipo de ndice especializado para la consulta sencilla sobre varias claves, aunque cada ndice de mapa de bits se construya para una nica clave El mapa de bits es un array de bits. Un mapa de bits sobre el atributo A de la relacin r es un array con tantas posiciones como tuplas, y un bit a 1 para aquellas posiciones donde el atributo A tome un determinado valor.

67

Los registros deben estar numerados. La insercin/borrado no debe afectar a la numeracinMapa de bits Nombre Juan Diana Mara Pedro Natalia Sexo M F F M F Direccin Santander Pamplona Madrid Barcelona Santander Nivel_in gresos N1 N2 N1 N4 n3 Nivel=N1 Nivel=N2 Nivel=N3 Nivel=N4 10100 01000 00001 00010 Sexo=m Sexo=f 10010 01101

Definicin de ndices en SQLCrear un ndice create index on () E.j.: create index b-index on sucursal(nombre) Usar create unique index para especificar que la clave de bsqueda es una clave candidata Se produce el mismo efecto si se utiliza la restriccin de integridad unique Usar create clustered index para especificar que el orden fsico de las filas es el mismo que el orden indizado de las filas y el nivel inferior (hojas) del ndice agrupado contiene las filas de datos reales Borrar un ndice drop index

68