> The assumption of size was "large-scale", which in this day and age usually means massively distributed. A B-tree is not a solution to that problem domain.

Another thought on this one: Space-filling curves decomposes the problem nicely: Scale out your favorite, ordered key/value stored, and then layer spatial indexing on top. No need to develop a new data structure that both scales out and handles spatial data.