- En lisant récemment Database Internals d’Alex Petrov, j’ai découvert des explications sur la façon dont les moteurs de stockage des SGBD sont implémentés, en particulier sur les optimisations de la structure de données B-Tree
- À l’université, quand j’ai appris les B-Tree, je les avais simplement compris comme un « BST en mieux », sans vraiment saisir pourquoi ils étaient utilisés en pratique
- Si l’on tient compte des E/S disque, la structure B-Tree est adaptée au stockage de gros volumes de données et à leur recherche rapide
- Cet article présente pourquoi les B-Tree sont nécessaires, comment ils fonctionnent, et quels types d’optimisations sont possibles dans une implémentation réelle
- L’une de leurs principales caractéristiques est de regrouper de nombreuses clés dans un même nœud afin de réduire le nombre d’accès au disque
Contraintes imposées par le disque
- On suppose une situation où l’ensemble des données ne tient pas en mémoire
- Le disque se lit et s’écrit par pages
- Un accès disque est beaucoup plus lent qu’un accès mémoire
- La structure de données doit donc organiser les données autour des pages et permettre le plus grand nombre possible de comparaisons de clés avec un minimum d’accès disque
- Si l’on stocke un BST tel quel sur disque, les nœuds sont dispersés, ce qui fait augmenter le nombre d’accès disque en proportion du nombre d’étapes de recherche
- Un B-Tree regroupe plusieurs clés dans un nœud afin de pouvoir comparer plusieurs clés après une seule lecture disque
Pages à slots
- Lorsqu’on place des données sur disque, on les gère par « pages »
- Chaque page contient un en-tête, des cellules pour les données de longueur variable, ainsi qu’un tableau de pointeurs d’offset indiquant l’emplacement de ces cellules
- La structure de page à slots permet de conserver l’ordre de tri même si la taille des clés varie, sans coût important de réorganisation
- Lors d’une suppression ou d’une insertion de clé, il est bien plus efficace de réordonner des pointeurs que de déplacer les données elles-mêmes
- Par exemple, SQLite utilise une free list dans cette structure de page afin de réutiliser l’espace des cellules supprimées
Recherche dans un B-Tree
- L’algorithme de recherche dans un B-Tree est simple :
- partir du nœud racine
- regarder les separator keys du nœud courant pour trouver le nœud enfant où la clé recherchée est censée se trouver
- parcourir l’arbre de manière récursive
- si l’on trouve la feuille contenant la clé recherchée, c’est terminé ; sinon, on conclut qu’elle n’existe pas
- Les nœuds internes peuvent ne contenir que des separator keys au lieu des données réelles, celles-ci étant généralement stockées uniquement dans les feuilles
- Afin de retrouver efficacement les clés à l’intérieur d’un nœud par recherche binaire, les clés de chaque nœud sont maintenues triées
Réduction des separator keys
- Dans les nœuds internes, il n’est pas nécessaire de stocker la clé complète : il suffit qu’elle permette de délimiter une plage
- Par exemple, pour distinguer 0xAAAAAA de 0xBBBBBB, il n’est pas indispensable de stocker l’intégralité de 0xBBBBBB ; un préfixe plus court peut suffire
- Dans les bases de données où les clés sont longues, ce type de réduction peut permettre un gain d’espace de stockage important
- Au-delà de cette réduction des separator keys, il existe aussi des stratégies pour réduire efficacement les préfixes (prefix) et suffixes (suffix)
- Comme les feuilles sont bien plus nombreuses, certains estiment que la compression par préfixe contribue davantage aux performances
Pages d’overflow
- Lorsqu’un nœud contient trop de clés pour tenir dans une seule page, on utilise des pages d’overflow
- Au lieu de déplacer la clé entière vers une page d’overflow, on peut ne laisser dans le nœud qu’un court préfixe et stocker le reste séparément
- Ainsi, pour vérifier la présence d’une clé ou effectuer une recherche par plage, on commence par examiner le préfixe dans le nœud et l’on ne lit la page d’overflow qu’en cas de nécessité
- Même si cela implique d’allouer des pages supplémentaires, cette méthode peut réduire le coût global des recherches
Pointeurs de nœuds frères
- Certaines implémentations stockent dans chaque nœud des pointeurs vers ses frères gauche et droit
- Cela permet, lors des recherches par plage, de passer directement d’une feuille à sa voisine et de parcourir rapidement des clés consécutives
- Sans ces pointeurs, il faudrait remonter au parent puis redescendre à plusieurs reprises, ce qui augmenterait le coût en E/S
- Comme les plages de clés des nœuds frères ne se chevauchent pas, suivre le pointeur vers le frère droit garantit d’accéder à la « plage de clés suivante »
Variantes de B-Tree
- Il existe de nombreuses variantes, au-delà du B⁺-Tree
- Les « Lazy B-Tree » comme celui de WiredTiger, ainsi que les Lazy-Adaptive Tree, améliorent les performances en mettant les opérations d’écriture en tampon
- Le FD-Tree est une structure conçue pour les SSD, qui tient compte de contraintes physiques comme l’écriture par blocs
- Le Bw-Tree (Buzzword Tree) est une structure optimisée pour une forte concurrence et pour l’accès aux arbres en mémoire
Conclusion
- Entre le concept abstrait de « B⁺-Tree » et une implémentation réelle comme le « format de base de données de SQLite », il existe de nombreuses optimisations et différences de détail
- Les optimisations ne changent pas la complexité en Big-O, mais elles ont un impact majeur sur les performances et l’utilisabilité d’une base de données en conditions réelles
- Au-delà des points présentés ici, chaque système de stockage nécessite beaucoup de réglages fins spécifiques
- Derrière l’idée qu’« il suffit d’un peu d’information supplémentaire » se cachent en réalité une complexité d’implémentation et des difficultés de débogage
- Comme exemple représentant un B-Tree de manière plus réaliste, le diagramme de B-Tree de Designing Data-Intensive Applications est particulièrement marquant
1 commentaires
Commentaire Hacker News
La structure d’une page se compose d’un en-tête, de cellules et de pointeurs d’offset, avec l’avantage de pouvoir stocker des données de taille variable
Excellent article sur les B-trees, avec des animations
Il y a quelques années, j’ai implémenté un B-link Tree récupérable en concurrence à partir des travaux d’Ibrahim Jaluta
J’ai créé un explorateur de pages disque SQLite, ce qui m’a permis de mieux comprendre les B-trees
Il manque des éléments sur les B-link trees, la concurrence et le verrouillage, mais ce serait peut-être plus d’informations que nécessaire
Ancien commentaire : Hacker News
Excellent article, qui explique bien l’importance des détails
Bonne ressource sur l’implémentation des B-trees en Golang
Je suis un grand fan de cet article et j’avais une « compréhension floue » similaire à celle de l’auteur