一种改进的嵌入式电子地图空间索引  

An improved spatial index method for embedded electronic map

作　　者：劳洁莹[1] 孙志磊[1] 

机构地区：[1]浙江工业大学信息化办公室,浙江杭州310014

出　　处：《浙江工业大学学报》2015年第3期340-345,共6页Journal of Zhejiang University of Technology

基　　金：浙江省教育厅科研项目(20130251)

摘　　要：空间索引在嵌入式设备中有广泛的应用,按照不同的空间映射方式,可以分为不同的索引方法,如二叉树索引、网格索引、四叉树索引和R树索引及其变种,指出了各种空间索引的利弊和适用环境.目前嵌入式系统中硬件资源不足,人们对其功能的需求却在不断的增加,因此如何快速的检索到需要的空间数据以满足相应的功能成为了一个亟需的问题.根据各个索引方法优势以及其相关的使用环境,提出了一种四叉树和R*-树相结合的空间索引—QR*-树索引,此空间索引虽然在存储空间上比R*树略有增加,但是在插入、删除、查找等操作中的性能远远优于R*-树,非常适合作为嵌入式系统的数据库空间索引,最后在S3C2440平台上验证了其有效性.Spatial index is widely used in the embedded devices, which can be divided into various different index methods depending on space mapping method, such as binary tree index, grid index, quad tree index and R tree index. The advantages and disadvantages of various spatial index methods and the application environment are pointed out. But the hardware resources in embedded systems are insufficient for meeting the increasing requirements. Therefore, how to quickly retrieve spatial data needed to meet the corresponding function has become an urgent issue. A new spatial index-QR＊-tree index method combined with quad tree and R＊-tree is proposed in this paper. Although this spatial index has a little increase in storage space than R＊ - tree, but the performances in the insertion, deletion and search operations are far superior that R＊ - tree. It＇s very suitable for database spatial index in embedded system. The experiments show that the QR＊-tree index in the as3C2440 platform has a good performance.

关 键 词：电子地图 QR＊-树 嵌入式系统 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]