Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes d'information

Index : arbres B+, hachage et optimisation des requêtes

Pages et coût d'accès, arbres B+ avec démonstration de la hauteur et un exemple sur un milliard de lignes, hachage, index primaires, secondaires et composites, coût sur les écritures, l'optimiseur et EXPLAIN.

https://www.electronics-engineering.com/fr/index-arbres-b-plus-optimiseur-de-requetes/

Pas encore de vote : soyez le premier à noter cette page.

Une table d’un milliard de lignes peut être lue en entier, mais cela prend des minutes. Trouver le client d’un code donné en quelques millisecondes demande un index, comme celui d’un livre. Dans cette leçon, nous regardons comment une base de données organise les données sur le disque, les arbres B+ avec la démonstration de leur hauteur et un exemple numérique, les index de hachage, les index composites et la règle du préfixe, le coût des index sur les écritures et le travail de l’optimiseur.

Pages et accès

Le SGBD lit et écrit les données par pages (blocs) de quelques kilo-octets, typiquement 4-16 Ko. Le coût d’une requête se mesure en pages lues, parce qu’un accès au disque est des milliers de fois plus lent qu’une opération en mémoire : environ 10 ms sur un disque magnétique, 0,1 ms sur un SSD. Un tampon (buffer) en mémoire garde les pages les plus utilisées. Sans index, chercher une valeur exige un balayage (scan) de toute la table : pour un milliard de lignes de 100 octets, 100 Go.

Les arbres B+

L’index le plus utilisé est l’arbre B+ : un arbre équilibré dont chaque nœud occupe une page et contient de nombreuses clés ordonnées avec des pointeurs vers les enfants. Les feuilles contiennent les clés avec des références aux lignes (ou les lignes elles-mêmes) et sont reliées en une liste ordonnée. Tout nœud sauf la racine est rempli au moins à moitié, et toutes les feuilles sont à la même profondeur.

Arbre B+ à trois niveaux
La racine et les nœuds internes contiennent des clés de séparation : pour chercher 66, on va à droite depuis la racine (66 est supérieur ou égal à 40), puis dans l’enfant du milieu (66 est entre 60 et 75), et l’on trouve la feuille. Les feuilles sont reliées entre elles, si bien qu’une recherche par intervalle continue dans l’ordre sans remonter dans l’arbre.

Théorème. Un arbre B+ de N clés dans ses feuilles, où chaque nœud interne a au plus f enfants et au moins \lceil f/2\rceil (la racine au moins 2), a une hauteur h qui satisfait

    \[ \log_f N \le h \le 1 + \log_{\lceil f/2\rceil}\frac{N}{2} \]

Démonstration. *Borne inférieure.* Chaque niveau multiplie le nombre de nœuds par au plus f, donc un arbre de hauteur h a au plus f^h positions de feuilles : pour contenir N clés il faut f^h \ge N, c’est-à-dire h \ge \log_f N. *Borne supérieure.* La racine a au moins 2 enfants et tout autre nœud interne au moins \lceil f/2\rceil : au niveau des feuilles il y a au moins 2\lceil f/2\rceil^{h-1} nœuds, donc (avec des feuilles remplies au moins à moitié) au moins autant de portions de clés. De 2\lceil f/2\rceil^{h-1} \le N on tire h \le 1 + \log_{\lceil f/2\rceil}(N/2). ∎

Le point essentiel est le facteur de branchement (fan-out) f : avec des pages de 8 Ko et des clés de 40 octets avec leurs pointeurs, f vaut environ 200. Exemple. Avec N = 10^9 clés, \log_{200}10^9 \approx 3.9 : 4 niveaux suffisent, et même dans le pire cas, avec des nœuds à moitié pleins, il en faut 5. Les deux ou trois premiers niveaux, quelques milliers de pages, restent toujours dans le tampon : trouver une ligne parmi un milliard coûte une ou deux lectures sur disque. Les insertions et les suppressions gardent l’arbre équilibré en scindant les nœuds pleins et en fusionnant ceux qui sont trop vides, à un coût lui aussi logarithmique.

Les feuilles reliées rendent aussi efficaces les recherches par intervalle (« notes entre 25 et 28 », « commandes de mars ») ainsi que le tri : on trouve la première valeur et l’on parcourt la liste.

Les index de hachage

Un index de hachage calcule à partir de chaque clé, avec une fonction de hachage, le numéro du seau où la chercher : en moyenne un seul accès, quelle que soit la taille de la table. Mais il ne fonctionne que pour les recherches d’égalité : les clés sont dispersées au hasard entre les seaux, et il ne sert à rien pour les intervalles et le tri. C’est pourquoi les SGBD utilisent presque toujours des arbres B+, et les index de hachage dans des cas particuliers, comme les jointures en mémoire.

Index primaires, secondaires et composites

Un index primaire (ou groupé, clustered) détermine l’ordre physique des lignes dans la table : les lignes de clés voisines sont dans les mêmes pages, et un intervalle se lit avec quelques pages consécutives. Il ne peut y en avoir qu’un. Les index secondaires contiennent des références à des lignes dispersées : lire beaucoup de lignes par un index secondaire peut coûter plus qu’un balayage, une page différente pour chaque ligne.

Un index composite sur plusieurs colonnes, par exemple (nom, prénom), est trié d’abord par nom et, à nom égal, par prénom. Il sert les recherches par nom, ou par nom et prénom, mais pas celles par prénom seul, qui est dispersé dans tout l’index : c’est la règle du préfixe le plus à gauche.

Le prix des index

Chaque index accélère les lectures mais ralentit les écritures : chaque insertion, mise à jour ou suppression doit mettre à jour tous les index de la table, et chaque index occupe de la place. On indexe donc les colonnes réellement utilisées dans les conditions de recherche et de jointure, en particulier les clés étrangères, et non toutes les colonnes « au cas où ».

L’optimiseur

Pour chaque requête, le SGBD évalue de nombreux plans d’exécution équivalents (quel index utiliser, dans quel ordre joindre les tables, avec quel algorithme de jointure) et choisit celui de moindre coût estimé, en s’appuyant sur des statistiques sur les données : nombre de lignes, valeurs distinctes, distribution. Un index est rentable quand la condition est sélective, c’est-à-dire qu’elle sélectionne une petite fraction des lignes, typiquement moins de 5-10 % ; sinon, un balayage séquentiel est plus rapide. La commande EXPLAIN montre le plan choisi, et c’est le premier outil quand une requête est lente : on découvre souvent un balayage complet là où l’on attendait un index, à cause d’une colonne non indexée ou d’une condition écrite de façon à empêcher l’usage de l’index, comme une fonction appliquée à la colonne.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x