The n-dimensional B-tree problem has been outstanding for 25 years, and has been described as "one of the persistent puzzles of computer science". The solution we present is surprisingly simple, and of such generic nature that it opens up a flood of possible application areas: multi-dimensional indexing in conventional database applications; spatial object indexing in GIS; image indexing in digital libraries; and scalable rule indexing in deductive databases.
For example, until now, not a single design for a dynamic spatial object index has been able to meet the predictable and controllable worst-case characteristics of the B-tree. We show how this can now be achieved.
More generally, we show how the result makes it possible to index any complex objects whose structures can be expressed as trees.
For a postscript version of this abstract, click here.