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
"restructuring the whole index". No. Restructuring the R-tree is restricted to a single path, not the "whole" index. It works similar to the B-tree, actually.
Consider implementing both, and doing some benchmarks yourself, to really know how they perform. Don't only use theory.
On uniformly distributed data with a high change frequency, quadtrees will usually work better. On disk, the R-tree has clear advantages.