Les B-arbres et les index de base de données

Qu’est-ce qu’un B-tree ?

• Le B-tree joue un rôle fondamental dans de nombreux logiciels, en particulier les systèmes de gestion de bases de données (SGBD)

• MySQL, Postgres, MongoDB, Dynamo et d’autres s’appuient sur les B-tree pour effectuer des recherches de données efficaces via des index

• Nous allons voir comment fonctionnent les B-tree et les B+tree, pourquoi les bases de données les utilisent pour les index, et pourquoi utiliser un UUID comme clé primaire peut être une mauvaise idée

• Un B-tree stocke des paires de données appelées clés et valeurs dans ce que les programmeurs appellent une structure semblable à un arbre

• Un B-tree est composé de nœuds (rectangles) et de pointeurs enfants (lignes reliant les nœuds)

• Le nœud tout en haut s’appelle le nœud racine, les nœuds du niveau le plus bas sont les nœuds feuilles, et tous les autres sont des nœuds internes

• Voici la définition d’un B-tree :

  • Chaque nœud stocke N paires clé/valeur (où N est supérieur à 1 et inférieur ou égal à K)
  • Chaque nœud interne contient au moins N/2 paires clé/valeur (un nœud interne n’est ni une feuille ni la racine)
  • Chaque nœud possède N+1 enfants
  • Le nœud racine contient au moins une valeur et deux enfants, sauf s’il est le seul nœud
  • Toutes les feuilles se trouvent au même niveau

• Une autre caractéristique essentielle du B-tree est l’ordre : à l’intérieur de chaque nœud, les éléments sont maintenus triés

• Grâce à cet ordre, il est possible de rechercher des clés de manière très efficace. La recherche commence au nœud racine et suit les étapes suivantes :

  1. Vérifier si la clé recherchée est présente dans le nœud
  2. Sinon, trouver dans le nœud l’endroit où la clé serait insérée
  3. À partir de là, suivre le pointeur enfant vers le niveau suivant et répéter le processus

• De cette manière, pour rechercher une clé, il suffit de visiter un seul nœud à chaque niveau de l’arbre

• Le B-tree a été spécialement conçu pour bien fonctionner avec de très grandes quantités de données qui doivent en plus être conservées sur du stockage longue durée (disque). Cela est possible parce que chaque nœud utilise un nombre fixe d’octets

• Dans un B-tree, le nombre de valeurs qu’un nœud peut stocker dépend du nombre d’octets qui lui est alloué et du nombre d’octets consommés par chaque paire clé/valeur

B+tree (optimisé pour les bases de données)

• Le B+tree ressemble au B-tree, mais les règles suivantes changent :
  • Les paires clé/valeur sont stockées uniquement dans les nœuds feuilles
  • Les nœuds non feuilles ne stockent que des clés et les pointeurs enfants associés
• L’implémentation des index MySQL avec des B+tree ajoute deux règles spécifiques :
  • Les nœuds non feuilles stockent N pointeurs enfants au lieu de N+1
  • Tous les nœuds incluent aussi des pointeurs "suivant" et "précédent", si bien que chaque niveau de l’arbre peut également fonctionner comme une liste doublement chaînée
• Il y a deux raisons pour lesquelles le B+tree convient mieux aux bases de données :
  1. Comme les nœuds internes n’ont pas besoin de stocker les valeurs, ils peuvent contenir davantage de clés. Cela aide à réduire la profondeur de l’arbre
  2. Toutes les valeurs sont stockées au même niveau et peuvent être parcourues dans l’ordre via la liste chaînée du niveau inférieur

Utilisation des B+tree dans MySQL

• MySQL prend en charge plusieurs moteurs de stockage, et le plus couramment utilisé est InnoDB, qui repose fortement sur les B+tree
• En réalité, InnoDB s’y appuie tellement qu’il stocke toutes les données de la table dans un B+tree en utilisant la clé primaire de la table comme clé de l’arbre
• Chaque fois que vous créez une nouvelle table InnoDB, vous devez spécifier une clé primaire
• MySQL crée un B+tree pour chaque nouvelle table, et la valeur définie comme clé primaire devient la clé de l’arbre. La valeur associée correspond au reste des colonnes de chaque ligne et n’est stockée que dans les nœuds feuilles
• La taille de chaque nœud de ce B+tree est fixée par défaut à 16k
• Chaque fois que MySQL doit accéder à un fragment de données (clé, valeur, etc.), il charge depuis le disque la page entière associée (le nœud du B+tree), même s’il n’a pas besoin des autres clés ou valeurs
• Il est aussi courant de créer des index secondaires sur une table InnoDB. Pour chaque index secondaire, un B+tree persistant supplémentaire est construit : la clé correspond à la colonne choisie pour l’index, et la valeur est la clé primaire de la ligne associée

Choix de la clé primaire : insertions

• Comme la manière dont les données de la table sont organisées dans le B+tree dépend de la clé choisie, le choix de PRIMARY KEY affecte la disposition sur disque de toutes les données de la table
• Deux choix courants pour la clé primaire sont :
  • une séquence d’entiers (BIGINT UNSIGNED AUTO_INCREMENT, par exemple)
  • UUID (qui existe en plusieurs versions)
• Si vous utilisez une clé primaire UUIDv4, alors lors d’une insertion :
  1. Il est impossible de prédire à l’avance quel nœud sera visité pour l’insertion
  2. Il est impossible de prédire quelle feuille sera la destination de l’insertion
  3. Les valeurs des feuilles ne sont pas ordonnées
• Les points 1 et 2 posent problème parce que de nombreuses insertions amènent à visiter beaucoup de nœuds (pages) dans l’arbre. Ces lectures et écritures excessives dégradent les performances
• Si vous utilisez BIGINT UNSIGNED AUTO_INCREMENT comme clé primaire :
  1. L’insertion d’une nouvelle valeur suit toujours le chemin le plus à droite
  2. Les feuilles ne sont ajoutées qu’à droite de l’arbre
  3. Au niveau des feuilles, les données sont triées dans l’ordre d’insertion
• Grâce aux points 1 et 2, de nombreuses insertions séquentielles revisitent le même chemin de pages, ce qui réduit les requêtes d’E/S quand on insère beaucoup de paires clé/valeur

Choix de la clé primaire : lecture ordonnée des données

• Il est courant de récupérer des données dans l’ordre chronologique dans une base de données
• Si vous utilisez UUIDv4 comme clé primaire, la séquence de valeurs renvoyée par la recherche sera dispersée sur plusieurs nœuds feuilles non contigus
• Si vous recherchez des valeurs insérées séquentiellement, toutes les pages contenant les résultats seront adjacentes entre elles. Lorsqu’on récupère plusieurs lignes, elles peuvent même toutes se trouver côte à côte dans une seule page
• Pour ce type de requêtes, une clé primaire séquentielle peut réduire le nombre de pages à lire

Choix de la clé primaire : taille

• La taille de la clé primaire est aussi un point important. Une clé primaire doit toujours :
  1. être suffisamment grande pour ne pas s’épuiser
  2. être suffisamment petite pour ne pas consommer trop d’espace de stockage
• Pour les séquences d’entiers, on peut utiliser MEDIUMINT (16 millions de valeurs uniques) ou INT (4 milliards de valeurs uniques) pour des tables plus petites
• Pour les grandes tables, on choisit BIGINT par sécurité (18 quintillions de valeurs possibles). BIGINT fait 64 bits (8 octets)
• Un UUID fait généralement 128 bits (16 octets), soit deux fois la taille du plus grand type entier de MySQL
• Comme les nœuds d’un B+tree ont une taille fixe, utiliser BIGINT permet de stocker plus de clés par nœud qu’avec un UUID. Cela se traduit par un arbre moins profond et des recherches plus rapides

B+tree, pages et InnoDB

• L’un des grands avantages du B+tree est qu’on peut définir la taille des nœuds comme on le souhaite
• Dans InnoDB, les nœuds du B+tree sont généralement fixés à 16k, c’est-à-dire la taille des pages InnoDB
• Lors du traitement des requêtes (et donc du parcours du B+tree), InnoDB ne lit pas les lignes et colonnes individuellement depuis le disque. Chaque fois qu’il doit accéder à un fragment de données, il charge la page entière associée
• InnoDB utilise plusieurs techniques pour atténuer cela, la principale étant le buffer pool. Le buffer pool est un cache mémoire des pages InnoDB situé entre les pages sur disque et l’exécution des requêtes MySQL
• Quand MySQL doit lire une page, il vérifie d’abord si elle est déjà dans le buffer pool. Si oui, il la lit depuis là et évite l’opération d’E/S disque. Sinon, il récupère la page sur disque, l’ajoute au buffer pool, puis poursuit l’exécution de la requête
• Le buffer pool améliore énormément les performances des requêtes. Sans lui, il faudrait effectuer beaucoup plus d’opérations d’E/S disque pour traiter la charge de requêtes

Autres cas

• Ici, l’accent a surtout été mis sur la comparaison entre clés séquentielles et clés aléatoires/UUID, mais ces principes restent utiles quel que soit le type de clé primaire ou secondaire envisagé
• Par exemple, vous pouvez envisager d’utiliser un timestamp user.created_at comme clé d’index, car il présente des caractéristiques similaires à celles d’un entier séquentiel. Sauf insertion de données historiques, les insertions suivent généralement toujours le chemin le plus à droite
• À l’inverse, une chaîne comme user.email_address a des propriétés plus proches d’une clé aléatoire. Les utilisateurs ne créent pas leurs comptes dans l’ordre alphabétique de leur adresse e-mail, donc les insertions se répartissent dans tout le B+tree

Conclusion

• Nous avons couvert beaucoup d’aspects sur les B+tree, les index et le choix des clés primaires
• En apparence, cela semble simple, mais pour tirer le maximum de performances d’une base de données, il faut tenir compte de nombreuses subtilités
• Pour aller plus loin, vous pouvez visiter ce site interactif sur les B+tree

[GN⁺]

Avis Hacker News

• Ils maintiennent leur wiki utile en utilisant une stratégie de gestion comparable à un B-Tree

  • Lorsqu'il y a trop de pages d'accueil, ils déplacent les liens et les sections vers des sous-pages
  • Les liens similaires et anciens sont déplacés vers des pages sœurs correspondant au sujet
  • Au final, les anciens documents sont déplacés à trois niveaux sous la page d'accueil
  • La documentation finit par être un problème de recherche
  • C'est une bonne façon de passer un vendredi après-midi de manière productive

• Cela faisait longtemps que je cherchais quelque chose comme ça, billet impressionnant

  • J'aurais aimé qu'il y ait une section sur les index composites

• Merci pour ces visuels impressionnants

  • J'ai travaillé sur la prise en charge de l'indexation BTree+ au-dessus d'Aerospike
  • Supprimer les clés expirées du BTree+ était un vrai défi
  • Nous avons décidé de ne fusionner qu'un branchement d'un niveau à l'intérieur du premier nœud feuille frère
  • Nous avons ajouté du sharding au-dessus du BTree+ pour accélérer le système et réduire la contention sur les verrous
  • Le BTree+ peut devenir déséquilibré pendant le processus de nettoyage
  • Nous avons fourni une fonction de reconstruction d'index pour éviter des opérations de nettoyage supplémentaires

• La fenêtre modale des cookies ne fonctionne pas sur Firefox mobile

  • Il faudrait permettre à l'utilisateur de le configurer dans le navigateur

• Il ne faut pas utiliser une colonne UUID comme clé primaire

  • Il faut recopier un entier de 128 bits dans tous les aspects relationnels
  • Dans la plupart des cas, c'est totalement aléatoire
  • Il faut utiliser un PK bigserial (64 bits) pour les relations internes des tables, et des UUID (128 bits) pour les identifiants au niveau applicatif et les clés naturelles
  • La base de données s'en portera beaucoup mieux

• Excellent support pédagogique

  • Ce genre de démos interactives aide énormément

• Si les blocs disque et les nœuds de B-tree font 16k, et que les clés, les valeurs et les pointeurs enfants font tous 8 bits, on peut stocker 682 paires clé/valeur et 683 pointeurs enfants par nœud

  • Un arbre à trois niveaux peut stocker plus de 300 millions de paires clé/valeur
  • Chaque élément devrait faire 8 octets

• Excellent article

  • Quand InnoDB stocke les données dans le B-tree lui-même, on parle d'index clusterisé
  • MyISAM utilisait des index non clusterisés
  • Oracle et d'autres permettent de choisir

• Quelqu'un demande ce que signifient v0, v1, ...v10 dans le graphique

  • Il se demande si cela représente des pages différentes

• Magnifique visualisation interactive

  • C'est du plus haut niveau en matière de pédagogie et de vulgarisation