IEEE Transactions on Knowledge and Data Engineering · 2000 · 36 citations · 14 references
ComputingComputer EngineeringComputer ScienceData StructuresDatabasesStorage SystemsDatabase ManagementQuery OptimizationQuery ProcessingSpatial Database SystemsSpatial DatabasesStorage ManagementBuffer CapacityBufferingDatabase Management SystemsQuery Performance OptimizationQuery Performance PredictionR-treesTree Algorithms
Past R-tree studies have focused on the number of nodes visited as a metric of query performance. Since database systems usually include a buffering mechanism, we propose that the number of disk accesses is a more realistic measure of performance. We develop a buffer model to analyze the number of disk accesses required for spatial queries using R-trees. The model can be used to evaluate the quality of R-tree update operations, such as various node splitting and tree restructuring policies, as measured by query performance on the resulting tree. We use our model to study the performance of three well-known R-tree loading algorithms. We show that ignoring buffer behavior and using number of nodes accessed as a performance metric can lead to incorrect conclusions, not only quantitatively, but also qualitatively. In addition, we consider the problem of how many levels of the R-tree should be pinned in the buffer.
14
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
Ibrahim Kamel, Christos Faloutsos · 1993 · 491 citations · Full text