面向多核处理器的空间数据库索引性能分析

计算机科学与探索 ›› 2011, Vol. 5 ›› Issue (8): 707-718.

面向多核处理器的空间数据库索引性能分析

吴烨, 熊伟, 蔡蕾, 景宁

国防科学技术大学电子科学与工程学院, 长沙 410073

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-08-01 发布日期:2011-08-01

Performance Analysis of Spatial Database Indices on Chip Multi-Processor

WU Ye, XIONG Wei, CAI Lei, JING Ning

School of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China

Received:1900-01-01 Revised:1900-01-01 Online:2011-08-01 Published:2011-08-01

摘要/Abstract

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

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

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

吴烨, 熊伟, 蔡蕾, 景宁. 面向多核处理器的空间数据库索引性能分析[J]. 计算机科学与探索, 2011, 5(8): 707-718.

WU Ye, XIONG Wei, CAI Lei, JING Ning. Performance Analysis of Spatial Database Indices on Chip Multi-Processor[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(8): 707-718.

[1]	申金鑫，吴烨，陈荦，景宁. 面向空间在线分析的并行近似聚集查询[J]. 计算机科学与探索, 2018, 12(10): 1559-1570.
[2]	胡昱璞，牛保宁. 动态确定K值聚类算法的R-树空间索引构建[J]. 计算机科学与探索, 2016, 10(2): 173-181.
[3]	李国红，汪东升，刘振宇，李崇民，刘根贤，郭三川. 核分组的多核处理器优化方法[J]. 计算机科学与探索, 2014, 8(4): 385-396.
[4]	郭宪勇，陈性元，邓亚丹. 基于多核处理器的VTD-XML解析性能优化[J]. 计算机科学与探索, 2013, 7(8): 736-746.
[5]	王淼，漆锋滨. 异构多核代码自动生成框架[J]. 计算机科学与探索, 2013, 7(6): 518-526.
[6]	周国亮，王桂兰，朱永利. 多核处理器上的并行联机分析处理算法研究[J]. 计算机科学与探索, 2013, 7(2): 180-190.
[7]	李佳佳1 , 王波涛1+ , 陈东1 , 喜连川优2 , 王国仁1 . 分组移动对象的区域偏离监视算法*[J]. 计算机科学与探索, 2010, 4(9): 803-811.
[8]	刘涛+, 季振洲, 王庆. SimTile:片状多核处理器的高效模拟器[J]. 计算机科学与探索, 2010, 4(12): 1115-1120.
[9]	王波涛1+ ，陈贺1 ，马俊1 ，喜连川优2 ，王国仁1 . 利用覆盖区域设计与实现移动对象索引[J]. 计算机科学与探索, 2010, 4(1): 64-72.
[10]	庞一+,张凤妍,孙立峰,杨士强. 面向多核处理器的视频编码并行加速算法综述[J]. 计算机科学与探索, 2009, 3(4): 337-346.
[11]	刘胤田1,2 ,刘应明1 ,徐开阔3 ,曾涛4 ,唐常杰3+ . 多维空间索引结构SHG-Tree[J]. 计算机科学与探索, 2009, 3(1): 68-90.