2 ejercicios de indexación corregidos

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

indexación

Ejercicio de indexación sencillo

Recordemos algunas definiciones:

  1. Í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)
  2. 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)
  3. 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)
  4. Índice jerárquico = índice sobre un índice, sobre un índice, ... para acelerar la búsqueda de la clave en el índice
  5. Índices discriminantes o no discriminatorios = sobre datos discriminatorios o no discriminatorios (identificando un artículo de forma única o no)
  6. 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.
  7. Í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)
  8. Índice secundario = un acelerador de acceso, este índice no es discriminatorio

Organizaciones indexado nécessitent la création d’un index trié sur lequel sont appliquées les recherches dichotomiques d’une valeur de clé discriminante ou non. Le fichier étant lui-même trié sur clé, l’index correspondant est de type primaire non dense. Cet index peut être vu comme une table de couples  (val_clé, adr_page) où val_clé est la plus petite clé des articles stockés dans la page référencée par adr_page. Lorsque l’index est de grande taille, on le décompose en une arborescence dont chaque nœud a une taille inférieure ou égale à une page. Le nœud sommet de l’arborescence est appelé racine de l’index. 

Lors de la recherche d’une valeur de clé dans l’index, un examen de la racine permet de déterminer la partie de l’arbre dans laquelle se poursuivra la recherche en renvoyant sur un nœud de niveau immédiatement inférieur. L’examen de ce nœud permet à son tour d’affiner l’intervalle de recherche. Ce processus récursif s’applique jusqu’à rencontrer un nœud ou une feuille (nœud de plus bas niveau de l’arbre) contenant la valeur de clé cherchée et l’adresse de la page associée. Les organisations arborescentes se différencient par le principe suivant lequel est gérée la dynamicité de l’index hiérarchique. 

Ce principe détermine les performances obtenues tant au niveau du nombre d’E/S nécessaires pour parcourir l’index qu’au niveau du taux d’occupation de chaque nœud de la hiérarchie.

a arbre balancé es tambien llamado árbol-B, árbol B Dónde eje equilibrado. Intuitivement, il est possible de construire une arborescence dynamique de la façon suivante. Lorsqu’un index est de grande taille, il est possible d’indexer à son tour le fichier contenant cet index et ce, de façon récursive jusqu’à ce que l’index de plus haut niveau (la racine) tienne sur une seule page. Compte tenu de la dynamicité de l’index, la racine elle-même peut croître et ne plus tenir dans une page. 

On rajoute alors un niveau à la hiérarchie d’index. La hiérarchie grossit donc par la racine de telle sorte que tous les chemins de la racine aux feuilles ont même longueur. La définition formelle d’un arbre-B est donnée ci-dessous et est illustrée sur l’exemple de la Figure 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.

Indexación de árbol B

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

De nombreuses applications exécutent des traitements séquentiels triés sur leurs fichiers. La structure d’arbre-B est-elle bien adaptée à ce type de traitements ? Combien d’E/S nécessite un parcours séquentiel trié de toutes les clés de l’arbre-B présenté Figure 1 ? Proposer une optimisation de cette structure permettant de lire uniquement les feuilles de l’arbre lors d’un parcours séquentiel trié. Cette organisation est connue sous le nom arbre-B+. Discuter des avantages des  arbres B+ par rapport aux arbres 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

Lors d’une recherche (ou d’une écriture) dans un index, l’accès à chaque nœud traversé dans l’arborescence génère une E/S. Les hauteurs minimale et maximale de l’arborescence bornent donc le coût en E/S de recherche d’une clé dans l’index. Or, il a été montré dans la question précédente que plus l’ordre de l’arbre-B est grand, plus sa hauteur est faible. D’autre part, on a montré que le nombre de comparaisons engendrées par la recherche d’une clé dans un arbre-B est indépendant de l’ordre de cet arbre-B. 

Il est donc intéressant de choisir un ordre aussi grand que possible afin de stocker un maximum de clés par nœud et minimiser la hauteur de l’index. Ce choix doit cependant tenir compte de la taille maximale des nœuds d’arbre-B. Cette taille est bornée par la taille d’une page disque afin d’assurer que la lecture d’un nœud nécessite une seule 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.

árbol b de indexación bdd

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.  

árbol b de indexación bdd

Figura 2. Inserción de las teclas 37 y luego 36

Pregunta 6

La suppression de la clé 17 entraîne une sous-occupation de la feuille contenant la clé 17. On choisit ici de fusionner cette feuille avec sa sœur droite (feuille appartenant au même nœud père). La clé médiane 24 redescend dans la feuille résultat de la fusion. La fusion de deux feuilles peut être suivie d’un ré-éclatement si la feuille résultat de la fusion se trouve sur-occupée. Lors de la fusion de 2 nœuds (resp. feuilles), le choix du frère (resp. sœur) avec lequel effectuer la fusion peut être systématique (frère droit ou frère gauche à chaque fois) ou bien dynamique. 

Un choix dynamique permet de fusionner avec le nœud (resp. feuille) qui produira un résultat de fusion le plus stable possible, c’est-à-dire ni sur-occupé ni sous-occupé. Cette optimisation nécessite cependant la lecture des deux frères (resp. sœurs) pour un gain hypothétique.

árbol b de indexación bdd

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.

árbol b de indexación bdd

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 index secondaire est constitué sur un attribut (ou plusieurs) discriminant ou non et donne pour chaque valeur de l’attribut les identifiants (souvent les adresses relatives) des articles ayant cette valeur. L’attribut (ou le groupe d’attributs) ainsi indexé est appelé clé secondaire. 

Lors d’une recherche sur clé secondaire, l’accès à l’index secondaire (un arbre B ou B+)  délivre les identifiants de tous les articles satisfaisant le critère de recherche. Ces articles sont ensuite récupérés un à un via leurs identifiants, à raison d’au plus une E/S par article. La création d’un index secondaire introduit un coût de stockage important. De plus, toute mise à jour du fichier de données entraîne la mise à jour de tous les index secondaires portant sur ce fichier. L’utilisation d’index secondaires doit donc être restreinte à des critères de recherche fréquents.

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.

Compartir, repartir