B-arbre - B-tree

B-arbre
Taper	Arborescence (structure de données)
A inventé	1970
Inventé par	Rudolf Bayer , Edward M. McCreight
Complexité temporelle en grande notation O
Algorithme Moyenne Pire cas Espacer O( n ) O( n ) Chercher O(log n ) O(log n ) Insérer O(log n ) O(log n ) Effacer O(log n ) O(log n )

En informatique , un B-tree est une structure de données arborescente auto-équilibrée qui conserve les données triées et permet des recherches, des accès séquentiels, des insertions et des suppressions en temps logarithmique . Le B-tree généralise l' arbre de recherche binaire , permettant des nœuds avec plus de deux enfants. Contrairement aux autres arbres de recherche binaires auto-équilibrés , le B-tree est bien adapté aux systèmes de stockage qui lisent et écrivent des blocs de données relativement volumineux, tels que des disques. Il est couramment utilisé dans les bases de données et les systèmes de fichiers .

Origine

Les arbres B ont été inventés par Rudolf Bayer et Edward M. McCreight alors qu'ils travaillaient pour Boeing Research Labs , dans le but de gérer efficacement les pages d'index pour les gros fichiers à accès aléatoire. L'hypothèse de base était que les index seraient si volumineux que seuls de petits morceaux de l'arbre pourraient tenir dans la mémoire principale. L'article de Bayer et McCreight, Organisation et maintenance des grands indices ordonnés , a été diffusé pour la première fois en juillet 1970 et publié plus tard dans Acta Informatica .

Bayer et McCreight n'ont jamais expliqué ce que, le cas échéant, le B signifie : Boeing , équilibré , large , touffu et Bayer ont été suggérés. McCreight a déclaré que "plus vous pensez à ce que signifie le B dans les arbres B, mieux vous comprenez les arbres B".

Définition

Selon la définition de Knuth, un B-arbre d'ordre m est un arbre qui satisfait les propriétés suivantes :

1. Chaque nœud a au plus m enfants.
2. Chaque nœud non-feuille (sauf la racine) a au moins ⌈ m /2⌉ nœuds enfants.
3. La racine a au moins deux enfants s'il ne s'agit pas d'un nœud feuille.
4. Un nœud non-feuille avec k enfants contient k − 1 clés.
5. Toutes les feuilles apparaissent au même niveau et ne portent aucune information.

Les clés de chaque nœud interne agissent comme des valeurs de séparation qui divisent ses sous-arbres. Par exemple, si un nœud interne a 3 nœuds enfants (ou sous-arbres) alors il doit avoir 2 clés : un ₁ et un ₂ . Toutes les valeurs dans le sous - arbre gauche sera inférieure à un ₁ , toutes les valeurs dans la sous - arborescence du milieu sera comprise entre un ₁ et un ₂ , et toutes les valeurs dans la sous - arborescence de droite sera supérieure à une ₂ .

Nœuds internes

Les nœuds internes sont tous des nœuds à l'exception des nœuds feuilles et du nœud racine. Ils sont généralement représentés comme un ensemble ordonné d'éléments et de pointeurs enfants. Chaque nœud interne contient un maximum de U enfants et un minimum de L enfants. Ainsi, le nombre d'éléments est toujours inférieur de 1 au nombre de pointeurs fils (le nombre d'éléments est compris entre L -1 et U -1). U doit être soit 2 L soit 2 L -1 ; par conséquent, chaque nœud interne est au moins à moitié plein. La relation entre U et L implique que deux nœuds à moitié pleins peuvent être joints pour former un nœud légal, et un nœud complet peut être divisé en deux nœuds légaux (s'il y a de la place pour pousser un élément vers le haut dans le parent). Ces propriétés permettent de supprimer et d'insérer de nouvelles valeurs dans un B-tree et d'ajuster l'arbre pour préserver les propriétés du B-tree.

Le nœud racine

Le nombre d'enfants du nœud racine a la même limite supérieure que les nœuds internes, mais n'a pas de limite inférieure. Par exemple, lorsqu'il y a moins de L -1 éléments dans l'arbre entier, la racine sera le seul nœud de l'arbre sans aucun enfant.

Nœuds feuilles

Dans la terminologie de Knuth, les nœuds feuilles ne transportent aucune information. Les nœuds internes qui sont un niveau au-dessus des feuilles sont ce que d'autres auteurs appelleraient des « feuilles » : ces nœuds ne stockent que des clés (au plus m -1, et au moins m /2-1 s'ils ne sont pas la racine) et pointeurs vers des nœuds ne portant aucune information.

Un arbre B de profondeur n +1 peut contenir environ U fois plus d'éléments qu'un arbre B de profondeur n , mais le coût des opérations de recherche, d'insertion et de suppression augmente avec la profondeur de l'arbre. Comme pour tout arbre équilibré, le coût augmente beaucoup plus lentement que le nombre d'éléments.

Certains arbres équilibrés stockent des valeurs uniquement au niveau des nœuds feuilles et utilisent différents types de nœuds pour les nœuds feuilles et les nœuds internes. Les arbres B conservent des valeurs dans chaque nœud de l'arbre, à l'exception des nœuds feuilles.

Différences de terminologie

La littérature sur les arbres B n'est pas uniforme dans sa terminologie.

Bayer et McCreight (1972), Comer (1979) et d'autres définissent l' ordre du B-tree comme le nombre minimum de clés dans un nœud non racine. souligne que la terminologie est ambiguë car le nombre maximum de clés n'est pas clair. Une commande 3 B-tree peut contenir un maximum de 6 clés ou un maximum de 7 clés. Knuth (1998) évite le problème en définissant l' ordre comme étant le nombre maximum d'enfants (qui est un de plus que le nombre maximum de clés).

Le terme feuille est également incohérent. Bayer et McCreight (1972) considéraient que le niveau feuille était le niveau de clés le plus bas, mais Knuth considérait que le niveau feuille était un niveau en dessous des clés les plus basses. Il existe de nombreux choix de mise en œuvre possibles. Dans certaines conceptions, les feuilles peuvent contenir l'intégralité de l'enregistrement de données ; dans d'autres conceptions, les feuilles ne peuvent contenir que des pointeurs vers l'enregistrement de données. Ces choix ne sont pas fondamentaux pour l'idée d'un arbre B.

Par souci de simplicité, la plupart des auteurs supposent qu'il existe un nombre fixe de clés qui tiennent dans un nœud. L'hypothèse de base est que la taille de la clé est fixe et la taille du nœud est fixe. En pratique, des clés de longueur variable peuvent être utilisées.

Description informelle

Dans les arbres B, les nœuds internes ( non-feuilles ) peuvent avoir un nombre variable de nœuds enfants dans une plage prédéfinie. Lorsque des données sont insérées ou supprimées d'un nœud, son nombre de nœuds enfants change. Afin de maintenir la plage prédéfinie, les nœuds internes peuvent être joints ou divisés. Étant donné qu'une plage de nœuds enfants est autorisée, les arbres B n'ont pas besoin d'être rééquilibrés aussi fréquemment que les autres arbres de recherche à équilibrage automatique, mais peuvent gaspiller de l'espace, car les nœuds ne sont pas entièrement pleins. Les limites inférieure et supérieure du nombre de nœuds enfants sont généralement fixées pour une implémentation particulière. Par exemple, dans un arbre 2-3 (parfois appelé arbre B 2-3 ), chaque nœud interne peut n'avoir que 2 ou 3 nœuds enfants.

Chaque nœud interne d'un B-tree contient un certain nombre de clés. Les clés agissent comme des valeurs de séparation qui divisent ses sous-arbres . Par exemple, si un nœud interne a 3 nœuds enfants (ou sous-arbres) alors il doit avoir 2 clés : et . Toutes les valeurs du sous-arbre le plus à gauche seront inférieures à , toutes les valeurs du sous-arbre du milieu seront comprises entre et , et toutes les valeurs du sous-arbre le plus à droite seront supérieures à . ${\style d'affichage a_{1}}$${\style d'affichage a_{2}}$${\style d'affichage a_{1}}$${\style d'affichage a_{1}}$${\style d'affichage a_{2}}$${\style d'affichage a_{2}}$

Habituellement, le nombre de clés est choisi pour varier entre et , où est le nombre minimum de clés, et est le degré minimum ou le facteur de branchement de l'arbre. En pratique, les clés occupent le plus de place dans un nœud. Le facteur 2 garantira que les nœuds peuvent être divisés ou combinés. Si un nœud interne a des clés, l'ajout d'une clé à ce nœud peut être accompli en divisant le nœud de clé hypothétique en deux nœuds de clé et en déplaçant la clé qui aurait été au milieu vers le nœud parent. Chaque nœud divisé a le nombre minimum de clés requis. De même, si un nœud interne et son voisin ont chacun des clés, alors une clé peut être supprimée du nœud interne en la combinant avec son voisin. La suppression de la clé ferait en sorte que le nœud interne ait des clés ; rejoindre le voisin ajouterait des clés plus une clé de plus apportée par le parent du voisin. Le résultat est un nœud de clés entièrement complet . ${\style d'affichage d}$${\style d'affichage 2d}$${\style d'affichage d}$${\style d'affichage d+1}$${\style d'affichage 2d}$${\style d'affichage 2j+1}$${\style d'affichage d}$${\style d'affichage d}$${\style d'affichage d-1}$${\style d'affichage d}$${\style d'affichage 2d}$

Le nombre de branches (ou de nœuds enfants) d'un nœud sera supérieur au nombre de clés stockées dans le nœud. Dans un arbre B 2-3, les nœuds internes stockeront soit une clé (avec deux nœuds enfants), soit deux clés (avec trois nœuds enfants). Un arbre B est parfois décrit avec les paramètres - ou simplement avec l'ordre de branchement le plus élevé, . ${\style d'affichage (j+1)}$${\style d'affichage (2j+1)}$${\style d'affichage (2j+1)}$

Un arbre B est maintenu équilibré après l'insertion en divisant un nœud potentiellement trop rempli, de clés, en deux frères et sœurs et en insérant la clé de valeur moyenne dans le parent. La profondeur n'augmente que lorsque la racine est fendue, maintenant l'équilibre. De même, un arbre B est maintenu équilibré après la suppression en fusionnant ou en redistribuant les clés entre frères et sœurs pour maintenir le minimum de clés pour les nœuds non racines. Une fusion réduit le nombre de clés dans le parent, l'obligeant potentiellement à fusionner ou à redistribuer les clés avec ses frères et sœurs, et ainsi de suite. Le seul changement de profondeur se produit lorsque la racine a deux enfants, de et (de manière transitoire) , auquel cas les deux frères et le parent sont fusionnés, réduisant la profondeur d'un. ${\style d'affichage 2j+1}$${\style d'affichage d}$${\style d'affichage d}$${\style d'affichage d}$${\style d'affichage d-1}$

Cette profondeur augmentera lentement au fur et à mesure que des éléments sont ajoutés à l'arbre, mais une augmentation de la profondeur globale est peu fréquente et a pour résultat que tous les nœuds feuilles sont un nœud plus éloigné de la racine.

Les arbres B présentent des avantages substantiels par rapport aux implémentations alternatives lorsque le temps d'accès aux données d'un nœud dépasse largement le temps passé à traiter ces données, car le coût d'accès au nœud peut alors être amorti sur plusieurs opérations au sein du nœud. Cela se produit généralement lorsque les données du nœud se trouvent dans un stockage secondaire tel que des lecteurs de disque . En maximisant le nombre de clés au sein de chaque nœud interne , la hauteur de l'arbre diminue et le nombre d'accès aux nœuds coûteux est réduit. De plus, le rééquilibrage de l'arbre se produit moins souvent. Le nombre maximal de nœuds enfants dépend des informations qui doivent être stockées pour chaque nœud enfant et de la taille d'un bloc de disque complet ou d'une taille analogue dans le stockage secondaire. Alors que 2 à 3 arbres B sont plus faciles à expliquer, les arbres B pratiques utilisant un stockage secondaire nécessitent un grand nombre de nœuds enfants pour améliorer les performances.

Variantes

Le terme B-tree peut se référer à un dessin spécifique ou il peut se référer à une classe générale de dessins. Au sens étroit, un B-tree stocke des clés dans ses nœuds internes mais n'a pas besoin de stocker ces clés dans les enregistrements des feuilles. La classe générale comprend des variantes telles que l' arbre B+ , l' arbre B ^* et l'arbre B ^*+ .

• Dans l' arbre B+ , des copies des clés sont stockées dans les nœuds internes ; les clés et les enregistrements sont stockés dans des feuilles ; de plus, un nœud feuille peut inclure un pointeur vers le nœud feuille suivant pour accélérer l'accès séquentiel.
• L' arbre B ^* équilibre davantage de nœuds internes voisins pour garder les nœuds internes plus denses. Cette variante garantit que les nœuds non racines sont remplis au moins aux 2/3 au lieu de 1/2. Comme la partie la plus coûteuse de l'opération d'insertion du nœud dans le B-tree est la division du nœud, les B ^* -trees sont créés pour reporter l'opération de division aussi longtemps qu'ils le peuvent. Pour maintenir cela, au lieu de diviser immédiatement un nœud lorsqu'il est plein, ses clés sont partagées avec un nœud voisin. Cette opération de débordement est moins coûteuse à faire que la division, car elle ne nécessite que de déplacer les clés entre les nœuds existants, sans allouer de mémoire pour un nouveau. Pour l'insertion, il est d'abord vérifié si le nœud a de l'espace libre, et si c'est le cas, la nouvelle clé est simplement insérée dans le nœud. Cependant, si le nœud est plein (il a m − 1 clés, où m est l'ordre de l'arbre en tant que nombre maximal de pointeurs vers les sous-arbres d'un nœud), il faut vérifier si le bon frère existe et a de l'espace libre . Si le frère de droite a j < m − 1 clés, alors les clés sont redistribuées entre les deux nœuds frères aussi uniformément que possible. À cette fin, m - 1 clés du nœud actuel, la nouvelle clé insérée, une clé du nœud parent et j clés du nœud frère sont considérées comme un tableau ordonné de m + j + 1 clés. Le tableau est divisé par deux, de sorte que ⌊ ( m + j + 1)/2 les clés les plus basses restent dans le nœud actuel, la clé suivante (du milieu) est insérée dans le parent et le reste va au frère de droite. (La clé nouvellement insérée peut se retrouver dans l'un des trois endroits.) La situation lorsque le frère de droite est plein et que la gauche ne l'est pas est analogue. Lorsque les deux nœuds frères sont pleins, les deux nœuds (nœud actuel et un frère) sont divisés en trois et une clé supplémentaire est déplacée vers le haut de l'arborescence, vers le nœud parent. Si le parent est plein, l'opération de débordement/de division se propage vers le nœud racine. Cependant, la suppression de nœuds est un peu plus complexe que l'insertion.
• L' arbre B ^*+ combine les principales caractéristiques de l'arbre B+ et de l' arbre B ^* .
• Les arbres B peuvent être transformés en arbres de statistiques d'ordre pour permettre des recherches rapides du Nième enregistrement dans l'ordre des clés, ou compter le nombre d'enregistrements entre deux enregistrements et diverses autres opérations connexes.

Utilisation de B-tree dans les bases de données

Il est temps de rechercher un fichier trié

Habituellement, les algorithmes de tri et de recherche ont été caractérisés par le nombre d'opérations de comparaison qui doivent être effectuées en utilisant la notation d'ordre . Une recherche binaire d'une table triée avec N enregistrements, par exemple, peut être effectuée dans environ ⌈ log ₂ N ⌉ comparaisons. Si la table avait 1 000 000 d'enregistrements, alors un enregistrement spécifique pourrait être localisé avec au plus 20 comparaisons : ⌈ log ₂ (1 000 000) ⌉ = 20 .

Les grandes bases de données ont historiquement été conservées sur des lecteurs de disque. Le temps de lecture d'un enregistrement sur un lecteur de disquette dépasse de loin le temps nécessaire pour comparer les clés une fois l'enregistrement disponible. Le temps de lecture d'un enregistrement à partir d'un lecteur de disque implique un temps de recherche et un délai de rotation. Le temps de recherche peut être de 0 à 20 millisecondes ou plus, et le retard de rotation est en moyenne d'environ la moitié de la période de rotation. Pour un lecteur de 7 200 tr/min, la période de rotation est de 8,33 millisecondes. Pour un disque tel que le Seagate ST3500320NS, le temps de recherche de piste à piste est de 0,8 milliseconde et le temps de recherche de lecture moyen est de 8,5 millisecondes. Pour plus de simplicité, supposons que la lecture à partir du disque prend environ 10 millisecondes.

Naïvement, alors, le temps de localiser un enregistrement sur un million prendrait 20 lectures de disque fois 10 millisecondes par disque lu, soit 0,2 seconde.

Le temps ne sera pas si mauvais car les enregistrements individuels sont regroupés dans un bloc de disque . Un bloc de disque peut faire 16 kilo-octets. Si chaque enregistrement est de 160 octets, alors 100 enregistrements pourraient être stockés dans chaque bloc. Le temps de lecture du disque ci-dessus était en fait pour un bloc entier. Une fois la tête de disque en place, un ou plusieurs blocs de disque peuvent être lus avec peu de retard. Avec 100 enregistrements par bloc, les 6 dernières comparaisons environ n'ont pas besoin de faire de lecture de disque - les comparaisons sont toutes dans le dernier bloc de disque lu.

Pour accélérer davantage la recherche, les 13 à 14 premières comparaisons (qui nécessitent chacune un accès disque) doivent être accélérées.

Un index accélère la recherche

Un index B-tree crée une structure arborescente à plusieurs niveaux qui divise une base de données en blocs ou pages de taille fixe. Chaque niveau de cette arborescence peut être utilisé pour lier ces pages via un emplacement d'adresse, permettant à une page (appelée nœud ou page interne) de se référer à une autre avec des pages feuilles au niveau le plus bas. Une page est généralement le point de départ de l'arbre, ou la "racine". C'est là que la recherche d'une clé particulière commencerait, parcourant un chemin qui se termine par une feuille. La plupart des pages de cette structure seront des pages feuilles qui se réfèrent finalement à des lignes de tableau spécifiques.

Une amélioration significative des performances peut être réalisée avec un indice B-tree . Étant donné que chaque nœud (ou page interne) peut avoir plus de deux enfants, un index B-tree aura généralement une hauteur plus courte (la distance de la racine à la feuille la plus éloignée) qu'un arbre de recherche binaire. Dans l'exemple ci-dessus, les lectures de disque initiales ont réduit la plage de recherche d'un facteur de deux. Cela peut être considérablement amélioré en créant un index auxiliaire qui contient le premier enregistrement de chaque bloc de disque (parfois appelé index sparse ). Cet index auxiliaire représenterait 1% de la taille de la base de données d'origine, mais il peut être recherché plus rapidement. Trouver une entrée dans l'index auxiliaire nous indiquerait quel bloc rechercher dans la base de données principale ; après avoir recherché l'index auxiliaire, nous n'aurions à rechercher que ce bloc de la base de données principale, au prix d'une lecture de disque supplémentaire. L'index contiendrait 10 000 entrées, il faudrait donc au plus 14 comparaisons. Comme la base de données principale, les six dernières comparaisons environ dans l'index auxiliaire seraient sur le même bloc de disque. L'index peut être recherché en environ huit lectures de disque, et l'enregistrement souhaité peut être consulté en neuf lectures de disque.

L'astuce de création d'un index auxiliaire peut être répétée pour créer un index auxiliaire à l'index auxiliaire. Cela ferait un index aux-aux qui n'aurait besoin que de 100 entrées et tiendrait dans un bloc de disque.

Au lieu de lire 14 blocs de disque pour trouver l'enregistrement souhaité, nous n'avons besoin de lire que 3 blocs. Ce blocage est l'idée centrale derrière la création de l'arbre B, où les blocs de disque remplissent une hiérarchie de niveaux pour constituer l'index. La lecture et la recherche du premier (et seul) bloc de l'index aux-aux qui est la racine de l'arbre identifie le bloc pertinent dans aux-index au niveau inférieur. La lecture et la recherche de ce bloc aux-index identifient le bloc pertinent à lire, jusqu'à ce que le niveau final, appelé niveau feuille, identifie un enregistrement dans la base de données principale. Au lieu de 150 millisecondes, nous n'avons besoin que de 30 millisecondes pour obtenir l'enregistrement.

Les indices auxiliaires ont transformé le problème de recherche d'une recherche binaire nécessitant approximativement log ₂ N lectures de disque à une seule ne nécessitant que log _b N lectures de disque où b est le facteur de blocage (le nombre d'entrées par bloc : b = 100 entrées par bloc dans notre exemple ; log ₁₀₀ 1 000 000 = 3 lectures).

En pratique, si la base de données principale est fréquemment recherchée, l'index aux-aux et une grande partie de l'index aux peuvent résider dans un cache disque , de sorte qu'ils n'entraîneraient pas de lecture de disque. Le B-tree reste l'implémentation d'index standard dans presque toutes les bases de données relationnelles , et de nombreuses bases de données non relationnelles les utilisent également.

Insertions et suppressions

Si la base de données ne change pas, la compilation de l'index est simple à faire et l'index n'a jamais besoin d'être modifié. S'il y a des changements, la gestion de la base de données et de son index devient plus compliquée.

La suppression d'enregistrements d'une base de données est relativement simple. L'index peut rester le même et l'enregistrement peut simplement être marqué comme supprimé. La base de données reste dans l'ordre trié. S'il y a un grand nombre de suppressions, la recherche et le stockage deviennent moins efficaces.

Les insertions peuvent être très lentes dans un fichier séquentiel trié car il faut faire de la place pour l'enregistrement inséré. L'insertion d'un enregistrement avant le premier enregistrement nécessite de décaler tous les enregistrements d'un. Une telle opération est tout simplement trop coûteuse pour être pratique. Une solution consiste à laisser des espaces. Au lieu de regrouper de manière dense tous les enregistrements dans un bloc, le bloc peut avoir de l'espace libre pour permettre des insertions ultérieures. Ces espaces seraient marqués comme s'il s'agissait d'enregistrements « supprimés ».

Les insertions et les suppressions sont rapides tant que de l'espace est disponible sur un bloc. Si une insertion ne tient pas sur le bloc, alors de l'espace libre sur un bloc voisin doit être trouvé et les indices auxiliaires ajustés. L'espoir est que suffisamment d'espace soit disponible à proximité, de sorte que beaucoup de blocs n'aient pas besoin d'être réorganisés. Alternativement, certains blocs de disque hors séquence peuvent être utilisés.

Avantages de l'utilisation de B-tree pour les bases de données

L'arbre B utilise toutes les idées décrites ci-dessus. En particulier, un arbre B :

• conserve les clés dans l'ordre trié pour un parcours séquentiel
• utilise un index hiérarchique pour minimiser le nombre de lectures de disque
• utilise des blocs partiellement pleins pour accélérer les insertions et les suppressions
• maintient l'index équilibré avec un algorithme récursif

De plus, un arbre B minimise les déchets en s'assurant que les nœuds intérieurs sont au moins à moitié pleins. Un B-tree peut gérer un nombre arbitraire d'insertions et de suppressions.

Hauteurs dans le meilleur des cas et dans le pire des cas

Soit h ≥ –1 la hauteur du B-tree classique (voir Arbre (structure de données) § Terminologie pour la définition de la hauteur de l'arbre). Soit n ≥ 0 le nombre d'entrées dans l'arbre. Soit m le nombre maximum d'enfants qu'un nœud peut avoir. Chaque nœud peut avoir au plus m -1 clés.

On peut montrer (par récurrence par exemple) qu'un B-arbre de hauteur h avec tous ses nœuds complètement remplis a n = m ^{h +1} –1 entrées. Par conséquent, la hauteur optimale (c'est-à-dire la hauteur minimale) d'un arbre B est :

${\displaystyle h_{\mathrm {min} }=\lceil \log _{m}(n+1)\rceil -1}$

Soit le nombre minimum d'enfants qu'un nœud interne (non racine) peut avoir. Pour un arbre B ordinaire,${\style d'affichage d}$${\displaystyle d=\left\lceil m/2\right\rceil .}$

Comer (1979) et Cormen et al. (2001) donnent la hauteur dans le pire des cas (la hauteur maximale) d'un arbre B comme

${\displaystyle h_{\mathrm {max} }=\left\lfloor \log _{d}{\frac {n+1}{2}}\right\rfloor .}$

Algorithmes

Chercher

La recherche est similaire à la recherche dans un arbre de recherche binaire. En partant de la racine, l'arbre est parcouru récursivement de haut en bas. A chaque niveau, la recherche réduit son champ de vision au pointeur enfant (sous-arbre) dont la plage inclut la valeur de recherche. La plage d'un sous-arbre est définie par les valeurs, ou clés, contenues dans son nœud parent. Ces valeurs limites sont également appelées valeurs de séparation.

La recherche binaire est généralement (mais pas nécessairement) utilisée dans les nœuds pour trouver les valeurs de séparation et l'arbre enfant d'intérêt.

Insertion

Toutes les insertions commencent à un nœud feuille. Pour insérer un nouvel élément, recherchez dans l'arborescence le nœud feuille où le nouvel élément doit être ajouté. Insérez le nouvel élément dans ce nœud en procédant comme suit :

1. Si le nœud contient moins que le nombre maximal d'éléments autorisé, il y a de la place pour le nouvel élément. Insérez le nouvel élément dans le nœud, en gardant les éléments du nœud ordonnés.
2. Sinon, le nœud est plein, divisez-le également en deux nœuds ainsi :
   1. Une seule médiane est choisie parmi les éléments de la feuille et le nouvel élément.
   2. Les valeurs inférieures à la médiane sont placées dans le nouveau nœud gauche et les valeurs supérieures à la médiane sont placées dans le nouveau nœud droit, la médiane agissant comme une valeur de séparation.
   3. La valeur de séparation est insérée dans le parent du nœud, ce qui peut entraîner sa division, et ainsi de suite. Si le nœud n'a pas de parent (c'est-à-dire que le nœud était la racine), créez une nouvelle racine au-dessus de ce nœud (en augmentant la hauteur de l'arbre).

Si le fractionnement va jusqu'à la racine, il crée une nouvelle racine avec une seule valeur de séparateur et deux enfants, c'est pourquoi la limite inférieure de la taille des nœuds internes ne s'applique pas à la racine. Le nombre maximum d'éléments par nœud est U -1. Lorsqu'un nœud est divisé, un élément se déplace vers le parent, mais un élément est ajouté. Ainsi, il doit être possible de diviser le nombre maximum U -1 d'éléments en deux nœuds légaux. Si ce nombre est impair, alors U =2 L et l'un des nouveaux nœuds contient ( U −2)/2 = L −1 éléments, et est donc un nœud légal, et l'autre contient un élément de plus, et donc c'est légal aussi. Si U −1 est pair, alors U =2 L −1, il y a donc 2 L −2 éléments dans le nœud. La moitié de ce nombre est L -1, qui est le nombre minimum d'éléments autorisés par nœud.

Un algorithme alternatif prend en charge un seul passage dans l'arbre de la racine au nœud où l'insertion aura lieu, divisant de manière préventive tous les nœuds complets rencontrés sur le chemin. Cela évite d'avoir à rappeler les nœuds parents en mémoire, ce qui peut être coûteux si les nœuds se trouvent sur un stockage secondaire. Cependant, pour utiliser cet algorithme, nous devons pouvoir envoyer un élément au parent et diviser les U -2 éléments restants en deux nœuds légaux, sans ajouter de nouvel élément. Cela nécessite U = 2 L plutôt que U = 2 L -1, ce qui explique pourquoi certains manuels imposent cette exigence dans la définition des B-arbres.

Effacement

Il existe deux stratégies populaires pour la suppression d'un arbre B.

1. Localisez et supprimez l'élément, puis restructurez l'arborescence pour conserver ses invariants, OU
2. Faites un seul passage dans l'arborescence, mais avant d'entrer (visiter) un nœud, restructurer l'arborescence de sorte qu'une fois la clé à supprimer rencontrée, elle puisse être supprimée sans nécessiter de nouvelle restructuration

L'algorithme ci-dessous utilise la première stratégie.

Il y a deux cas particuliers à considérer lors de la suppression d'un élément :

1. L'élément dans un nœud interne est un séparateur pour ses nœuds enfants
2. La suppression d'un élément peut mettre son nœud sous le nombre minimum d'éléments et d'enfants

Les procédures pour ces cas sont dans l'ordre ci-dessous.

Suppression d'un nœud feuille

1. Recherchez la valeur à supprimer.
2. Si la valeur se trouve dans un nœud feuille, supprimez-la simplement du nœud.
3. En cas de dépassement de capacité, rééquilibrez l'arborescence comme décrit dans la section "Rééquilibrage après suppression" ci-dessous.

Suppression d'un nœud interne

Chaque élément d'un nœud interne agit comme une valeur de séparation pour deux sous-arbres, nous devons donc trouver un remplaçant pour la séparation. Notez que le plus grand élément du sous-arbre de gauche est toujours inférieur au séparateur. De même, le plus petit élément du sous-arbre de droite est toujours plus grand que le séparateur. Ces deux éléments se trouvent dans des nœuds feuilles, et l'un ou l'autre peut être le nouveau séparateur pour les deux sous-arbres. Décrit algorithmiquement ci-dessous :

1. Choisissez un nouveau séparateur (soit le plus grand élément du sous-arbre gauche, soit le plus petit élément du sous-arbre droit), supprimez-le du nœud feuille dans lequel il se trouve et remplacez l'élément à supprimer par le nouveau séparateur.
2. L'étape précédente a supprimé un élément (le nouveau séparateur) d'un nœud feuille. Si ce nœud feuille est maintenant déficient (a moins que le nombre requis de nœuds), alors rééquilibrez l'arbre à partir du nœud feuille.

Rééquilibrage après suppression

Le rééquilibrage commence à partir d'une feuille et se poursuit vers la racine jusqu'à ce que l'arbre soit équilibré. Si la suppression d'un élément d'un nœud l'a ramené sous la taille minimale, alors certains éléments doivent être redistribués pour ramener tous les nœuds au minimum. Habituellement, la redistribution implique le déplacement d'un élément d'un nœud frère qui a plus que le nombre minimum de nœuds. Cette opération de redistribution s'appelle une rotation . Si aucun frère ne peut épargner un élément, alors le nœud déficient doit être fusionné avec un frère. La fusion fait perdre au parent un élément séparateur, de sorte que le parent peut devenir déficient et nécessiter un rééquilibrage. La fusion et le rééquilibrage peuvent se poursuivre jusqu'à la racine. Étant donné que le nombre minimal d'éléments ne s'applique pas à la racine, faire de la racine le seul nœud déficient n'est pas un problème. L'algorithme pour rééquilibrer l'arbre est le suivant :

• Si le frère droit du nœud déficient existe et a plus que le nombre minimum d'éléments, alors tournez à gauche
  1. Copiez le séparateur du parent à la fin du nœud déficient (le séparateur descend ; le nœud déficient a maintenant le nombre minimum d'éléments)
  2. Remplacez le séparateur dans le parent par le premier élément du frère de droite (le frère de droite perd un nœud mais a toujours au moins le nombre minimum d'éléments)
  3. L'arbre est maintenant équilibré
• Sinon, si le frère gauche du nœud déficient existe et a plus que le nombre minimum d'éléments, alors tournez à droite
  1. Copiez le séparateur du parent au début du nœud déficient (le séparateur descend ; le nœud déficient a maintenant le nombre minimum d'éléments)
  2. Remplacez le séparateur dans le parent par le dernier élément du frère gauche (le frère gauche perd un nœud mais a toujours au moins le nombre minimum d'éléments)
  3. L'arbre est maintenant équilibré
• Sinon, si les deux frères immédiats n'ont que le nombre minimum d'éléments, alors fusionner avec un frère prenant en sandwich leur séparateur retiré de leur parent
  1. Copiez le séparateur à la fin du nœud de gauche (le nœud de gauche peut être le nœud déficient ou il peut s'agir du frère avec le nombre minimum d'éléments)
  2. Déplacez tous les éléments du nœud de droite vers le nœud de gauche (le nœud de gauche a maintenant le nombre maximum d'éléments et le nœud de droite est vide)
  3. Supprimer le séparateur du parent avec son enfant droit vide (le parent perd un élément)
     • Si le parent est la racine et n'a plus d'éléments, libérez-le et faites du nœud fusionné la nouvelle racine (l'arbre devient moins profond)
     • Sinon, si le parent a moins que le nombre requis d'éléments, alors rééquilibrez le parent

Remarque : Les opérations de rééquilibrage sont différentes pour les arbres B+ (par exemple, la rotation est différente car le parent a une copie de la clé) et B ^* -tree (par exemple, trois frères et sœurs sont fusionnés en deux frères et sœurs).

Accès séquentiel

Alors que les bases de données fraîchement chargées ont tendance à avoir un bon comportement séquentiel, ce comportement devient de plus en plus difficile à maintenir à mesure qu'une base de données se développe, ce qui entraîne des problèmes d'E/S et de performances plus aléatoires.

Construction initiale

Un cas particulier courant consiste à ajouter une grande quantité de données pré-triées dans un arbre B initialement vide. S'il est tout à fait possible d'effectuer simplement une série d'insertions successives, l'insertion de données triées aboutit à un arbre composé presque entièrement de nœuds à moitié pleins. Au lieu de cela, un algorithme spécial de « chargement en masse » peut être utilisé pour produire un arbre plus efficace avec un facteur de branchement plus élevé.

Lorsque l'entrée est triée, toutes les insertions sont au bord le plus à droite de l'arbre, et en particulier chaque fois qu'un nœud est divisé, nous sommes assurés qu'aucune autre insertion n'aura lieu dans la moitié gauche. Lors du chargement en masse, nous en profitons, et au lieu de diviser les nœuds trop pleins de manière égale, divisez-les aussi inégalement que possible : laissez le nœud gauche complètement plein et créez un nœud droit avec zéro clé et un enfant (en violation de l'habituel B- règles d'arborescence).

A la fin du chargement en masse, l'arbre est composé presque entièrement de nœuds complètement pleins ; seul le nœud le plus à droite sur chaque niveau peut être moins que plein. Étant donné que ces nœuds peuvent également être moins qu'à moitié pleins, pour rétablir les règles normales de l'arbre B, combinez ces nœuds avec leurs frères et sœurs gauches (garantis pleins) et divisez les clés pour produire deux nœuds au moins à moitié pleins. Le seul nœud qui n'a pas de frère gauche complet est la racine, qui est autorisée à être moins qu'à moitié pleine.

Dans les systèmes de fichiers

En plus de son utilisation dans les bases de données, le B-tree (ou § Variants ) est également utilisé dans les systèmes de fichiers pour permettre un accès aléatoire rapide à un bloc arbitraire dans un fichier particulier. Le problème de base est de transformer l' adresse de bloc de fichier en une adresse de bloc de disque (ou peut-être en une adresse de secteur de culasse ). ${\style d'affichage i}$

Certains systèmes d'exploitation exigent que l'utilisateur alloue la taille maximale du fichier lors de sa création. Le fichier peut ensuite être alloué sous forme de blocs de disque contigus. Dans ce cas, pour convertir l'adresse de bloc de fichier en une adresse de bloc de disque, le système d'exploitation ajoute simplement l'adresse de bloc de fichier à l'adresse du premier bloc de disque constituant le fichier. Le schéma est simple, mais le fichier ne peut pas dépasser sa taille créée. ${\style d'affichage i}$${\style d'affichage i}$

D'autres systèmes d'exploitation permettent à un fichier de croître. Les blocs de disque résultants peuvent ne pas être contigus, donc le mappage des blocs logiques aux blocs physiques est plus complexe.

MS-DOS , par exemple, utilisait une simple table d'allocation de fichiers (FAT). Le FAT a une entrée pour chaque bloc de disque, et cette entrée identifie si son bloc est utilisé par un fichier et si oui, quel bloc (le cas échéant) est le prochain bloc de disque du même fichier. Ainsi, l'allocation de chaque fichier est représentée sous forme de liste chaînée dans le tableau. Afin de trouver l'adresse de disque du bloc de fichier , le système d'exploitation (ou l'utilitaire de disque) doit suivre séquentiellement la liste chaînée du fichier dans le FAT. Pire, pour trouver un bloc disque libre, il doit scanner séquentiellement le FAT. Pour MS-DOS, ce n'était pas une pénalité énorme car les disques et les fichiers étaient petits et le FAT avait peu d'entrées et des chaînes de fichiers relativement courtes. Dans le système de fichiers FAT12 (utilisé sur les disquettes et les premiers disques durs), il n'y avait pas plus de 4 080 entrées, et le FAT résidait généralement en mémoire. Au fur et à mesure que les disques grossissaient, l'architecture FAT a commencé à faire face à des pénalités. Sur un disque volumineux utilisant FAT, il peut être nécessaire d'effectuer des lectures de disque pour connaître l'emplacement du disque d'un bloc de fichier à lire ou à écrire. ${\style d'affichage i}$

TOPS-20 (et éventuellement TENEX ) a utilisé un arbre de niveau 0 à 2 qui présente des similitudes avec un arbre B. Un bloc de disque était composé de 512 mots de 36 bits. Si le fichier tient dans un bloc de mots de 512 (2 ⁹ ), alors le répertoire de fichiers pointera vers ce bloc de disque physique. Si le fichier tient dans 2 ¹⁸ mots, alors le répertoire pointerait vers un index aux; les 512 mots de cet index seraient soit NULL (le bloc n'est pas alloué) soit pointaient sur l'adresse physique du bloc. Si le fichier tient en 2 ²⁷ mots, alors le répertoire pointe vers un bloc contenant un index aux-aux ; chaque entrée serait soit NULL, soit pointerait sur un index aux. Par conséquent, le bloc de disque physique pour un fichier de 2 ²⁷ mots pourrait être situé dans deux lectures de disque et lu sur la troisième.

Le système de fichiers d'Apple HFS+ , NTFS de Microsoft , AIX (jfs2) et certains systèmes de fichiers Linux , tels que btrfs et Ext4 , utilisent des B-trees.

^Les arbres B ^* sont utilisés dans les systèmes de fichiers HFS et Reiser4 .

Le système de fichiers HAMMER de DragonFly BSD utilise un arbre B+ modifié.

Performance

Un arbre B croît plus lentement avec la quantité de données croissante que la linéarité d'une liste chaînée. Par rapport à une liste de sauts , les deux structures ont les mêmes performances, mais le B-tree s'adapte mieux à la croissance de n . Un T-tree , pour les systèmes de base de données de mémoire principale , est similaire mais plus compact.

Variantes

Accès simultané

Lehman et Yao ont montré que tous les verrous de lecture pouvaient être évités (et donc l'accès concurrent grandement amélioré) en liant les blocs de l'arbre à chaque niveau avec un pointeur "suivant". Il en résulte une structure arborescente où les opérations d'insertion et de recherche descendent de la racine à la feuille. Les verrous en écriture ne sont requis que lorsqu'un bloc d'arborescence est modifié. Cela maximise la simultanéité d'accès par plusieurs utilisateurs, une considération importante pour les bases de données et/ou d'autres méthodes de stockage ISAM basées sur l'arbre B. Le coût associé à cette amélioration est que les pages vides ne peuvent pas être supprimées du btree pendant les opérations normales. (Cependant, consultez diverses stratégies pour implémenter la fusion de nœuds et le code source sur.)

Le brevet américain 5283894, accordé en 1994, semble montrer un moyen d'utiliser une « méthode d'accès méta » pour permettre l'accès et la modification simultanés de l'arborescence B+ sans verrous. La technique accède à l'arborescence « vers le haut » pour les recherches et les mises à jour au moyen d'index supplémentaires en mémoire qui pointent vers les blocs de chaque niveau du cache de blocs. Aucune réorganisation pour les suppressions n'est nécessaire et il n'y a pas de pointeurs « suivant » dans chaque bloc comme dans Lehman et Yao.

Algorithmes parallèles

Étant donné que les arbres B ont une structure similaire aux arbres rouge-noir , des algorithmes parallèles pour les arbres rouge-noir peuvent également être appliqués aux arbres B.

Voir également

• arbre B+
• R-arbre
• Arbre rouge-noir
• 2-3 arbres
• 2-3-4 arbre

Remarques

Les références

Général

• Bayer, R. ; McCreight, E. (1972), "Organization and Maintenance of Large Ordered Indexes" (PDF) , Acta Informatica , 1 (3) : 173-189, doi : 10.1007/bf00288683 , S2CID  29859053
• Comer, Douglas (juin 1979), "The Ubiquitous B-Tree", Computing Surveys , 11 (2) : 123-137, doi : 10.1145/356770.356776 , ISSN  0360-0300 , S2CID  101673.
• Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2001), Introduction aux algorithmes (deuxième éd.), MIT Press et McGraw-Hill, pp. 434-454, ISBN 0-262-03293-7. Chapitre 18: B-Trees.
• Folk, Michael J.; Zoellick, Bill (1992), Structures de fichiers (2e éd.), Addison-Wesley, ISBN 0-201-55713-4
• Knuth, Donald (1998), Tri et recherche , L'art de la programmation informatique , Volume 3 (deuxième éd.), Addison-Wesley, ISBN 0-201-89685-0 |volume=a du texte supplémentaire ( aide ). Section 6.2.4 : Arbres à plusieurs voies, pp. 481-491. De plus, les pages 476 à 477 de la section 6.2.3 (Arbres équilibrés) traitent de 2 à 3 arbres.

Papiers originaux

• Bayer, Rodolphe ; McCreight, E. (juillet 1970), Organisation and Maintenance of Large Ordered Indices , Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories.
• Bayer, Rudolf (1971), Binary B-Trees for Virtual Memory , Actes de l'atelier ACM-SIGFIDET de 1971 sur la description, l'accès et le contrôle des données, San Diego, Californie.

Liens externes

• Conférence B-tree par David Scot Taylor, SJSU
• Visualisation B-Tree (cliquez sur "init")
• Visualisation animée du B-Tree
• B-tree et UB-tree sur Scholarpedia Commissaire : Dr Rudolf Bayer
• B-Trees : structures de données arborescentes équilibrées
• Dictionnaire des algorithmes et des structures de données du NIST : B-tree
• Tutoriel B-Tree
• L'implémentation InfinityDB BTree
• Cache Oblivious B(+)-arbres
• Entrée du dictionnaire des algorithmes et des structures de données pour B*-tree
• Structures de données ouvertes - Section 14.2 - B-Trees , Pat Morin
• Arbres B comptés
• B-Tree .Net, une implémentation RAM & Disk moderne et virtualisée

Chargement en vrac

• Shetty, Soumya B. (2010). Une implémentation configurable par l'utilisateur de B-trees (Thèse). Université d'État de l'Iowa.
• Kaldırım, Semih (28 avril 2015). "Organisation des fichiers, ISAM, B+ Tree et Bulk Loading" (PDF) . Ankara, Turquie : Université Bilkent . p. 4–6.
• "ECS 165B : Implémentation du système de base de données : Conférence 6" (PDF) . Université de Californie, Davis . 9 avril 2010. p. 23.
• "BULK INSERT (Transact-SQL) dans SQL Server 2017" . Microsoft Docs. 6 septembre 2018.