2 Corrected Indexing Exercises

Database indexes are processed by indexing in order to find their record in a database as quickly as possible. Here is a series of exercises dealing with this problem. The course on binary search trees also addresses this problem by

indexing

Simple indexing exercise

Let us recall some definitions:

  1. Index = table allowing the relative address of this article (position in the file) to be associated with an article key (application data)
  2. Indexed access methods = way of fetching articles (application data) in a file from indexed organization (è primary index)
  3. Density of an index = quotient of the number of keys in the index to the number of articles in the file. Thus, a dense index has as many keys as there are articles in the file. If the file is sorted, we can use a non-dense index (eg: the largest key of the articles in each block with the relative address of the block)
  4. Hierarchical index = index on an index, on an index, ... to speed up the search for the key in the index
  5. Discriminant or non-discriminatory indexes = on discriminating or non-discriminatory data (identifying an article uniquely or not)
  6. Index placing = which arranges the articles in the order of the keys and restores them in the order in sequential reading of the memory
  7. Primary index = which is based on the key of the articles, allows them to be stored in memory (incidentally, accelerates access on key)
  8. Secondary index = an access accelerator, this index is non-discriminatory

Organizations indexed 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é is also called tree-B, B-tree Where balanced shaft. 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 arbre-B d’ordre m est un arbre tel que

(i) each node contains k sorted keys, with m <= k <= 2m except the root for which k checks 1<=k <= 2m.

(ii) every non-leaf node has (k+1) children. The ith son has keys including the (i-1)th and ith keys of the father.

(iii)   l’arbre est équilibré.

indexation B-tree

Question 1          

Compte tenu de la définition formelle des arbre-B, quelle seront les hauteurs minimale et maximale (nombre de niveaux) d’un arbre-B d’ordre m contenant n clés ?

Question 2          

Quels sont les critères de choix de l’ordre d’un arbre-B si l’on utilise cette structure pour construire un index ?

Question 3          

Quel est l’intérêt que la structure d’un index arborescent soit équilibrée ?

Question 4

Dans les applications réelles, les clés d’accès peuvent être de taille variable. En déduire le format de stockage du nœud d’un arbre-B. Quelle est l’utilité des bornes m et 2m fixées pour le nombre k de clés par nœud et comment faut-il interpréter ces bornes dans de cas de clés de taille variable ?

Question 5          

Représenter l’arbre-B de la Figure 1 après insertion des clés 37 puis 36.

Question 6

Représenter l’arbre-B de la Figure 1 après suppression des clés 17 puis 31.

Question 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.

Question 1

La hauteur d’un arbre-B évolue de façon logarithmique par rapport au nombre de clés stockées dans l’arbre. En effet, dans un arbre-B d’ordre m, chaque nœud possède entre (m+1) et (2m+1) fils. On peut donc stocker, au niveau i+1 de l’arbre-B, entre (m+1) et (2m+1) fois plus de clés qu’au niveau i, suivant que l’arbre est faiblement ou fortement occupé. Les formules de calcul de la hauteur minimale et maximale d’un arbre-B, en fonction de son ordre et du nombre de clés qu’il contient, sont donc:

         h_min » log_(2m+1) n h_max » log_(m+1) n

Par exemple, un arbre-B d’ordre 100 peut contenir plus de 8 millions de clés sur seulement trois niveaux. 

Question 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. 

Question 3

Une arborescence équilibrée garantit un coût d’accès constant à toute valeur de clé indépendamment de la distribution des clés. Il est donc possible de borner le nombre d’E/S nécessaire à la recherche ou à l’écriture d’un article. Cette propriété est particulièrement importante en bases de données. En effet, lorsque plusieurs chemins d’accès peuvent être empruntés pour accéder à un article, un SGBD doit être capable de faire automatiquement le choix optimal.

Question 4

A B-tree node contains a set of pairs (key, child pointer) and an additional pointer referencing the first child node (a node containing n keys has n+1 children), as shown in Figure 1. If the size of the keys is fixed, this size is stored in the index descriptor. If the size of the keys is variable, two solutions are possible:

– the keys are framed by a special character. This character, called a separator, must have a binary coding different from all the bytes likely to be contained in a key. Furthermore, reading the ith key of a node requires reading byte by byte of all the keys preceding it in this node.

– les clés sont précédées d’un champ longueur. Cette technique est la seule applicable si le codage binaire des clés couvre l’ensemble des codes binaires possibles. La ième clé d’un nœud peut ainsi être accédée en sautant de champ longueur en champ longueur.

bdd indexation b-tree

Figure 1. Format de stockage d’un noeud d’arbre-B

Les bornes m et 2m assurent que le taux de remplissage d’un nœud varie entre 50% et 100% (et est donc en moyenne de 75%). Dans la définition des arbres-B,  ce taux de remplissage k est exprimé en nombre de clés par nœud. Lorsque l’on utilise des arbres-B contenant des clés de taille variable, le taux de remplissage d’un nœud doit alors être exprimé en nombre d’octets plutôt qu’en nombre de clés.

Question 5

Les insertions des clés 37 puis 36 sont illustrées sur la Figure. L’insertion de la clé 36 provoque l’éclatement de la feuille où elle doit être insérée. La remontée de la clé médiane 37 provoque à son tour l’éclatement du nœud père de cette feuille. L’arbre-B croît donc par le haut et reste équilibré.  

bdd indexation b-tree

Figure 2. Insertion of keys 37 then 36

Question 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.

bdd indexation b-tree

Figure 3. Deleting keys 17 then 31

Deleting key 31 introduces a particular problem in that it does not belong to a leaf. To delete a key in a non-leaf node, replace it with the largest key in the left subtree (key 29 in the previous example) or with the smallest key in the right subtree (key 32 in the example ) whose key to delete is root. The chosen key must in turn be deleted from the sheet using the classic deletion procedure.

Question 7

La structure d’arbre-B permet les accès séquentiels triés puisque les clés sont triées dans l’arborescence. Cependant, un parcours séquentiel trié de l’arbre-B nécessite, après lecture de toutes les clés d’une feuille (resp. d’un nœud), de remonter au nœud père pour accéder à la feuille sœur droite (nœud frère droit) afin de continuer la lecture des clés dans l’ordre trié. Ainsi, un nœud père sera accédé sur disque à chaque lecture de l’un de ses fils, afin de récupérer l’adresse de ce fils. Il en résulte qu’une lecture séquentielle triée des 12 nœuds et feuilles de l’arbre-B présenté nécessite au total 20 E/S.

Une optimisation de la structure d’arbre-B pour les parcours séquentiels triés consiste à dupliquer toutes les clés stockées dans les nœuds non feuille au niveau des feuilles puis à chaîner ces feuilles entre elles dans l’ordre du tri.  L’adresse de la première feuille peut de plus être stockée dans le descripteur de fichier. Ainsi, un parcours séquentiel trié ne nécessite que la lecture des feuilles de l’arbre. Ce type d’arbre est appelé arbre-B+ [Comer79]. L’arbre-B+ correspondant à l’arbre-B est présenté Figure 4.

bdd indexation b-tree

Figure 4.  Arbre-B+ correspondant à l’arbre-B de la figure 2

Multiple index exercise

In the field of databases, article searches are generally carried out on multiple criteria (example: searching for cars with power greater than 10 hp and Citroën brand). File organizations indexed with a single index favor processing the most frequently used search criterion on a file, ordering the articles on disk according to this criterion. To efficiently process multi-criteria searches, it is possible to manage several indexes for the same file.

The solution consists of using a main placing index (the data is sorted according to this index) and subsidiary indexes, called secondary indexes. 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.

Question 1

We wish to use an organization based on a B+ tree technique to index the articles of a file according to several attributes, A1 being primary (placing) key and A2, A3, … Ap being secondary keys. Specify how the algorithms for inserting, updating and deleting articles in files should be modified.

Question 2

In the same context where the file is placed on A1 and indexed on the secondary keys A2, A3, … Ap, specify the algorithm for executing a criterion restriction (A1 = v1 & A2 = v2 … & Ap = vp ). How can we optimize the search for relevant articles? How to modify the algorithm if some "and" ( & ) are replaced by "or" ( | ), assuming a disjunctive normal form (and of or)?

Question 3

In the same context where the file is placed on A1 and indexed on the secondary keys A2, A3, … Ap, specify the algorithm for executing a criterion restriction (A1 = v1 & A2 = v2 … & Ap = vp & B1 = v'1 & B2 = v'2 & …), the Bi being non-indexed attributes. Given a forecast frequency of querying and updating an attribute, specify how to choose whether an attribute benefits from being indexed or not?

 Les algorithmes de gestion des arbre-B+ introduits  font l’hypothèse d’un tri mono-critère (c-à-d, prenant en compte un seul attribut). Afin de prendre en compte plusieurs attributs dans la méthode de placement, il suffit d’adapter la fonction Search_dichoto  à un tri multi-critères. La clé à utiliser dans le tri est la concaténation des attributs A1, A2, …, An. La comparaison de 2 clés s’effectue d’abord sur l’attribut A1. En cas d’égalité, on prend en compte la valeur de l’attribut A2 et ainsi de suite. Une clé c1 est donc considérée comme supérieure à une clé c2 si ($i / c1.Ai > c2.Ai) et (i=1 ou « j<i c1.Ai = c2.Ai).

This method does not treat different attributes equally. Thus, if the chosen sorting criterion is A1, A2, ..., An, it is possible to accelerate searches based on a complete key or based on a partial key provided that this partial key preserves the first attributes of the complete key. Thus, a search for all articles such that (A1=value1 and A2=value2) is possible. On the other hand, a search for all articles such as (A2=value1 and A3=value2) without specifying a value for A1 cannot be accelerated by the B+ tree.

To share