Find database structures is an area that has led to much research in the field of software engineering. These include the B-Tree and its variants, the BSP, the RB Tree, and finally the R-Tree, which is a fairly new, dating from 1984 was discovered by A. Guttman.
I had the pleasure of developing such an engine-based R-Tree during my mission in Viamichelin for indexing the French road network and its traffic information. The R-Tree is now beginning to go beyond its starting field, which was indexing geospatial data, to arrive in the branches of jurisdiction as the classification of multimedia archives, or geo-indexing of moving objects , popularized by the influx of cheap GPS.
The R-Tree has many advantages that command attention:
- While the original R-Tree was to organize efficiently a large database of two-dimensional, it has evolved to include higher order data through its variants (MVR-Tree for the 4-dimensional example). Its variants are, at present, the most efficient structures to store data at large.
- The structure is dynamic allowing the insertion, the destruction and queries in any order, while using heuristics to minimize the time of application. There are some prototypes that bind Artificial Intelligence techniques for forecasting and arranging the structure of the database based on queries.
- The complexity of research and therefore the response time is similar to the size of the database even with large number of elements. Similarly, this structure is fully adapted for parallel I / O or CPU.
Its other advantage is that it is well documented, and there is also a very large number of variants that can meet many different needs. After my mission, I chose a variant called R * Tree, which is one of the best known and most robust, associated with a method of bulk loading method by Hilbert, since I had data strictly two dimensional.
There are many open source libraries on the Internet that implements these trees. A special note:
- SAIL : library C + + / Java I recommend, despite the brevity of its documentation. Note the Java plug-in for 3D visualization of the base. It is very portable and can change quickly access methods or bulk load.
- GiST : is the library that served as the basis of RTree PostGreSQL but in C + +.
- XXL : a Java library which is a very good introduction to the R-Tree but I found too rigid to adapt to customer demand.
Note also a portal specializing in RTree with many code sources on http://rtreeportal.org/ , and very good documentation available. The book RTrees: Theory and Applications Springer is one of my strong recommendations for anyone starting in this field. There are, of course, the possibility of using postgres for its R-Tree.
