基于直角多边形的R树结点的分裂算法.pdfVIP

１基金颁发部门：国家自然科学基金委；项目名称：煤矿安全监测数据解析整合模型与应用 研究；编号 基金申请人: 孟凡荣 2 基金颁发部门：江苏省教委；项目名称：煤矿井下人员安全管理与救援支持系统科技示范 工程研究；编号：BS2006002 基金申请人: 孟凡荣 基于直角多边形的 R 树结点的分裂算法 孟凡荣 曹彦燕 郑鹏 （中国矿业大学计算机科学与技术学院，江苏 徐州 221008 ） 摘要：对于空间查询来说，目标近似是一个非常重要的问题。在R 树中常用的是最小包围 矩形（MBR ），但是它的近似精度不是很高，因此用直角多边形来近似空间对象可以提高近 似的精度。文中主要探讨了结点是直角多边形近似的R 树的结点分裂算法。 关键字：空间索引；R 树；分裂算法；直角多边形 中图法分类号：TP311 文献标识码：A Splitting algorithm of R Tree Based on Orthogonal Polygons MENG Fan-rong CAO Yan-yan (Computer Science and Technology Department, China University of Mining and Technology, 221008, China) Abstract ：To the spatial query, the important problem is the similar of the goal. In R tree, the MBR is usually used to represent the node; however it is not very similar to the goal. So using orthogonal polygon can improve the similar accuracy of the spatial object. In this paper, we mainly talk about the splitting algorithm of R tree that the node is represented by orthogonal polygons. Keywords ：Spatial Indexing Tree; Splitting Algorithm; Orthogonal Polygon 1. 引言 空间索引是提高空间数据库性能的关键技术，它直接影响空间数据的存储效率以及空间 检索的性能，研究空间索引技术并寻求更好的空间索引机制，已经成为当前计算机领域和其 它应用领域的一个研究热点。由于 R 树及其变体的结点都是用最小包围矩形来近似的，所 以在查询目标不规则的情况下，近似的精度不是很高。为此，本文对结点是直角多边形来近 似R 树的结点分裂算法进行了讨论。 2. 基本概念 2.1 R 树的定义 R-tree 和B-tree 相似，是一个高度平衡树，它的叶子结点中的索引数据包含指向数据的 指针。如果索引是驻留磁盘的，结点对应的则是磁盘中的页面。这样设计，空间查询则只要 访问少量的结点。索引是完全动态，插入和删除可以在查询时同时进行，这样就免去了周期 性的从新调整。 空间数据由一系列的空间数据记录对象组成。每一个空间数据记录有一个唯一的标识。 通过这个唯一的标识（RCID ）可以查找到记录所在的叶结点，从而找到记录所在的位置。 R 树中叶结点的形式描述如下： （I，tuple-identifier ） tuple-identifier 是空间数据的唯一的记录号 I= （I ，I ，I ….I ）表示空间数据，它是一个n 维的边界矩形。I ，I ，I ….I 表示各点 0 1 2 n 0 1 2 n 的坐标。 R 树中非叶结点形式描述如下： 基金项目：国家自然科学基金），江苏