Agreed. Also: R-trees don't do so well as you add data dimensions. (This is partly received wisdom; my rough understanding is that the empty volume in each node becomes cavernous and nice splitting becomes much less achievable.)

Another reference dump: If you haven't seen them I found spill trees a nice extension of metric trees for certain types of problems (CV anyone?); found via surfing links from some forgotten HN article: http://books.nips.cc/papers/files/nips17/NIPS2004_0187.pdf