R-arbre

Les R-arbres sont des structures de données sous forme d'arbre utilisées comme méthodes d'exploration spatiale. Elles servent à indexer des informations multidimensionnelles (coordonnées géographiques, rectangles ou polygones). Inventés par Antonin Guttman en 1984, les R-arbres sont utilisés aussi bien dans des contextes théoriques qu'appliqués. Un cas d'utilisation typique des R-arbres est le stockage d'informations géographiques : par exemple l'emplacement des restaurants dans une ville, ou les polygones constitutifs des dessins d'une carte (routes, bâtiments, côtes, etc.), et de pouvoir par la suite répondre à des requêtes du type de "trouver tous les musées dans un rayon de 2 kilomètres", "afficher toutes les routes situées à moins de 5 kilomètres" ou "trouver la station-service la plus proche de ma position", par exemple dans une application de navigation. Les R-arbres peuvent également êtres utilisés pour accélérer la recherche des K plus proches voisins, en particulier pour certaines métriques comme la distance du grand cercle. 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.