Un r*-arbre révisé en comparaison avec des structures d'index connexes

Dans cet article, nous présentons une refonte améliorée de l'arbre R*-tree qui est entièrement adaptée à un fonctionnement au sein d'un SGBD. Plus important encore, une insertion est garantie à être limitée à un seul chemin car la réinsertion pourrait être abandonnée. Nous avons réingénieré à la fois, le choix de sous-arbre et l'algorithme de séparation, pour être plus robustes face à des distributions de données spécifiques et des ordres d'insertion, ainsi qu'aux particularités souvent rencontrées dans des ensembles de données multidimensionnels réels. Cela s'accompagne d'une réduction substantielle du temps CPU.