A simple analysis
d = 20, (2d ?1,000,000), N = 1,000,000
Let assume an ideally balanced R-tree with no overlap
- Tree height is lnm(N)-1
- for one point query the number of comparisons is :
- d ? m? (lnm(N)-1)
- m is minimum number of entries in a node.
- m =2 : 780 comparisons
- 2d queries : 780,000,000 comparisons
Simple scan: 20,000,000 comparisons