Abstract: Spatial indices are used to improve performance of queries in spatial databases. The chip multi-processor (CMP) brings challenges as well as opportunity to spatial index structures. However, there is no comprehensive and quantificational evaluation of spatial index structures based on CMP, thus lacking of analysis on important factors that affect index performance. Based on modern commodity CMPs, this paper compares the performances of R-tree index, Hilbert R tree index, quad tree index and CR tree index in main memory, and evaluates how different factors, including different CPU parameters, different node sizes, different selectivities and different distributions of input data and so on, affect the performance of spatial indices. Experimental results show that, in order to improve per-formance of spatial indices, hardware features of the CMP must be fully exploited.

Key words: chip multi-processor (CMP), spatial index, cache sensitivity

摘要： 空间数据库索引是提高空间查询性能的重要方法, 片上多核处理器的出现, 在提高数据库性能的同时, 也给空间索引结构提出了新的挑战。面向多核处理器, 还缺乏对各种主要空间数据库索引结构和性能的综合实验比较, 从而无法定量分析影响索引性能的重要因素。针对目前主流的共享cache多核处理器, 对R树、Hilbert R树、四叉树及CR树在内存中的性能进行了测试, 分析了不同处理器硬件、不同索引结点大小、不同选择率、不同输入数据等多种因素对索引性能的影响。实验表明, 在多核环境下, 为了提高空间索引性能, 必须充分利用多核处理器的硬件特性。

关键词: 多核处理器, 空间索引, cache敏感