CQRtree空间数据库索引结构及实现算法.pdfVIP

维普资讯 CN43—1258／TP 计算机工程与科学 2006年第 28卷第6期 ISSN 1007—130X COMPUTERENGINEERING SCIENCE V01．28，No．6，2006 文章编号：1007—130X(2006)06—0108—04 CQRtree空间数据库索引结构及实现算法 TheIndexStructureandItsImplementation Algorithm fortheCQRtreeSpatialDatabase 卢炎生。向祥兵，潘 鹏 LU Yan-sheng，XIANG Xiang-bing。PAN Peng (华中科技大学计算机科学与技术学院．湖北 武汉 430074) (SchoolofComputerScienceandTechnology，HuazhongUniversityofSciencenadTechnology。Wuhna 430074，China) 摘 要：空间数据库的索引是提高空间数据库存储效率、空间检索性能的关键技术。本文在 R树索引的基础上提 出 了一种新的空间数据库索引结构CQRtree，给出了CQRtree的数据结构、插入、删除、查询实现算法以及性能分析与比较， 最后指出了进一步的研究方向。 Abstract：Spatia1databaseindexisthevitaltechniqueforimprovingthestorageefficiencyofspatialdatabasesandthe spatialretrievalperformance．OnthebasisoftheanalysisofRtree，thispaperputSforwardaspatialdatabaseindexstructure CQRtre~ThispaperalsopresentsthedatastructureofCQRtree，theinsertion，deletionandsearchingalgorithmsforits implementationandthecomparisonsoftheCQRtreewithR tree．Finallythefurtherresearchdirectionisgiven． 关键词：空间数据库；索引结构；CQRtree Keywords：spatialdatabase；indexstructure；CQRtree 中圉分类号：TP311 文献标识码：A 和满四叉树各自优点的空间数据库的索引结构。下面就分 1 引言 别介绍这两类空间索引方法，并分析其各 自的优缺点。 2．1 CELLQtree树索引结构 空间索引是提高空间数据库性能的关键技术，它直接 影响空间数据的存储效率以及空间检索的性能。研究空间 2．1．1 CELLQtree树的结构及特性 索引技术并寻求更好的空问索引机制 ，对于空间查询的优 CELLQtree树r3]即满四叉树，是一种四叉树 它将 化有着十分重要的意义。 已知范围的空间划分成四个相等的子空问，如果需要，可以 迄今为止，人们提出了规则格网索引方法、二值空间划 将每个或其中几个子空间继续划分下去，这样就形成了一 分树(BSP树)、K_D-B树、R树[1]、R+树、Cell树、四叉 个基于四叉树的空间划分。 树[]等众多空间索引，其中主要为 R树系列和四叉树系 在CELLQtree树空间索引机制中，N层 CELLQtree 列 然而，R树和四叉树索引方法各有优缺点 本文结合