Los índices de bases de datos se procesan mediante indexación para encontrar su registro en una base de datos lo más rápido posible. A continuación presentamos una serie de ejercicios que abordan este problema. El curso sobre árboles de búsqueda binarios también aborda este problema al
Ejercicio de indexación sencillo
Recordemos algunas definiciones:
- Índice = tabla que permite asociar la dirección relativa de este artículo (posición en el archivo) a una clave de artículo (datos de la aplicación)
- Métodos de acceso indexados = forma de recuperar artículos (datos de la aplicación) en un archivo de una organización indexada (è índice primario)
- Densidad de un índice = cociente del número de claves en el índice y el número de artículos en el archivo. Por lo tanto, un índice denso tiene tantas claves como artículos en el archivo. Si el archivo está ordenado, podemos usar un índice no denso (por ejemplo: la clave más grande de los artículos en cada bloque con la dirección relativa del bloque)
- Índice jerárquico = índice sobre un índice, sobre un índice, ... para acelerar la búsqueda de la clave en el índice
- Índices discriminantes o no discriminatorios = sobre datos discriminatorios o no discriminatorios (identificando un artículo de forma única o no)
- Colocación de índice = que ordena los artículos en el orden de las claves y los restaura en el orden en la lectura secuencial de la memoria.
- Índice primario = que se basa en la clave de los artículos, permite almacenarlos en la memoria (por cierto, acelera el acceso a la clave)
- Índice secundario = un acelerador de acceso, este índice no es discriminatorio
Organizaciones indexado requieren la creación de un índice ordenado en el que se apliquen búsquedas dicotómicas de un valor clave discriminante o no discriminatorio. El archivo en sí está ordenado por clave, el índice correspondiente es de tipo primario no denso. Este índice puede verse como una tabla de pares (key_val, page_adr) donde key_val es la clave más pequeña de los artículos almacenados en la página a la que hace referencia page_adr. Cuando el índice es grande, se descompone en una estructura de árbol en la que cada nodo tiene un tamaño menor o igual a una página. El nodo superior del árbol se llama raíz del índice.
Al buscar un valor clave en el índice, un examen de la raíz ayuda a determinar en qué parte del árbol continuar la búsqueda regresando a un nodo de nivel inmediatamente inferior. Examinar este nodo a su vez permite refinar el intervalo de búsqueda. Este proceso recursivo se aplica hasta encontrar un nodo o una hoja (nodo de nivel más bajo del árbol) que contiene el valor clave buscado y la dirección de la página asociada. Las organizaciones arbóreas se diferencian por el principio según el cual se gestiona la dinámica del índice jerárquico.
Este principio determina el rendimiento obtenido tanto en términos del número de E/S necesarias para navegar por el índice como en términos de la tasa de ocupación de cada nodo en la jerarquía.
a árbol oscilante es tambien llamado árbol-B, árbol B Dónde eje equilibrado. Intuitivamente, es posible construir una estructura de árbol dinámica de la siguiente manera. Cuando un índice es grande, es posible indexar el archivo que contiene este índice de forma recursiva hasta que el índice de nivel más alto (la raíz) quepa en una sola página. Dada la dinámica del índice, la raíz misma puede crecer y ya no cabe en una página.
Luego agregamos un nivel a la jerarquía del índice. Por lo tanto, la jerarquía crece desde la raíz de modo que todos los caminos desde la raíz hasta las hojas tienen la misma longitud. La definición formal de un árbol B se proporciona a continuación y se ilustra con el ejemplo de la Figura 1.
Un árbol B de orden m es un árbol tal que
(i) cada nodo contiene k claves ordenadas, con m <= k<= 2m excepto la raíz para la cual k verifica 1<=k <= 2m.
(ii) cada nodo que no es hoja tiene (k+1) hijos. El i-ésimo hijo tiene claves, incluidas la (i-1)ésima y la iésima claves del padre.
(iii) el árbol está equilibrado.
Pregunta 1
Dada la definición formal de árboles B, ¿cuáles serán las alturas mínima y máxima (número de niveles) de un árbol B de orden m que contiene n claves?
Pregunta 2
¿Cuáles son los criterios para elegir el orden de un árbol B si usamos esta estructura para construir un índice?
Pregunta 3
¿Cuál es el punto de equilibrar la estructura de un índice de árbol?
Pregunta 4
En aplicaciones reales, las claves de acceso pueden variar en tamaño. Deduzca el formato de almacenamiento del nodo de un árbol B. ¿Para qué sirven los límites m y 2m fijados para el número k de claves por nodo y cómo deben interpretarse estos límites en el caso de claves de tamaño variable?
Pregunta 5
Represente el árbol B en la Figura 1 después de insertar las claves 37 y luego 36.
Pregunta 6
Represente el árbol B en la Figura 1 después de quitar las claves 17 y luego 31.
Pregunta 7
Muchas aplicaciones realizan un procesamiento secuencial ordenado en sus archivos. ¿La estructura del árbol B se adapta bien a este tipo de procesamiento? ¿Cuánta E/S requiere un recorrido secuencial ordenado de todas las claves en el árbol B que se muestra en la Figura 1? Proponga una optimización de esta estructura que permita leer solo las hojas del árbol durante un recorrido secuencial ordenado. Esta organización se conoce como árbol B+. Analice las ventajas de los árboles B+ sobre los árboles B.
Pregunta 1
La altura de un árbol B escala logarítmicamente con respecto al número de claves almacenadas en el árbol. De hecho, en un árbol B de orden m, cada nodo tiene entre (m+1) y (2m+1) hijos. Por lo tanto, podemos almacenar, en el nivel i+1 del árbol-B, entre (m+1) y (2m+1) veces más claves que en el nivel i, dependiendo de si el árbol está poco o muy ocupado. Las fórmulas para calcular la altura mínima y máxima de un árbol B, en función de su orden y del número de claves que contiene, son por tanto:
h_min » log_(2m+1) n h_max » log_(m+1) n
Por ejemplo, un árbol B de orden 100 puede contener más de 8 millones de claves en sólo tres niveles.
Pregunta 2
Al buscar (o escribir) un índice, acceder a cada nodo atravesado en el árbol genera una E/S. Por lo tanto, las alturas mínima y máxima del árbol limitan el costo de E/S de buscar una clave en el índice. Sin embargo, en la pregunta anterior se demostró que cuanto mayor es el orden del árbol B, menor es su altura. Por otro lado, hemos demostrado que el número de comparaciones generadas por la búsqueda de una clave en un árbol B es independiente del orden de este árbol B.
Por tanto, es interesante elegir un pedido lo más grande posible para almacenar un máximo de claves por nodo y minimizar la altura del índice. Sin embargo, esta elección debe tener en cuenta el tamaño máximo de los nodos del árbol B. Este tamaño está limitado por el tamaño de una página de disco para garantizar que la lectura de un nodo requiera solo una E/S.
Pregunta 3
Un árbol equilibrado garantiza un coste de acceso constante a cualquier valor clave independientemente de la distribución de claves. Por lo tanto, es posible limitar el número de E/S necesarias para investigar o escribir un artículo. Esta propiedad es particularmente importante en las bases de datos. De hecho, cuando se pueden tomar varias vías de acceso para acceder a un artículo, un DBMS debe poder realizar automáticamente la elección óptima.
Pregunta 4
Un nodo de árbol B contiene un conjunto de pares (clave, puntero secundario) y un puntero adicional que hace referencia al primer nodo secundario (un nodo que contiene n claves tiene n+1 hijos), como se muestra en la Figura 1. Si el tamaño de las claves es fijo, este tamaño se almacena en el descriptor de índice. Si el tamaño de las claves es variable, son posibles dos soluciones:
– las teclas están enmarcadas por un carácter especial. Este carácter, llamado separador, debe tener una codificación binaria diferente de todos los bytes que pueden estar contenidos en una clave. Además, leer la iésima clave de un nodo requiere leer byte a byte de todas las claves que la preceden en este nodo.
– las claves están precedidas por un campo de longitud. Esta técnica es la única aplicable si la codificación binaria de las claves cubre todos los códigos binarios posibles. Por tanto, se puede acceder a la iésima clave de un nodo saltando de un campo de longitud a otro.
Figura 1. Formato de almacenamiento de un nodo de árbol B
Los terminales my 2m garantizan que la tasa de llenado de un nodo varía entre 50% y 100% (y por tanto es de media 75%). En la definición de árboles B, esta tasa de llenado k se expresa en número de claves por nodo. Cuando se utilizan árboles B que contienen claves de tamaño variable, la tasa de llenado de un nodo debe expresarse en número de bytes en lugar de en número de claves.
Pregunta 5
Las inserciones de las teclas 37 y 36 se ilustran en la Figura. La inserción de la llave 36 provoca que reviente la hoja donde se va a insertar. La subida de la tecla central 37 provoca a su vez la explosión del nodo padre de esta hoja. Por lo tanto, el árbol B crece desde arriba y se mantiene equilibrado.
Figura 2. Inserción de las teclas 37 y luego 36
Pregunta 6
La eliminación de la clave 17 da como resultado una subocupación de la hoja que contiene la clave 17. Elegimos aquí fusionar esta hoja con su hermana derecha (hoja que pertenece al mismo nodo padre). La tecla del medio 24 vuelve a bajar a la hoja de resultados de la fusión. La fusión de dos hojas puede ir seguida de una nueva distribución si la hoja resultante de la fusión está sobreocupada. Al fusionar 2 nodos (o hojas), la elección del hermano (o hermana) con el que realizar la fusión puede ser sistemática (hermano derecho o hermano izquierdo cada vez) o dinámica.
Una elección dinámica le permite fusionarse con el nodo (o hoja), lo que producirá el resultado de fusión más estable posible, es decir, ni sobreocupado ni subocupado. Esta optimización, sin embargo, requiere la lectura de ambos hermanos (respectivamente hermanas) para obtener una ganancia hipotética.
Figura 3. Eliminando las claves 17 y luego 31
La eliminación de la clave 31 introduce un problema particular porque no pertenece a una hoja. Para eliminar una clave en un nodo no hoja, reemplácela con la clave más grande en el subárbol izquierdo (clave 29 en el ejemplo anterior) o con la clave más pequeña en el subárbol derecho (clave 32 en el ejemplo) cuya clave a eliminar es raíz. La clave elegida a su vez debe eliminarse de la hoja mediante el procedimiento de eliminación clásico.
Pregunta 7
La estructura del árbol B permite accesos secuenciales ordenados ya que las claves están ordenadas en el árbol. Sin embargo, un recorrido secuencial ordenado del árbol B requiere, después de leer todas las claves de una hoja (respectivamente de un nodo), volver al nodo padre para acceder a la hoja hermana derecha (nodo hermano derecho) para continuar leyendo. las llaves en orden ordenado. Por lo tanto, se accederá a un nodo padre en el disco cada vez que se lea uno de sus hijos, para recuperar la dirección de este hijo. Como resultado, una lectura secuencial ordenada de los 12 nodos y hojas del árbol B presentado requiere un total de 20 E/S.
Una optimización de la estructura del árbol B para recorridos secuenciales ordenados es duplicar todas las claves almacenadas en nodos que no son hoja en el nivel de hoja y luego encadenar estas hojas en orden de clasificación. La dirección de la primera hoja también se puede almacenar en el descriptor de archivo. Por lo tanto, un recorrido secuencial ordenado solo requiere leer las hojas del árbol. Este tipo de árbol se denomina árbol B+ [Comer79]. El árbol B+ correspondiente al árbol B se presenta en la Figura 4.
Figura 4. Árbol-B+ correspondiente al árbol-B en la Figura 2
Ejercicio de índice múltiple
En el ámbito de las bases de datos, las búsquedas de artículos se realizan generalmente según múltiples criterios (ejemplo: búsqueda de coches con potencia superior a 10 CV y marca Citroën). Las organizaciones de archivos indexados con un único índice favorecen el procesamiento del criterio de búsqueda más utilizado en un archivo, ordenando los artículos en disco según este criterio. Para procesar de forma eficiente búsquedas multicriterio, es posible gestionar varios índices para un mismo archivo.
La solución consiste en utilizar un índice de colocación principal (los datos se ordenan según este índice) e índices subsidiarios, llamados índices secundarios. Un índice secundario se constituye sobre un atributo (o varios) que puede o no ser discriminatorio y proporciona para cada valor del atributo los identificadores (a menudo las direcciones relativas) de los artículos que tienen este valor. El atributo (o grupo de atributos) así indexado se denomina clave secundaria.
Durante una búsqueda de clave secundaria, el acceso al índice secundario (un árbol B o B+) entrega los identificadores de todos los artículos que satisfacen el criterio de búsqueda. Luego, estos artículos se recuperan uno por uno a través de sus identificadores, con como máximo una E/S por artículo. La creación de un índice secundario introduce un costo de almacenamiento significativo. Además, cualquier actualización del archivo de datos hace que se actualicen todos los índices secundarios relacionados con este archivo. Por tanto, el uso de índices secundarios debe limitarse a criterios de búsqueda frecuentes.
Pregunta 1
Deseamos utilizar una organización basada en una técnica de árbol B+ para indexar los artículos de un archivo según varios atributos, siendo A1 la clave primaria (ubicación) y A2, A3,… Ap las claves secundarias. Especifique cómo se deben modificar los algoritmos para insertar, actualizar y eliminar artículos en archivos.
Pregunta 2
En el mismo contexto donde el archivo se coloca en A1 y se indexa en las claves secundarias A2, A3,… Ap, especifique el algoritmo para ejecutar una restricción de criterio (A1 = v1 & A2 = v2… & Ap = vp). ¿Cómo podemos optimizar la búsqueda de artículos relevantes? ¿Cómo modificar el algoritmo si algunos "y" ( & ) se reemplazan por "o" ( | ), asumiendo una forma normal disyuntiva (y de o)?
Pregunta 3
En el mismo contexto donde el archivo se coloca en A1 y se indexa en las claves secundarias A2, A3,… Ap, especifique el algoritmo para ejecutar una restricción de criterio (A1 = v1 & A2 = v2… & Ap = vp & B1 = v' 1 & B2 = v'2 &…), siendo Bi atributos no indexados. Dada una frecuencia prevista de consulta y actualización de un atributo, especifique cómo elegir si un atributo se beneficia de estar indexado o no.
Los algoritmos de gestión de árboles B+ introducidos suponen una clasificación por criterio único (es decir, teniendo en cuenta un único atributo). Para tener en cuenta varios atributos en el método de colocación, basta con adaptar la función Buscar_dicoto a la clasificación multicriterio. La clave a utilizar en la clasificación es la concatenación de los atributos A1, A2,…, An. La comparación de 2 claves se realiza primero en el atributo A1. En caso de igualdad, tomamos en cuenta el valor del atributo A2 y así sucesivamente. Por lo tanto, una clave c1 se considera superior a una clave c2 si ($i / c1.Ai > c2.Ai) y (i=1 o “j
Este método no trata los diferentes atributos por igual. Así, si el criterio de clasificación elegido es A1, A2, ..., An, es posible acelerar las búsquedas a partir de una clave completa o a partir de una clave parcial siempre que esta clave parcial conserve los primeros atributos de la clave completa. Por lo tanto, es posible una búsqueda de todos los artículos tales que (A1=valor1 y A2=valor2). Por otro lado, el árbol B+ no puede acelerar una búsqueda de todos los artículos como (A2=valor1 y A3=valor2) sin especificar un valor para A1.
ES 
FR 
EN