L'arbre T est essentiellement un arbre binaire. Donc la profondeur de l'arbre est quelque chose comme log2 (N/B) pour l'arbre T vs. logB (N) pour l'arbre B + (N = # éléments de données, B = nombre de clés stockées dans chaque nœud = facteur de branche pour B + Arbre). Ils sont approximatifs car aucun arbre n'a un nombre fixe d'éléments dans chaque nœud. Quoi qu'il en soit, pour un grand N, l'Arbre B + gagnera facilement sur cette métrique. Dans l'hypothèse d'un accès uniforme à la mémoire, ce chiffre n'a pas d'importance, mais il est vraiment important sur le stockage secondaire où il s'agit à peu près du nombre d'accès au stockage secondaire. Il compte également sur les machines modernes à mémoire hiérarchique (le papier T-Tree original testé sur un Vax 11/750).
Je fais des hypothèses ci-dessus concernant la façon dont vous mettez à jour les deux structures pour les environnements respectifs. Je crois qu'ils sont symétriques et justes. Principalement je suppose que les données et les clés sont stockées par référence en mémoire et par copie sur le stockage secondaire. Le fait de ne pas ajuster les structures de cette façon serait désastreux pour l'arbre T, qui a un coût d'accès uniforme au cœur de sa conception, car chaque comparaison clé nécessiterait un accès externe. Pour les données de taille non fixe, d'autres ajustements d'emballage sont nécessaires dans les deux cas (et utilisés dans le monde réel).
Si vous limitez à log B via la mise en cache, vous dites essentiellement que le nombre de nœuds lus est indépendant de la taille de l'index. Pour l'amour de l'argument, fixez B = 2 pour que votre index soit suffisamment grand pour que seul le dernier nœud soit lu. Je pense que cela signifie que tous vos nœuds internes doivent tenir dans le cache. Retour à l'index de taille arbitraire et vous avez un cache de taille arbitraire. – DrC
@DrC, vous avez parfaitement raison. Supposons que seules les valeurs min/max et les pointeurs enfants de chaque nœud sont mis en cache, ce qui signifie que B peut être beaucoup plus important alors que le coût de la mémoire reste constant pour chaque nœud de l'arborescence. Disons que vous avez besoin de 64 octets pour mettre en cache le min/max/left/right pour chaque nœud et B = 128. Sur la base du log (N/B) pour N = 1024 et B = 128, la hauteur devrait être log2 (1024/128) ou 3 avec 7 nœuds totaux (2^h - 1). Donc, avec 7 nœuds et 64 octets par nœud, c'est seulement 448 octets. Par conséquent, le coût de la mémoire augmente avec le nombre de noeuds et non N. Ce qui conduit à votre conclusion que seul le dernier noeud est lu à partir du disque au journal B. – max