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.
