Indexation B-Arbre

Un index B-tree est une structure de données en arbre équilibré couramment utilisée dans les bases de données pour organiser et rechercher efficacement de grands volumes de données.
Les B-trees sont très similaires aux arbres de recherche binaire (BST), mais les nœuds d'un B-tree peuvent avoir plus de deux enfants. Vous pouvez en apprendre davantage sur les BST dans le cours Aperçu des Algorithmes et Structures de Données.

Le B-tree stocke les clés dans un ordre trié au sein des nœuds, permettant une récupération rapide des données par traversée hiérarchique du nœud racine aux nœuds feuilles. L'indexation B-tree est bien adaptée aux requêtes de plage et aux recherches d'égalité, ce qui en fait un choix populaire pour optimiser les performances des bases de données.

Comment ça fonctionne ?

L'index B-tree organise les données de manière hiérarchique, chaque nœud contenant un nombre fixe de clés et de pointeurs vers les nœuds enfants.
Les B-trees maintiennent l'équilibre en s'assurant que tous les nœuds feuilles sont au même niveau, ce qui optimise les opérations de recherche.
Lors de la recherche d'une clé particulière, l'algorithme B-tree parcourt l'arbre du nœud racine jusqu'aux nœuds feuilles, en utilisant la recherche binaire pour localiser efficacement la clé souhaitée.

La recherche d'index implique de parcourir l'arbre pour atteindre les nœuds feuilles, de suivre la chaîne de nœuds feuilles pour trouver les enregistrements correspondants, et de récupérer les données réelles du disque.

Dans la figure, la recherche de la clé 302 est illustrée :

1. Une structure d'arbre de recherche est un type d'arbre où chaque nœud a deux pointeurs : le pointeur gauche pointe vers les nœuds enfants avec des valeurs inférieures au nœud parent, et le pointeur droit pointe vers les nœuds enfants avec des valeurs supérieures au nœud parent ;

2. Dans un B-tree, le nœud racine peut contenir plusieurs valeurs d'index. Par exemple, si la racine contient trois valeurs distinctes, elle aura trois pointeurs, chacun indiquant la plage de valeurs entre ces valeurs clés ;

3. Pour rechercher une clé, telle que 302, la recherche commence au nœud racine et suit les pointeurs appropriés jusqu'aux nœuds feuilles. La recherche est terminée après avoir traversé trois blocs d'arbre, comme illustré dans le diagramme en rouge ;

4. Pour rechercher une plage de valeurs à partir de 302, vous pouvez utiliser les pointeurs horizontaux entre les nœuds feuilles. Par exemple, récupérer des valeurs de 302 à 502 se fait en suivant les nœuds feuilles de manière séquentielle.

Remarque

La clé utilisée pour la recherche dans un index B-tree provient des valeurs stockées dans la ou les colonnes indexées de la table de la base de données. Par exemple, si l'index est sur une colonne comme "client_id", la clé de recherche sera les valeurs réelles de "client_id". Chaque valeur numérique unique dans la colonne indexée sert de clé dans l'index B-tree, facilitant la recherche et la récupération des lignes correspondantes dans la table de la base de données.

Avantages et inconvénients

Contrairement à la structure de données standard de l'arbre binaire de recherche, les nœuds B-tree peuvent accueillir plus de 2 enfants. Le nombre maximum par défaut d'enfants par nœud est généralement fixé à 16.

Implémentation de l'index

Pour créer un index B-tree sur une colonne dans PostgreSQL, vous pouvez utiliser la commande SQL suivante :

Comme l'index B-tree est un index par défaut en SQL, nous pouvons également utiliser l'instruction suivante pour le créer :

Remarque

En SQL, lorsque vous créez une table avec une contrainte de clé primaire, la plupart des systèmes de gestion de bases de données créent automatiquement un index sur la ou les colonnes spécifiées dans la clé primaire. Cet index aide à faire respecter la contrainte d'unicité de la clé primaire et améliore également les performances des requêtes impliquant des recherches ou des jointures basées sur la ou les colonnes de la clé primaire.