|
|
|
The B-tree is in a meaningful sense the database counterpart of (balanced) binary trees, and it is supported in any respectable DBMS. No doubt, it is an important structure. I think of this paper's contribution as a generalization of B-trees to multiple dimensions. This is not the only such generalization, but it is a particularly powerful and elegant one. No doubt, this, too, is an important structure. Much subsequent research has been based on it, and it is also finding its way into products. Had Antonin Guttman not invented this structure, somebody else would have; this is how natural it is. In fact, that this structure was not invented until more than a decade after the B-tree was invented, and not until 1984, is in retrospect incredible. This paper marked an substantial step forward.
The R-tree indexes multi-dimensional data objects, which may be points or may have extent, by enclosing data objects in bounding rectangles, which are then, recursively, also enclosed in bounding rectangles. An index node then contains pairs of a pointer and a bounding rectangle, where the pointer points to the sub-tree with all objects enclosed in its corresponding rectangle. Search proceeds as in the B-tree, except that the query is a rectangle and the result contains all intersecting data objects.
The clarity and precision of this paper is remarkable, particularly taking into account the amount concepts and specifics provided. In the format of a ten-page conference paper, this paper succeeds at presenting a new index, complete with descriptions of the structure and properties of the index, its algorithms for search, insertion, and deletion, and three pages of performance studies. This paper may serve well as a model for a conference paper.
Copyright © 1999 by the author(s). Review published with permission.