Tema 10. Indexacion ´ y asociacion ´ Juan Ignacio Rodr´ıguez de Leon ´ Resumen ´ Conceptos b´asicos. Indices ordenados. Archivos de ´ındices de a´ rbol B+. Archivos de ´ındices de a´ rbol B. Asociacion ´ est´atica. Asociacion ´ din´amica. Comparacion ´ entre la indexacion ´ ordenada y la asociacion. ´ Definicion ´ de ´ındices en SQL. Accesos multiclave.

´ Indice 1. Conceptos b´asicos

3

´ 2. Indices ordenados ´ 2.1. Indice primario . . . . . . . . . . . ´ 2.1.1. Indices densos y dispersos . ´ 2.1.2. Indices multinivel . . . . . 2.1.3. Actualizacion ´ del ´ındice . .

4 4 4 5 5

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

´ 3. Indices secundarios

5

4. Archivos del ´ındices de a´ rbol B+ 4.1. Estructura de a´ rbol B+ . . . . . . . . . . . . . . . 4.1.1. Consultas con a´ rboles B+ . . . . . . . . . 4.1.2. Actualizaciones en a´ rboles B+ . . . . . . . 4.1.3. Organizacion ´ de archivos con a´ rboles B+ 4.2. Archivos de ´ındices de a´ rbol B . . . . . . . . . .

. . . . .

6 6 6 7 7 7

. . . .

8 8 8 9 9

6. Asociacion ´ din´amica 6.1. Asociacion ´ extensible . . . . . . . . . . . . . . . . . . . . . . .

10 10

7. Comparacion ´ de la indexacion ´ ordenada y la asociacion ´

11

5. Asociacion ´ est´atica 5.1. Organizacion ´ de archivos por asociacion ´ 5.1.1. Funciones de asociacion ´ . . . . . 5.2. Gestion ´ de desbordamientos de cajones ´ 5.3. Indices asociativos . . . . . . . . . . . .

1

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

´ INDICE

2

8. Definicion ´ de ´ındices en SQL 9. Accesos multiclave 9.1. Archivos en ret´ıcula . . . . . . . . . . . . . . . . . . . ´ 9.2. Indices de mapas de bits . . . . . . . . . . . . . . . . 9.2.1. Estructura de los ´ındices de mapas de bits . 9.2.2. Implementacion ´ eficiente de las operaciones pas de bits . . . . . . . . . . . . . . . . . . . .

11

. . . . . . de . .

. . . . . . . . . ma. . .

12 12 12 13 13

1

1.

´ CONCEPTOS BASICOS

3

Conceptos b´asicos

Un ´ındice para un archivo del sistema funciona como el ´ındice de un libro. Si se va a buscar un tema (especificado por una palabra o una frase), se puede buscar en el ´ındice las p´aginas en las que aparece y despu´es leer esas p´aginas para encontrar la informacion ´ que estamos buscando. Las palabras de ´ındice est´an ordenadas, lo que hace f´acil las busquedas. Adem´as, el ´ ´ındice es mucho m´as pequeno ˜ que el libro, con lo que se reduce el esfuerzo necesario para encontrar las palabras en cuestion. ´ Hay dos tipos b´asicos de ´ındices: ´ Indices ordenados Basados en una disposicion ´ ordenada de los valores. ´ Indices asociativos (hash indices) Basados en una distribucion ´ uniforme de los valores a trav´es de una serie de cajones (buckets). El valor asignado a cada cajon ´ est´a determinado por una funcion, ´ llamada funcion ´ de asociacion ´ (hash function). Se considerar´an varias t´ecnicas de indexacion ´ y asociacion. ´ Ninguna de ellas es la mejor. Sin embargo, cada t´ecnica es la m´as apropiada para una aplicacion ´ espec´ıfica de bases de datos. Cada t´ecnica debe ser valorada segun ´ los siguientes criterios: Tipos de acceso Tipos de acceso que se soportan eficazmente. Estos tipos podr´ıan incluir la busqueda de registros con un valor concreto en un ´ atributo, o buscar los registros cuyos atributos contengan valores en un rango especificado. Tiempo de acceso Tiempo que se tarda en buscar un determinado elemento de datos, o conjunto de elementos, usando la t´ecnica en cuestion. ´ Tiempo de insercion ´ Tiempo empleado en insertar un nuevo elemento de datos. Incluye el tiempo utilizado en buscar el lugar apropiado donde insertar el nuevo elemento de datos, as´ı como el empleado en actualizar la estructura del ´ındice. Tiempo de borrado Tiempo empleado en borrar un elemento de datos. Incluye el tiempo utilizado en buscar el elemento a borrar, as´ı como el tiempo empleado en actualizar la estructura del ´ındice. Espacio adicional requerido El espacio ocupado por la estructura del ´ındice. Como normalmente suele ser moderada, es razonable sacrificar el espacio para alcanzar un mejor rendimiento. Los atributos o conjunto de atributos usados para buscar en un archivo se llaman claves de busqueda. ´ Normalmente existir´an varias claves de busqueda. ´

2

´ INDICES ORDENADOS

2.

4

´ Indices ordenados

Si el archivo que contiene los registros est´a ordenado secuencialmente, el ´ındice cuya clave de busqueda especifica el orden secuencial del archivo ´ es el ´ındice primario. (El t´ermino ´ındice primario se emplea algunas veces para hacer alusion ´ a un ´ındice segun ´ una clave primaria. Sin embargo, tal uso no es normal y deber´ıa evitarse.) Los ´ındices primarios tambi´en se llaman ´ındices con agrupaci´on (clustering indices). La clave de busqueda de un ´ındice primario es normalmente – ´ aunque no obligatoriamente– la clave primaria. Los ´ındices cuyas claves de busqueda especifican un orden diferente del orden secuencial del archivo ´ se llaman ´ındices secundarios o ´ındices sin agrupaci´on (non clustering indices).

2.1.

´ Indice primario

En este apartado se asume que todos los archivos est´an ordenados secuencialmente segun Estos archivos se llaman ´ alguna clave de busqueda. ´ archivos secuenciales indexados. Se emplean cuando las operaciones m´as habituales son el procesamiento secuencial el acceso directo a sus registros. 2.1.1.

´ Indices densos y dispersos

Un registro ´ındice o entrada del ´ındice consiste en un valor de la clave de busqueda y punteros a uno o m´as registros con ese valor de la clave de ´ busqueda. El puntero a un registro consiste en el identificador de un bloque ´ de disco y un desplazamiento en el mismo, para identificar el registro dentro del bloque. Hay dos clases de ´ındices ordenados que se pueden emplear: ´ Indice denso Existe un registro ´ındice por cada valor de la clave de busque´ da. El registro ´ındice contiene el valor de la clave y un puntero al primer registro con ese valor de la clave de busqueda. El resto de ´ registros se almacenan consecutivamente, dado que los registros se ordenan sobre la misma clave de busqueda. ´ ´ Indice disperso Solo ´ se crea un registro ´ındice para algunos de los valores. Para localizar un registro se busca la entrada del ´ındice con el valor m´as grande que sea menor o igual que el valor que se est´a buscando y despu´es se realiza una busqueda secuencial. ´ Generalmente es m´as r´apido localizar un registro mediante un ´ındice denso que mediante uno disperso. Sin embargo, los ´ındices dispersos utilizan menos espacio y requieren menos mantenimiento para las inserciones y borrados. Existe un buen compromiso que consiste en tener un ´ındice disperso con una entrada del ´ındice por cada bloque. El rendimiento es bueno porque

3

´ INDICES SECUNDARIOS

5

el mayor coste de procesar una peticion ´ es el tiempo empleado en traer un bloque de disco a la memoria. 2.1.2.

´ Indices multinivel

Si un ´ındice es lo bastante pequeno ˜ como para guardarlo en la memoria principal, el tiempo de busqueda para encontrar una entrada ser´a breve. ´ Sin embargo, si el ´ındice es tan grande que se debe guardar en disco, buscar una entrada implicar´a leer varios bloques de disco, por lo que se convierte en una operacion ´ m´as lenta. Para resolver este problema se trata el ´ındice como si fuese un archivo secuencial y se construye un ´ındice disperso sobre el ´ındice primario. Usando los dos niveles de indexacion ´ y con el ´ındice m´as externo en memoria principal, podemos reducir el numero de accesos a disco. Si al archivo ´ es extremadamente grande se podr´ıa repetir este proceso tantas veces como fuese necesario. Los ´ındices con dos o m´as niveles se llaman ´ındices multinivel. Cada nivel de ´ındice se podr´ıa corresponder con una unidad del almacenamiento f´ısico. As´ı, podr´ıamos tener ´ındices a nivel de pista, cilindro o disco. 2.1.3.

Actualizacion ´ del ´ındice

Sin importar el tipo de ´ındice que se est´e usando, los ´ındices se deben actualizar siempre que se inserte o borre un registro del archivo. los algoritmos para actualizar ´ındices de un solo nivel, ante una operacion ´ de insercion ´ o borrado, son relativamente sencillos. Los algoritmos para los ´ındices multinivel se extienden a partir de estos.

3.

´ Indices secundarios

Un ´ındice secundario sobre una clave candidata es como un ´ındice denso primario, excepto porque los registros apuntados por los sucesivos valores del ´ındice no est´an almacenados secuencialmente; esto conlleva que est´an estructurados de forma diferente. Un ´ındice secundario debe contener punteros a todos los registros (ya que no puede contar con realizar una busqueda ´ secuencial). Se puede usar un nivel adicional de indireccion; los punteros ´ de estos ´ındices no apuntan directamente al archivo, sino que apuntan a un cajon ´ que contiene punteros al archivo. Dado que el orden de la clave secundario y el orden f´ısico de los registros difieren, si se intenta examinar el archivo secuencialmente por el orden de la clave secundaria, es muy probable que la lectura de cada bloque suponga la lectura de un nuevo bloque del disco. Los ´ındices secundarios mejoran el rendimiento de las consultas que emplean claves diferentes de la clave de busqueda del ´ındice primario, sin ´

4

´ ´ ARCHIVOS DEL INDICES DE ARBOL B+

6

embargo, implican aumentar el tiempo al modificar (inserciones o actualizaciones) la base de datos.

4.

Archivos del ´ındices de a´ rbol B+

Un ´ındice de a´ rbol B+ toma la forma de un a´ rbol equilibrado donde los caminos de la ra´ız a cada hoja del a´ rbol son de la misma longitud. Cada nodo que no es una hoja tiene entre n/2 y n hijos, donde n est´a fijo para cada a´ rbol en particular.

4.1.

Estructura de a´ rbol B+

Un ´ındice de a´ rbol B+ es un ´ındice multinivel, pero con una estructura diferente. Puede contener hasta n − 1 claves de busqueda K1 , K2 , . . . , Kn−1 ´ y n punteros P1 , P2 , . . . , Pn , estando ordenados los valores de la clave de busqueda. ´ La estructura de los nodos hoja es la siguiente: para i = 1, 2, . . . , n − 1 el puntero Pi apunta o bien a un registro del archivo con valor de la clave de busqueda Ki , o bien a un cajon ´ ´ de punteros, cada uno de los cuales apunta a un registro del archivo con valor de la clave de busqueda Ki . Cada hoja ´ puede guardar entre (n − 1)/2 y n − 1 valores, y los rangos de los valores en cada hoja no se solapan. As´ı, si Li y L j son nodos hoja e i < j , entonces cada valor de la clave de busqueda en Li es menor que cada valor de L j . ´ El puntero Pn se usa para encadenar juntos los nodos hoja en el orden de la clave de busqueda. ´ Los nodos internos del a´ rbol B+ forman un ´ındice multinivel sobre los nodos hoja. La estructura es la misma que la de los nodos hoja, excepto que todos los punteros son punteros a nodos del a´ rbol. El numero de punteros ´ de un nodo se llama grado de salida. Solo ´ en la ra´ız no es obligatorio que se mantenga un m´ınimo de n/2 punteros. Un requisito de los a´ rboles B+ es que la longitud de cada camino desde la ra´ız a cada nodo hoja sea la misma, es decir, ha de estar equilibrado. 4.1.1.

Consultas con a´ rboles B+

Supongamos que se desea encontrar todos los registros cuyo valor de la clave de busqueda sea K. Primero se examina el nodo ra´ız para buscar ´ el menor valor de la clave de busqueda mayor que K. Si, por ejemplo, este ´ valor es Ki , se sigue el puntero Pi . Se realiza la misma operacion ´ hasta llegar a un nodo hoja, cuyo puntero apunta al registro o cajon ´ deseado.

4

´ ´ ARCHIVOS DEL INDICES DE ARBOL B+

4.1.2.

7

Actualizaciones en a´ rboles B+

El borrado y la insercion ´ son m´as complicados, ya que podr´ıa ser necesario dividir un nodo que resultara demasiado grande, o combinar nodos, adem´as de mantener el equilibrio. Suponiendo que los nodos no son ni demasiados grandes ni demasiados pequenos, el problema de borrados e insercion ˜ ´ se reduce a la misma t´ecnica de la busqueda. ´ Si es necesario dividir, se inserta el nuevo nodo dentro del padre del nodo que hay que dividir. Si esta insercion ´ produce otra division, ´ procedemos recursivamente. Para borrar un nodo hoja se tiene que borrar el puntero que le llega desde su padre. Si el nodo padre queda pequeno, ˜ se busca el nodo hermano y si tiene sitio se fundan los dos nodos. No siempre es posible fundir nodos. La solucion ´ es redistribuir los punteros. 4.1.3.

Organizacion ´ de archivos con a´ rboles B+

El inconveniente de la organizacion ´ de archivos secuenciales de ´ındices es la degradacion ´ del rendimiento segun ´ crece el archivo. Se resuelve esta degradacion ´ mediante el uso de ´ındices de a´ rbol B+ en el archivo. En la organizacion ´ de archivos con a´ rboles B+ , los nodos hoja del a´ rbol almacenan registros en vez de punteros. Ya que los registros son m´as grandes que los punteros, el numero m´aximo de registros que se pueden almacenar ´ en un nodo hoja es menor que el numero de punteros, aunque todav´ıa se ´ requiere que los nodos hojas est´e llenos al menos hasta la mitad. La insercion ´ y borrado se trata igual que un ´ındice de a´ rbol B+ .

4.2.

Archivos de ´ındices de a´ rbol B

Son similares al a´ rbol B+ , salvo que un a´ rbol B elimina el almacenamiento redundante de los valores de la clave de busqueda. Ya que e´ stas no est´an ´ repetidas, ser´ıa posible almacenar el ´ındice empleando menos nodos del a´ rbol que con el a´ rbol B+ . Sin embargo, puesto que las claves de busqueda ´ que aparecen en los nodos internos no aparecen en ninguna otra parte, nos vemos obligados a incluir un campo adicional para un puntero por cada clave de busqueda de un nodo interno, que apuntan a registros del archivo ´ o a los cajones. El borrado en un a´ rbol B es m´as complicado. La entrada borrada podr´ıa aparecer en un nodo interno, debiendo elegir el valor apropiado del sub´arbol del nodo para sustituirla.

5

´ ESTATICA ´ ASOCIACION

5.

8

Asociacion ´ est´atica

Un inconveniente de la organizacion ´ de archivos secuenciales es que hay que acceder a una estructura de ´ındices para localizar los datos o utilizar una busqueda binaria, resultando en m´as operaciones de E/S. La organizacion ´ ´ de archivos basada en la t´ecnica de la asociaci´on (hashing) permite evitar el acceso a la estructura del ´ındice.

5.1.

Organizacion ´ de archivos por asociacion ´

En una organizacion ´ de archivos por asociacion ´ se obtiene la direccion ´ del bloque de disco que contiene el registro deseado mediante el c´alculo directo de una funcion del ´ unidireccional sobre el valor de la clave busqueda ´ registro. En nuestra descripcion ´ de asociacion, ´ utilizaremos el t´ermino caj´on (bucket) para indicar una unidad de almacenamiento que puede guardar uno o m´as registros. Formalmente, sea K el conjunto de todos los valores de clave de busque´ da y sea B el conjunto de todas las direcciones posibles de cajones, una funci´on de asociaci´on h es una funcion ´ de K a B. Para insertar un registro con clave de busqueda Ki , calculamos h(Ki ), lo ´ que nos proporcionar´a la direccion ´ del cajon ´ donde almacenar el registro. Para realizar una busqueda por el valor de Ki , simplemente se calcula h(Ki ), ´ y luego se busca el registro dentro del cajon. ´ Hay que realizar esta busqueda ´ porque dos claves de busqueda distintas, por ejemplo, K5 y K7 pueden dar el ´ mismo valor de asociacion, ´ es decir h(K5 ) = h(k7 ), por lo que ambos registros est´an almacenados en el mismo cajon. ´ 5.1.1.

Funciones de asociacion ´

La peor funcion ´ posible de asociacion ´ asigna todos los valores de la clave de busqueda al mismo cajon. tiene que examinar cada ´ ´ Una busqueda ´ registro hasta encontrar el deseado. Una funcion ´ de asociacion ´ ideal distribuye las claves almacenadas uniformemente a trav´es de todos los cajones, para que cada uno de ellos contenga el mismo numero de registros. Como normalmente no se sabe que ´ valores de clave se usar´an en el archivo, se busca una funcion ´ gen´erica que cumpla lo siguiente: Distribucion ´ uniforme Cada cajon ´ tendr´a asignado m´as o menos el mismo numero de valores de la clave de busqueda. ´ ´ Distribucion ´ aleatoria No habr´a correlacion ´ entre los valores obtenidos por la funcion ´ y ningun ´ criterio exterior de ordenacion ´ sobre los valores de la clave, como por ejemplo el orden alfab´etico o la longitud de la clave. La funcion ´ de asociacion ´ tendr´a que parecer aleatoria.

5

´ ESTATICA ´ ASOCIACION

9

Las funciones de asociacion ´ t´ıpicas realizan c´alculos sobre la representacion ´ binaria interna para los caracteres de la clave de busqueda. ´

5.2.

Gestion ´ de desbordamientos de cajones

Si, al insertar un registro, el cajon ´ que le toca est´a lleno, sucede lo que se denomina desbordamiento de cajones. Estos pueden ocurrir por varias razones: Numero ´ insuficiente de cajones El numero de cajones, que se denota con ´ nB , debe ser escogido tal que nC > nr / fr , donde nr denota el numero ´ total de registros que ser´an almacenados, y fr denota el numero de ´ registros que se colocar´an en un cajon. ´ Esta designacion ´ presupone que se conoce el numero total de registros cuando se define la funcion ´ ´ de asociacion. ´ Atasco Algunos cajones tendr´an asignados m´as registros que otros, por lo que un cajon ´ se podr´ıa desbordar incluso cuando otros cajones tienen todav´ıa espacio. Esta situacion ´ se denomina atasco de cajones. El atasco puede ocurrir por dos razones: 1. Varios registros podr´ıan tener la misma clave de busqueda. ´ 2. La funcion ´ de asociacion ´ elegida podr´ıa producir una distribucion ´ no uniforme. El desbordamiento de cajones se trata utilizando cajones extra, llamados cajones de desbordamiento. Si un registro se tiene que insertar en un cajon ´ C, que ya est´a lleno, se crear´a un cajon ´ de desbordamiento para C, y el registro se insertar´a en el cajon ´ de desbordamiento. Si este se llenara tambi´en, se crear´ıa un nuevo cajon ´ de desbordamiento, y as´ı sucesivamente. Todos los cajones de desbordamiento de un cajon ´ determinado se encadenan juntos utilizando una lista enlazada, t´ecnica que se conoce como cadena de desbordamiento.

5.3.

´ Indices asociativos

La asociatividad se puede utilizar no solo ´ para la organizacion ´ de archivos sino tambi´en para la creacion ´ de estructuras de ´ındice. Un ´ındice asociativo (hash index) organiza las claves de busqueda, con sus punteros ´ asociados, dentro de una estructura de archivo asociativo. Para construirlo, se aplica la funcion para identificar ´ de asociacion ´ sobre la clave de busqueda ´ un cajon, ´ y luego se almacena la clave y los punteros asociados en el cajon ´ (o en los cajones de desbordamiento, si procede). Se usa el t´ermino ´ındice asociativo para denota las estructuras de archivo asociativo, as´ı como los ´ındices secundarios asociativos.

6

´ DINAMICA ´ ASOCIACION

6.

10

Asociacion ´ din´amica

Como se ha visto, la necesidad de determinar el conjunto C de direcciones de cajon ´ presenta un serio problema con la t´ecnica de asociacion ´ est´atica, ya que la mayor´ıa de las bases de datos crecen con el tiempo. Si se va a utilizar la asociacion ´ est´atica, hay tres opciones: 1. Elegir una funcion ´ de asociacion ´ basada en el tamano ˜ actual del archivo. Esta opcion ´ producir´a una degradacion ´ del rendimiento a medida que la tabla crezca. 2. Elegir una funcion ´ de asociacion ´ basada en el tamano ˜ previsto del archivo. Inicialmente, pierde una cantidad de espacio significativa, pero se evita la degradacion ´ de la opcion ´ anterior. 3. Reorganizar periodicamente la estructura asociativa en respuesta al ´ crecimiento del archivo. Esto operacion ´ implica recalcular la funcion ´ de asociacion ´ de cada registro del archivo, y reasignar los cajones. Por ello, es una operacion ´ masiva, que requiere mucho tiempo y, normalmente, es necesario impedir el acceso al archivo durante la reorganizacion. ´ Algunas t´ecnicas de asociaci´on din´amica permiten modificar la funcion ´ de asociacion ´ din´amicamente para acomodarse al aumento o disminucion ´ de la base de datos. Se ver´a una de estas t´ecnicas, denominada asociaci´on extensible.

6.1.

Asociacion ´ extensible

La asociacion ´ extensible afronta los cambios en el tamano ˜ de la base de datos separando y uniendo los cajones a medida que las tablas aumentan o disminuyen. De esta forma, se conserva de forma eficaz el espacio. Adem´as, como la reorganizacion ´ se produce sobre un cajon ´ cada vez, la degradacion ´ del rendimiento es aceptable. Se elige una funcion ´ de asociacion ´ que genere valores dentro de un rango relativamente amplio, de b bits. No se crea un cajon ´ para cada valor de la funcion ´ de asociacion, ´ sino que los cajones se van creando bajo demanda. Para ello, inicialmente no se utilizan el total de b bits, sino i, donde 0 ≤ i ≤ b. Estos i bits se utilizan como desplazamiento en una tabla adicional, que contiene las direcciones de los cajones. El valor de i aumenta o disminuye con el tamano ˜ de la base de datos. Aunque se requieren i bits para encontrar la entrada correcta en la tabla de direcciones de los cajones, algunas entradas consecutivas de la tabla podr´ıan apuntar al mismo cajon. ´ Todas estas entradas tendr´an un prefijo comun ´ del valor de la funcion ´ de asociacion, ´ aunque la longitud de este

7

´ DE LA INDEXACION ´ ORDENADA Y LA ASOCIACION11 ´ COMPARACION

prefijo bien puede ser menor que i. Por tanto, se asocia con cada cajon ´ un numero entero que proporciona la longitud del prefijo comun. ´ ´ Este numero ´ nos servir´a para saber si, al aumentar o disminuir el numero de registro, ´ debemos dividir o refundir cajones. Para localizar el cajon Kn , ´ que contiene el valor de la clave de busqueda ´ se toman los i bits m´as significativos de h(Kn ), se busca la entrada de la tabla que corresponda a esta cadena de bits, y se sigue el puntero del cajon ´ en la tabla. Para insertar, se sigue el mismo procedimiento, pero si no hubiera espacio, hay que dividir el cajon, ´ y redistribuir los registros. Si i = i j , solo ´ una entrada en la tabla de direcciones apunta al cajon ´ j, por lo que es necesario incrementar el tamano ˜ de la tabla de direcciones, para poder incluir los dos cajones que resultar´an de la division, ´ y redistribuir los registros entre ambos. Si i > i j , se puede dividir el cajon ´ j en dos y redistribuir sin necesidad de incrementar el tamano ˜ de la tabla. En ambos casos, solo ´ se necesita recalcular la funcion ´ de asociacion ´ en los registros del cajon ´ j. La ventaja principal de este esquema es que el rendimiento no se degrada a medida que crece el archivo. Adem´as, el espacio requerido adicional es m´ınimo. Aunque la tabla de direcciones es un gasto adicional, al contener solo ´ punteros, la tabla es pequena. ˜ Un inconveniente es que la busqueda ´ implica un nivel adicional de indireccion. ´

7.

Comparacion ´ de la indexacion ´ ordenada y la asociacion ´

Las t´ecnicas de ´ındices ordenados son preferibles a las estructuras organizativas en los casos donde la consulta especifica un rango de valores. Si las consultas son por igualdad de valores, en general es preferible la asociacion ´ (aunque el peor caso posible en una estructura asociativa es peor que el peor caso posible en un ´ındice ordenado).

8.

Definicion ´ de ´ındices en SQL

En principio, un sistema de base de datos puede decidir qu´e ´ındices crear. Sin embargo, no es f´acil hacer una eleccion ´ apropiada autom´aticamente. Por este motivo, la mayor´ıa de las implementaciones de SQL proporcionan control sobre la creacion del ´ y eliminacion ´ de ´ındices v´ıa ordenes ´ lenguaje de definicion ´ de datos. Un ´ındice se crea mediante la orden create index, la cual tiene la forma: create index nombre-´ındice on nombre-relaci´on (lista-atributos)

9

ACCESOS MULTICLAVE

12

Donde lista-atributos es la lista de atributos de la relacion ´ que constituye la clave de busqueda del ´ındice. ´ Si deseamos declarar que la clave de busqueda es una clave candidata, ´ hay que anadir el atributo unique a la definicion ˜ ´ del ´ındice: create unique index nombre-´ındice on nombre-relaci´on (lista-atributos) El nombre de ´ındice especificado con el ´ındice se necesita para hacer posible la eliminacion ´ (drop) de ´ındices. La orden drop index tiene la forma: drop index nombre-´ındice

9.

Accesos multiclave

Hasta ahora se ha asumido impl´ıcitamente que se utiliza solamente un ´ındice para procesar una consulta. Sin embargo, puede resultar ventajoso el uso de multiples ´ ´ındices, si e´ stos existen. Aun m´as eficiente es crear y usar un ´ındice con una clave de busqueda ´ que no es un simple atributo, sino una lista de atributos. El orden de los valores de la clave de busqueda es el orden lexicogr´afico, muy parecido al ´ orden alfab´etico. Para acelerar el procesamiento en general de consultas con varias claves de busqueda se pueden emplear estructuras especiales, como los archivos ´ ´ en ret´ıcula y los Indices de mapas de bits.

9.1.

Archivos en ret´ıcula

Los archivos en ret´ıcula se forma con un array bidimensional (matriz) llamado array en ret´ıcula y dos arrays unidimensionales llamados escalas lineales. Cada celda en el array de ret´ıcula tiene un puntero a un cajon ´ que contiene valores de las claves de busqueda y punteros a los registros. ´ Para conservar espacio, se permite que varios elementos del array puedan apuntar al mismo cajon. ´ Los archivos en ret´ıcula proporcionan un descenso significativo en el tiempo de procesamiento de consultas multiclave. Sin embargo, implican un gasto adicional de espacio, as´ı como una degradacion ´ del rendimiento al insertar y borrar registros.

9.2.

´ Indices de mapas de bits

Un mapa de bits es un array de bits. En su forma m´as simple, un ´ındice de mapas de bits sobre un atributo A de la relacion ´ r consiste en un mapa de bits para cada valor que pueda tomar A.

9

ACCESOS MULTICLAVE

9.2.1.

13

Estructura de los ´ındices de mapas de bits

Cada mapa de bits tiene tantos bits como el numero de registros de la ´ relacion. ´ El ´ı-´esimo bit del mapa de bits para el valor v j se establece en 1 si el registro con numero i tiene el valor v j para el atributo A. El resto de bits ´ del mapa de bits se establecen a 0. 9.2.2.

Implementacion ´ eficiente de las operaciones de mapas de bits

Los ´ındices de mapas de bits son utiles para las selecciones principal´ mente cuando hay selecciones bajo varias claves. Supongase que se crea un ´ ´ındice de mapas de bits sobre el atributo A y otro ´ındice de mapas de bits para el atributo B en la relacion ´ r. Consid´erese ahora una consulta que seleccione por ambos atributos, tal y como σ(A=a∧B=b) (r). Para evaluar esta seleccion ´ se busca el valor a en el mapa de bit de A y el valor b en el mapa de bit de B, y se realiza la interseccion ´ (conjuncion ´ logica) ´ de los dos mapas de bits. En otras palabras, se calcula un nuevo mapa de bits donde el bit i tiene el valor 1 si el i-´esimo bit de los dos mapas de bits es 1, y tiene el valor 0 en caso contrario. El sistema puede calcular entonces el resultado de la consulta buscando todos los bits con valor 1 en el mapa de bits resultante, y recuperando los registros correspondientes. Otro uso importante de los mapas de bits es contar el numero de tuplas ´ que satisfacen una seleccion ´ dada. Tales consultas son importantes para el an´alisis de datos. Los ´ındices de mapas de bits son generalmente muy pequenos ˜ comparados con el tamano ˜ real de la relacion. ´ Los registros tienen generalmente de decenas a centenas de bytes, mientras que un unico bit representa a un ´ registro en el mapa de bits. As´ı, el espacio ocupado por un unico mapa de ´ bits es usualmente menor que el 1 por ciento del espacio ocupado por la relacion. ´