R-arbre

L'idée principale derrière la structure de donnée est de représenter les objets proches par leur rectangle englobant au niveau immédiatement supérieur de l'arbre (le "R" de R-arbre est l'initiale de "rectangle"). En d'autres termes, dans un nœud donné de l'arbre sont stockés les rectangles englobants de chaque sous-arbre dont il est le parent. Ainsi, lorsqu'on recherche une information spatiale, il suffit de vérifier pour chaque branche si la position recherchée intersecte le rectangle correspondant, et d'ignorer les branches associées à un rectangle pour lequel il n'y a pas d'intersection. Chaque feuille de l'arbre décrit un seul objet, et chaque niveau supérieur décrit un rassemblement d'un nombre toujours plus important d'objets.

À l'instar d'un arbre B, les R-arbres sont des arbres de recherches équilibrés (toutes les feuilles sont à la même distance de la racine) dont les données sont organisées en pages, et sont spécialement indiqués pour le stockage sur disque, par exemple dans le cas d'une base de données. Chaque page a une capacité maximale, notée M (une page a au plus M entrées), et l'arbre garantit un taux de remplissage minimal de chaque page (à l'exception de la racine). Cette organisation en pages est adaptée à un grand volume de données : chaque page peut être chargée en mémoire lorsqu'on en a besoin, même si l'arbre entier était trop gros pour être stocké en mémoire.

La plupart des opérations de recherche spatiale (intersection, inclusion, recherche des plus proches voisins) sont simplifiées par la structure du R-arbre : on utilise le rectangle englobant d'une branche pour déterminer si on y poursuit l'exploration, ce qui permet d'éliminer la plupart des nœuds non pertinents.

La difficulté de mise en œuvre des R-arbres provient de la nécessité de garder l'arbre équilibré tout en évitant que les rectangles englobants ne couvrent trop d'espace vide ou que plusieurs rectangles ne recouvrent la même zone. Sans cela, les opérations de recherche spatiales risqueraient d'explorer trop de nœuds inutilement, ce qui aurait un effet sur les performances. Initialement, l'insertion des éléments se faisait en plaçant l'élément dans le sous-arbre dont la boite englobante grandirait le moins en y ajoutant le nouvel élément. Si une page est pleine, on divise ses éléments en cherchant à minimiser l'aire des rectangles correspondants aux deux sous-ensembles. La plupart des recherches concernant les R-arbres cherchent à optimiser les performances d'un arbre construit à partir d'une seule source de données (bulk loading) ou au contraire d'optimiser l'arbre dans le cas où les données sont ajoutées de manière incrémentale.

Bien que les R-arbres n'offrent pas de bonnes performances théoriques dans le pire des cas, ils sont très efficaces en pratique[5]. Il existe des variantes offrant des garanties d'optimalité même dans le pire cas pour le bulk-loading[6], mais la complexité de leur mise en œuvre limite leur usage dans les applications pratiques.

La possibilité de retrouver rapidement les objets situés à une distance r d'un point donné ou ses k plus proches voisins (au sens de n'importe quelle norme-p) à l'aide d'une opération de jointure spatiale[7] sert de base à de nombreux algorithmes qui reposent sur une implémentation efficace de ces opérations, par exemple pour le clustering ou la détection d'anomalies.

• Arbre de segments
• Arbre d'intervalles