Add geospatial to your comparison chart please. The way in which these implement support varies widely in performance and accuracy. I've yet to find one that actually uses R-Trees. Geohashes seem to be all the rage these days.
"I've yet to find one that actually uses R-Trees."
That's because R-Trees don't scale well with random write loads.
R-tree insertion performance is extremely dependent on insertion order (search for "sort tile recursive"). They're best used for problems where the data can be bulk-loaded and left alone. If random writes are an important part of the problem (as they are for most web-based tools), R-Trees are a bad idea.
Geohashes seem to play nicely to the strengths of an indexing search engine, because you can encode quadrants into a string of characters, and use ngram analysis to compare multiple levels of precision. There's almost no extra work that goes into using geohashes with a term-based index.
That said, they carry a lot of annoying edge cases when determining the adjacency of quadrants, so they're hardly a panacea to geospatial search. Lucene 3 and 4 make a lot of progress in spatial search, but there's still a fair bit of room for improvement.