Quadtree and R-tree indexes in oracle spatial

TLDR

Spatial indexing has been a focus of recent database research, with multiple Quadtree and R-tree variants proposed in the literature. The paper describes the implementation of Quadtree and R-tree indexes and related optimizations in Oracle Spatial. The authors compare the performance of the two structures for various query types and operations in Oracle Spatial. The study concludes with insights from indexing large GIS datasets using the two structures in Oracle Spatial.

Abstract

Spatial indexing has been one of the active focus areas in recent database research. Several variants of Quadtree and R-tree indexes have been proposed in database literature. In this paper, we first describe briefly our implementation of Quadtree and R-tree index structures and related optimizations in Oracle Spatial. We then examine the relative merits of two structures as implemented in Oracle Spatial and compare their performance for different types of queries and other operations. Finally, we summarize experiences with these different structures in indexing large GIS datasets in Oracle Spatial.