R-Tree and Quadtree Comparison
I want to compare the R-Tree and the Quadtree for geospatial data. While there is literature out there I struggle to find documents that cover real basic comparison. So I decided to ask this question.
In my opinion, the R-Tree has the advantage of being balanced and the tree has no empty leaves. As a disadvantage, the basic operation like insert or delete could result in restructering the whole index.
The Quadtree is the opposite, it is not balanced and has empty leaves, but it does not need to be restrctured.
So as a fazit from that I would say that the R-Tree does need less memory and is faster for searching because of the minimal height. The quadtree is better when there are many update-operations, but the resulting tree could be unbalanced.
Are these points correct in your opinion? Are there any good documents out there that cover this topic?
Auf Wiedersehen, Andre
Answer
Here's paper which has pretty nice comparison of QuadTrees and R Trees:
Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data
Some differences:
- Quadtrees require fine-tuning by choosing appropriate tiling level in order to optimize performance. No specific tuning is required for R-Trees.
- Quadtree can be implemented on top of existing B-tree. R-Tree -cannot
- Quadtree indexes are created faster than R-tree.
- R-trees are much faster than Quadtree for nearest neighbours queries.
- R-trees are substantially faster than Quadtree for window queries, like "inside", "contains", "covers" etc.