SYSTÈMES INFORMATIQUESSystèmes de gestion de bases de données

Carte mentale

Élargissez votre recherche dans Universalis

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 et de parcourir ensuite en séquence les entrées de l'index (fig. 2). Le fichier indexé a une organisation quelconque. En particulier, il n'a pas besoin d'être trié sur le montant du compte.

S.G.B.D. relationnel : fichier Comptes et arbre B

Dessin : S.G.B.D. relationnel : fichier Comptes et arbre B

Fichier Comptes et arbre B indexant le fichier Comptes sur le montant, avec au maximum quatre entrées par nœud. En réalité, la capacité d'un nœud est celle d'un bloc sur disque. Elle est couramment de 50 à 100 entrées par nœud. Chaque entrée de cet index est un couple (m,@) où m est... 

Crédits : Encyclopædia Universalis France

Afficher

L'évolution souple de l'index en cas de croissance importante du fichier indexé est une qualité de l'arbre B. Il possède en outre les propriétés suivantes. Quelle que soit la valeur a de l'attribut A, trouver la ou les entrées de l'index telles que A = a dépend uniquement de la hauteur de l'arbre, qui est O(logC(B)) [ce qui signifie que la hauteur de l'arbre est proportionnelle à logC(B)], si B est le nombre de blocs nécessaire pour stocker la relation et C le nombre d'entrées d'index qu'on peut stocker dans un bloc. Comme la recherche prend le même temps quelle que soit la valeur de A, la complexité affi [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 10 pages

Médias de l’article

S.G.B.D. relationnel : exemples de relations

S.G.B.D. relationnel : exemples de relations
Crédits : Encyclopædia Universalis France

dessin

S.G.B.D. relationnel : fichier Comptes et arbre B

S.G.B.D. relationnel : fichier Comptes et arbre B
Crédits : Encyclopædia Universalis France

dessin

S.G.B.D. relationnel : accès concurrent et transactions

S.G.B.D. relationnel : accès concurrent et transactions
Crédits : Encyclopædia Universalis France

dessin

S.G.B.D. relationnel : données hétérogènes

S.G.B.D. relationnel : données hétérogènes
Crédits : Encyclopædia Universalis France

dessin

Afficher les 4 médias de l'article


Écrit par :

  • : professeur des Universités
  • : professeur des Universités, Conservatoire national des arts et métiers, laboratoire Cédric

Classification

Autres références

«  SYSTÈMES INFORMATIQUES  » est également traité dans :

SYSTÈMES INFORMATIQUES - Conception, architecture et urbanisation des systèmes d'information

  • Écrit par 
  • Sylvie SERVIGNE
  •  • 3 256 mots
  •  • 7 médias

Le système d'information est aujourd'hui un élément central du fonctionnement d'une organisation. Un système d'information peut être défini comme un ensemble de ressources (personnel, logiciels, processus, données, matériels, équipements informatique et de télécommunication...) permettant la collecte, le stockage, la structuration, la m […] Lire la suite

SYSTÈMES INFORMATIQUES - Systèmes d'aide à la décision

  • Écrit par 
  • Elisabeth METAIS
  •  • 8 395 mots
  •  • 7 médias

L'information est la matière première la plus précieuse pour la compétitivité des entreprises au xxie siècle et l'intelligence – humaine ou artificielle – a besoin de cette connaissance pour aider à la prise de décision. Le partage de données et la diffusion de connaissance sont donc les domaines les plus s […] Lire la suite

Voir aussi

Pour citer l’article

Bernd AMANN, Michel SCHOLL, « SYSTÈMES INFORMATIQUES - Systèmes de gestion de bases de données », Encyclopædia Universalis [en ligne], consulté le 12 août 2022. URL : https://www.universalis.fr/encyclopedie/systemes-informatiques-systemes-de-gestion-de-bases-de-donnees/