T-Tree ou B-Tree

Question

L'algorithme T-tree est décrit dans this paper Et T * -Tree est une amélioration de T-tree pour une meilleure utilisation des opérations de requête, y compris les requêtes de gamme et qui contient toutes les autres bonnes caractéristiques de T -arbre.
Cet algorithme est décrit dans cet article « T * -tree: Une structure d'index de base de données de la mémoire principale pour les applications en temps réel ».
Selon ce document de recherche, T-Tree est plus rapide que B-tree/B + arbre lorsque les ensembles de données correspondent à la mémoire. I mis en œuvre T-Tree/T * Arbre comme ils ont décrit dans ces documents et ont comparé les performances avec B-tree/B + arbre, mais B-tree/B + arbre de meilleures performances que T-Tree/T * Arbre dans tous les tests cas (insertion, suppression, recherche).
J'ai lu que T-Tree est une structure d'index efficace pour la base de données en mémoire, et il est utilisé par Oracle TimesTen. Mais mes résultats ne le montrent pas.
Si quelqu'un peut en connaître la raison ou avoir des commentaires à ce sujet, ce sera formidable d'avoir des nouvelles d'elle (ou de lui).

Answer 1

T-arbres ne sont pas une structure de données de base dans le même sens que les arbres AVL ou B-arbres sont. Ils sont juste une version piratée d'arbres binaires équilibrés et en tant que tels, il peut y avoir ou non des applications de niche où ils offrent une performance décente.

En ce jour et l'âge ils sont liés à souffrir horriblement à cause de leur mauvaise localité, à la fois dans le sens du bloc prévu/la page transfert compte et dans le sens de la localité de cache. Ce dernier est évident puisque dans tous les accès de nœud d'une recherche sauf pour la dernière, seules les valeurs de limites seront vérifiées par rapport à la clé de recherche - tout le reste est paginé ou mis en cache pour rien. Comparez cela à l'excellente localisation des arbres B en général et des arbres B + en particulier (sans parler des versions cache-inconscient et cache-aware qui ont été conçues explicitement pour les performances de mémoire).

Des problèmes similaires existent avec le rééquilibrage. Dans le monde des B-tree, de nombreuses variantes - à commencer par B + et Blink - ont été développées et perfectionnées pour atteindre les caractéristiques de performance amorties souhaitées, y compris des aspects tels que la simultanéité (verrouillage/verrouillage) ou leur absence. Donc, la plupart du temps, vous pouvez simplement sortir et trouver une variation B-tree qui correspond à votre profil de performance - ou utiliser l'arbre B + classique simple et être certain de résultats décents. Les arbres T sont plus compliqués que les B-arbres comparables et il semble qu'ils n'ont rien à offrir en termes de performance en général, étant donné que les temps de matériel de base avec une «hiérarchie» de mémoire à un seul niveau ont disparu depuis des décennies. Non seulement le disque dur est la nouvelle mémoire, l'inverse est également vrai et la mémoire principale est le nouveau disque dur maintenant. C'est à dire. même sans NUMA, le coût de transfert des données de la mémoire principale dans la hiérarchie du cache est si élevé qu'il est avantageux de minimiser les transferts de pages - ce qui est précisément ce que font les arbres B et leurs variations et non le T-tree. Plus proche du cœur du processeur, c'est le nombre d'accès/transferts en ligne de cache qui compte mais l'image reste la même. En fait, si vous prenez l'idée de la recherche binaire - qui est prouvablement optimale - et pensez aux moyens d'arranger les clés de recherche d'une manière qui fonctionne bien avec les hiérarchies de mémoire (caches), vous finissez invariablement par quelque chose ressemble étrangement à un B-tree ...

Si vous programmez pour la performance, vous verrez que les gagnants sont presque toujours situés quelque part dans le triangle entre les tableaux triés, les arbres B et le hachage. Même les arbres binaires équilibrés ne sont compétitifs que si leurs performances relativement médiocres tiennent le pas face à d'autres considérations et que les chiffres clés sont relativement faibles, c'est-à-dire qu'ils ne dépassent pas quelques millions.