SYSTÈMES INFORMATIQUES Systèmes de gestion de bases de données

Accès aux données

Une requête écrite en SQL est traduite en une séquence d'opérations (procédures) qui prennent en entrée des fichiers où sont stockées les données interrogées : un fichier est une représentation machine d'une relation. Chaque n-uplet de la relation est représenté par un article du fichier. Pour diminuer le temps de réponse à une requête, il est indispensable d'accéder au plus petit ensemble d'articles nécessaires pour répondre à la requête. Rechercher une information précise (par exemple le montant disponible sur un compte) nécessite la lecture de un ou plusieurs blocs d'information sur disque. Avec la technologie actuelle, une lecture de bloc dure entre 3 et 10 millisecondes. Il faut donc essayer de minimiser le nombre de blocs du disque auxquels accéder lors d'une requête.

Par exemple, si on recherche les comptes de montant supérieur à 100 000 euros, on veut éviter d'avoir à parcourir tous les comptes (on dit dans ce cas qu'on balaie la relation), ce qui peut amener à lire 100 blocs sur disque, voire beaucoup plus, pour comparer le montant de chaque compte à 100 000 euros. Comme on peut supposer que le nombre de comptes de montant supérieur à 100 000 euros est faible, comment y accéder rapidement ?

La sélection par l'optimiseur des procédures pour exécuter une requête SQL et le choix d'un bon ordre entre ces procédures reposent sur les statistiques accumulées sur les données (taille des relations, distribution des valeurs d'attributs dans le domaine de définition, etc.) et sur l'existence d'index. Plus précisément, l'index est une structure de données qui permet de passer d'une recherche linéaire dans la taille de la relation (dans le cas d'un balayage) à une recherche logarithmique en cette taille, voire constante. On espère également que ces structures additionnelles ont une taille raisonnable et que les mises à jour de ces structures sont également aisées et efficaces. Nous venons d'illustrer le problème d'accès rapide à un fichier représentant une relation pour des opérations de filtrage simple (accès rapide aux comptes ayant un montant supérieur à 100 000 euros). Le problème d'accès rapide aux données est encore plus crucial lorsqu'on veut minimiser le temps d'exécution d'une jointure, qui nécessite l'accès à deux relations.

La requête Q2 « noms et montants des comptes des clients ingénieurs » nécessite une jointure sur le numéro de client. Il est souhaitable que la table Clients ou la table Comptes ait un index sur l'attribut numéroclient. On associe ainsi un ou plusieurs index à chaque relation sur les attributs clés ou sur ceux qui apparaissent souvent dans des critères de sélection.

Un attribut est une clé si sa valeur ne peut être la même pour deux n-uplets de la même relation. Cette valeur identifie le n-uplet.

On utilise presque exclusivement comme structure de données pour l'index, un arbre B (de l'anglais B-tree, probablement de balanced tree, « arbre équilibré », c'est-à-dire ayant le même nombre de niveaux dans chaque branche), une structure arborescente inventée en 1971 par Rudolf Bayer, qu'on traverse de la racine jusqu'à une ou plusieurs feuilles. Soit à indexer un fichier sur la valeur de l'attribut A avec un arbre B. Une feuille de l'arbre est placée dans un bloc disque et contient des entrées qui sont des couples (a, adresse de n-uplet dans le fichier indexé) pour chaque article du fichier tel que A = a. Trouver les n-uplets tels que A = a, consiste à traverser l'index jusqu'à la feuille qui contient une entrée telle que A = a. Les entrées sont triées sur la valeur de A. Cela permet les recherches par intervalle : il suffit de rechercher (en traversant l'arbre) la borne inférieure de l'intervalle[...]