B arbres vs arbres binaires

La complexité algorithmique est la même, puisque O (log _b n) = O(C log n) = O(log n) mais les facteurs constants sont extrêmement différents.

B-trees ont été conçus pour les disques durs de plateau, qui ont un temps d'accès énorme (déplacer la tête en position) après quoi un secteur physique entier est lu. Rendre les nœuds B-tree aussi grands que le secteur minimise le nombre de temps d'accès et maximise les données utiles de chaque opération de lecture.

Mais si vous travaillez à court de mémoire (ou SSD) vous avez un temps d'accès négligeable, donc une meilleure comparaison est de compter le nombre de mots simples accédés.

Par exemple, planifions une structure de données à stocker 2²⁰ clés de 1 mot chacune, pour un total de 4mib de données brutes sur une machine 32bit.

Un B-tree "costaud", conçu pour les disques durs contemporains, aura des nœuds 4kiB, pouvant contenir jusqu'à 512 clés et pointeurs (plus ou moins). Une profondeur de 2 avec 100% de remplissage tient 2¹⁸ Clés, donc nous avons besoin d'une profondeur de 3. À quoi ressemblera la recherche moyenne? En moyenne, il devra lire 3/8 (la moitié du remplissage moyen 3/4) de chaque nœud de son chemin, de la racine jusqu'au bas = 4608 mots.

Un arbre de recherche binaire aura 2²⁰ nœuds, chacun tenant une clé et deux pointeurs (3 mots). La profondeur sera de 20. La recherche moyenne devra lire la clé et l'un des pointeurs de chaque nœud dans son chemin, de la racine tout en bas = 40 mots .

Mémoire la mise en cache peut éventuellement atténuer la différence, mais ne peut pas inverser ces nombres.

D'autre part, les arbres B uniquement en mémoire avec un facteur de ramification beaucoup plus limité semblent mieux fonctionner que les arbres binaires dans la pratique.

32 clés par nœud en particulier semble être un sweet spot pour les architectures actuelles, à la fois 32 et 64 bits. De nombreux langages et bibliothèques plus récents utilisent des arborescences B à 32 touches comme structure de données intégrée, aux côtés de tables de hachage et de tableaux ou remplacement pour eux. Cette utilisation a été menée par Clojure et d'autres langages fonctionnels, mais a ensuite été reprise par des langages plus traditionnels tels que Javascript, avec l'accent récent sur les structures de données immuables (par exemple. immuable.js )

Ce résultat peut être dû au fait que, bien que les mots accédés par un algorithme B-tree soient plus que ceux d'un arbre binaire, le nombre de cache manque (lire les opérations qui provoquent le blocage du CPU et attendent le principal RAM) peut être plus faible que dans un arbre binaire, si l'architecture de mise en cache peut récupérer des morceaux de RAM qui contiennent un nœud B-tree entier à la fois.

Là encore, l'optimisation est la même que pour le stockage de masse sur disque, où nous utilisons des arbres B avec des nœuds aussi grands que le secteur physique, pour minimiser les temps d'accès. Dans ce cas, nous utilisons un b-tree avec des nœuds aussi grands que l'opération de lecture qui est effectuée par le cache de niveau 3 contre la RAM, pour minimiser les pertes de cache.