From a general programming perspective:

An R-tree is a data structure for indexing rectangles, which I guess would tally with Matt's comment about a having key which represents spatial data, ie. a point, line or area.

A B-tree is a similar but much simpler construct for indexing scalar values.

Your summary sounds reasonable though. Hash lookup efficiency is very much dependant on the suitability of the hash function with respect to your dataset. If your data clusters around a few hash values rather than being spread out over many then you are likely to get collisions where two or more key values generate the same hash value. This would be the point where your performance plummets as you can't go directly from the hashed value to the record you desire because you have to then search through all the records with that hash. I guess this is the point you have to optimise your table.

B/R-Trees are not subject to such collision problems but require more work when constructing the index (ie adding/removing records) because they optimise as they go along: Trees are most efficient when they are balanced - ie. at each decision point when traversing the tree there are roughly equal numbers of records in all directions. Most decent tree implementations are self-balancing to a degree, and this is where most of the work needs to be done when adding/removing records. However, it is usually possible to design a pathological dataset that would result in a severely unbalanced tree and if your dataset were unfortunate enough to conform to this then you would need to regenerate the tree to regain efficiency (this process would be largely analogous to optimising your hash table).

In summary, your summary would sound plausible :)