Le R-Tree qui cache la forêt.

Trouver des structures de base de données est un domaine qui a donné lieu à de nombreuses recherches dans le domaine de l’ingénierie logicielle. On peut citer les B-Tree et ses variantes, les BSP, le RB Tree, et enfin le R-Tree, qui est une structure assez nouvelle, sa découverte datant de 1984 par A. Guttman.

J’ai eu le plaisir de développer un tel moteur à base de R-Tree lors de ma mission chez Viamichelin pour l’indexation du réseau routier français ainsi que de ses informations de trafic. Le R-Tree commence désormais à outrepasser son domaine de départ, qui était l’indexation géo-spatiale des données, pour arriver dans des branches de compétence comme le classement d’archives multimédias, ou bien la géo-indexation d’objets en mouvement, popularisée par l’arrivée en masse de GPS bon marché.

Le R-Tree a de nombreux avantages qui retiennent l’attention :

  • Même si le R-Tree original visait à organiser de façon efficace une large base de données 2-dimensionnelles, il a évolué pour inclure des données d’ordre plus élevées grâce à ses variantes (MVR-Tree pour les 4 dimensions par exemple). Ses variantes sont, à l’heure actuelle, les structures les plus efficaces pour stocker des données à grandes dimensions.
  • La structure est dynamique permettant l’insertion, la destruction et des requêtes dans n’importe quel ordre, tout en utilisant des heuristiques pour minimiser les temps de requête. Il existe quelques prototypes qui lient des techniques d’Intelligence Artificielle pour pouvoir prévoir et agencer la structure de la base en fonction des requêtes.
  • La complexité de la recherche et donc le temps de réponse est analogue à la taille de la base de données même avec de grands nombre d’éléments. De même, cette structure est entièrement adaptée pour le parallélisme d’I/O ou CPU.

Son autre avantage étant qu’il est très documenté, et aussi qu’il existe un nombre très grand de variantes qui peuvent répondre à beaucoup de besoins différents. Au terme de ma mission, j’ai choisi une variante baptisée R* Tree, qui est l’une des plus connues et des plus robustes, associée à une méthode de bulk loading par méthode de Hilbert, étant donné que j’avais des données strictement deux dimensionnelles.

Il existe de nombreuses librairies Open source sur Internet qui implémente ces arbres. A noter particulièrement :

  • SaIL : la librairie C++/Java que je recommande, malgré la concision de sa documentation. A noter le plug-in java pour la visualisation en 3D de la base. Elle est très portable et permet de changer rapidement les méthodes d’accès ou de bulk load.
  • GiST : est la librairie qui a servi de base au RTree de PostGreSQL mais en C++.
  • XXL : une librairie Java qui est une très bonne initiation au R-Tree mais que j’ai trouvé trop rigide pour s’adapter au demande du client.

A noter aussi un portail spécialisé dans les RTree avec de nombreux code sources sur http://rtreeportal.org/, ainsi qu’une très bonne documentation disponible. Le livre RTrees : Theory and Applications chez Springer fait partie de mes recommandations fortes pour quiconque commençant dans ce domaine. Il y a, bien sûr, la possibilité d’utiliser postgres pour ses R-Tree.


Vous avez trouvé cette publication utile? Cliquer sur
Ippon
Ippon est un cabinet de conseil en technologies, créé en 2002 par un sportif de Haut Niveau et un polytechnicien, avec pour ambition de devenir leader sur les solutions Digitales, Cloud et BigData.

Ippon accompagne les entreprises dans le développement et la transformation de leur système d’information avec des applications performantes et des solutions robustes.

Ippon propose une offre de services à 360° pour répondre à l’ensemble des besoins en innovation technologique : Conseil, Design, Développement, Hébergement et Formation.

Nous avons réalisé, en 2017, un chiffre d’affaires de 31 M€ en croissance organique de 30%. Nous sommes aujourd’hui un groupe international riche de plus de 320 consultants répartis en France, aux USA, en Australie et au Maroc.
FRANCE Website LinkedIn