Introduction
Spatial data management has been an active area of intensive research for more than two decades.
In order to support spatial objects in a database system several issues should be taken into
consideration including spatial data models, indexing mechanisms, efficient query processing, and
cost models. One of the most influential access methods in the area is the R-tree structure proposed
by Guttman in 1984 as an effective and efficient solution to index rectangular objects in VLSI design
applications. Since then several variations of the original structure have been proposed to provide
more efficient access, handle objects in high-dimensional spaces, support concurrent accesses,
support I/O and CPU parallelism, and support efficient bulk loading. It seems that due to the modern
demanding applications and after academia paved the way, recently the industry has recognized the use
and necessity of R-trees. The simplicity of the structure and its resemblance to the B-tree allowed
developers to easily incorporate the structure into existing database management systems to
support spatial query processing. In this book we provide an extensive survey of the R-tree evolution,
studying the applicability of the structure and its variations to efficient query processing, accurate
proposed cost models, and implementation issues like concurrency control and parallelism. Based on the
observation that "space is everywhere", we anticipate that we are in the beginning of the era of the
"ubiquitous R-tree" in an analogous manner as B-trees were considered 25 years ago.
Click book cover to visit the book page at Springer.