Je connais assez bien un arbre B, je dois principalement garder les bases de données bien alimentées en électricité, en climatisation et en espace disque dur. Je m'associe à une liste chaînée double (doubl [ie, ey]?).
Aujourd'hui, l'un des développeurs au déjeuner a mentionné un arbre R.
J'ai sauté sur Wikipédia et j'ai commencé à lire. Cela ressemblait à un horrible arbre B plus grand. Malheureusement, le fait de ne pas avoir une formation approfondie en mathématiques rend difficile la compréhension de ce dont certains de mes collègues parlent.
J'espérais que quelqu'un pourrait clarifier quelques différences entre un arbre B et un arbre R. Je finirai probablement par demander aux gars de toute façon, mais rien ne garantit qu'ils répondront à ma question. Plus que probablement, ils commenceront à divaguer sur Dieu sait quoi. . .
Réponses:
Un arbre R peut être considéré comme la généralisation d'un arbre b. Lorsqu'un arbre b fournit un accès O (log n) sur une "plage limitée" des clés qu'il contient, un arbre R fournit un accès O (log n) sur une "région dimensionnelle K" des clés qu'il contient.
Si vous souhaitez mapper des codes postaux sur des noms de comté, vous pouvez utiliser un arbre B, car vous pouvez lui demander "Quels sont tous les comtés avec des codes postaux entre 60000 et 61000?" Cependant, un B-Tree serait mal adapté pour cartographier les coordonnées GPS des noms de comté pour des requêtes comme "Quels sont tous les comtés à moins de 100 miles de Chicago?", Car il ne commande ses clés que sur une seule dimension. Un R-Tree décompose ses clés en fonction des boîtes englobantes qui se chevauchent, et c'est donc un moyen naturel de stocker les clés lorsque vous devez interroger sur plusieurs dimensions.
la source
La plupart des structures arborescentes peuvent être réduites à une forme de liste liée, tant que vous ignorez comment la liste est construite (en particulier, comment les éléments sont ajoutés et supprimés, et comment les nœuds sont rééquilibrés, le cas échéant). C'est essentiellement l'algorithme d'insertion / suppression / récupération qui distingue une structure de données d'une autre.
Les nœuds dans une arborescence R contiennent généralement un cadre de délimitation, qui vous permet d'indexer efficacement les emplacements, comme vous pourriez en avoir besoin si vous souhaitez rechercher des enregistrements "près" d'un emplacement particulier. Les éléments d'un arbre B ont un ordre plus simple; vous pouvez directement comparer si quelque chose est supérieur ou égal à un autre élément. Dans un arbre R, le but de chaque entrée est de déterminer quels éléments sont contenus dans une boîte englobante.
Un B-Tree vous permet de rechercher efficacement des éléments pouvant être commandés dans la mémoire secondaire (comme un disque dur), et un R-Tree vous permet de rechercher efficacement des éléments qui sont "à" ou "près" d'un point particulier ou d'une boîte englobante, également dans la mémoire secondaire.
la source