一种基于四叉树和R_树的索引结构_QR_树
- 格式：pdf
- 大小：1.01 MB
- 文档页数：4
下载文档原格式
合集下载
QR-树:一种基于R-树与四叉树的空间索引结构
QR-树：一种基于R-树与四叉树的空间索引结构
张芩;王振民
【期刊名称】《计算机工程与应用》
【年(卷),期】2004(040)009
【摘要】提出了一种基于R-树与"四叉树"空间层次划分的空间索引结构QR-树,给出了其数据结构和算法描述.实验证明:与R-树相比,QR-树以略大(有时甚至略小)的空间开销代价,换取了更高的性能,且索引目标数越多,QR-树的整体性能越好.
【总页数】4页(P100-103)
【作者】张芩;王振民
【作者单位】华南理工大学计算机科学与工程学院,广州,510640;深圳市华正联实业有限公司,深圳,518049
【正文语种】中文
【中图分类】TP392
【相关文献】
1.R-树和四叉树的空间索引结构:RQOP_树 [J], 刘润涛;郝忠孝
2.一种基于R-树的空间索引结构 [J], 刘润涛;安晓华;高晓爽
3.一种基于R树和四叉树的移动对象空间数据库混合索引结构 [J], 徐少平;王命延;王炜立
4.一种基于四叉树和R*-树的索引结构--QR*-树 [J], 邱建华;唐学兵;黄华国
5.大型GIS空间数据库的有效索引结构QR-树 [J], 郭菁;郭薇;胡志勇
因版权原因，仅展示原文概要，查看原文内容请购买。
时空数据模型标准
时空数据模型标准
时空数据模型是一种用于处理和管理具有时间和空间维度的数据的模型。
以下是一些常见的时空数据模型标准：
1.时空立方体模型（Spatio-Temporal Cube Model）：这是一种基于立方体的数据模型，将空间数据按照不同的维度进行组织和存储。
时空立方体模型可以用于表示不同时间和空间分辨率的数据。
2.时空对象模型（Spatio-Temporal Object Model）：这是一种基于对象的数据模型，将时空数据表示为具有时间和空间属性的对象。
时空对象模型可以用于表示具有复杂时空行为的数据。
3.时空索引模型（Spatio-Temporal Index Model）：这是一种用于快速查询和检索时空数据的模型，通过建立索引来提高查询效率。
时空索引模型可以基于不同的索引结构，如R 树、四叉树等。
4.时空数据仓库模型（Spatio-Temporal Data Warehouse Model）：这是一种用于存储和管理大规模时空数据的模型，将时空数据组织成数据仓库的形式。
时空数据仓库模型可以用于支持时空数据的分析和决策。
这些时空数据模型标准在不同的应用领域和数据管理系统中得到广泛应用，可以根据具体需求选择适合的标准。
GIS技师试题
名词解释1.大地水准面军事辞海:【参考分类】军事力量 / 海军/海洋、海道测量及勤务【大地水准面在军事辞海中的解释】在全球海洋范围内．与静态海面地形的平均值为零的面相重合并向大陆内部延伸的水准面是地球重力场中一个等位面，亦是高程测量中的正高系统的起算面。
因地球表面地形起伏和内部质量分布不均匀，使大地水准面成为略有起伏的曲面大地测量学研究的地球形状主要指大地水准面的形状汉语大词典:【大地水准面在汉语词典中的解释】指与平均海水面重合并延伸到大陆内部的水准面。
是正高的基准面。
在测量工作中，均以大地水准面为依据。
因地球表面起伏不平和地球内部质量分布不匀，故大地水准面是一个略有起伏的不规则曲面。
该面包围的形体近似于一个旋转椭球，称为“大地体”，常用来表示地球的物理形状。
2.地图投影：地图投影就是指建立地球表面（或其他星球表面或天球面）上的点与投影平面（即地图平面）上点之间的一一对应关系的方法。
即建立之间的数学转换公式。
它将作为一个不可展平的曲面即地球表面投影到一个平面的基本方法，保证了空间信息在区域上的联系与完整。
3.地图集：地图集是具有统一的设计原则和编制体例、协调的地图内容、规定的比例尺、分幅系统和装帧形式的多幅地图的汇集，是根据一定的主题和要求，将一定数量的、有机联系的、完整的地图系统，经统一设计，汇编成册的地图作品。
4.空间数据结构：是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。
换句话说，是指空间数据以什么形式在计算机中存储和处理。
空间数据结构是指空间数据在计算机内的组织和编码形式。
它是一种适合于计算机存贮、管理和处理空间数据的逻辑结构，是地理实体的空间排列和相互关系的抽象描述。
它是对数据的一种理解和解释。
空间数据结构是指空间数据的编排方式和组织关系。
空间数据编码是指空间数据结构的具体实现，是将图形数据、影像数据、统计数据等资料按一定的数据结构转换为适合计算机存储和处理的形式。
GIS空间索引方法述评_阎超德
收稿日期:2004-05-11; 修订日期:2004-06-15 基金项目:国家杰出青年科学基金(4002501)作者简介:阎超德(1965-),男,副教授,博士研究生,研究方向为GIS 、LBS 等。
GIS 空间索引方法述评阎超德,赵学胜(中国矿业大学测绘系,北京100083)摘要:地理信息系统的主要任务之一是有效地检索空间数据及快速响应不同用户的在线查询。
传统的索引方法只能解决一维查询问题,无法满足地理信息系统的要求。
该文介绍了G IS 中具有代表性的三类空间索引方法,即基于点区域划分的索引方法、基于面区域划分的索引方法和空间实体的地址编码索引方法,并且进行了分析对比。
关键词:空间索引;地理信息系统;四叉树;R-树;地址编码中图分类号:P208 文献标识码:A 文章编号:1672-0504(2004)04-0023-04地理信息系统(GIS )的主要任务之一是有效地检索空间数据及快速响应不同用户的在线查询。
空间索引是通过对存储在介质上的空间数据的描述,建立空间数据的逻辑记录与物理记录之间的对应关系,最终目的是提高系统对空间数据获取的效率。
传统的索引方法只能解决一维查询问题,无法胜任GIS 中海量空间数据的查询。
传统树表索引方法[1]中,如二叉树、B 树、ISAM (Index ed Sequential Access Method)等,主要针对字符、数字等数据对象,数据类型是在一个良序集之中,即集合中任意给出两个元素都可以确定其关系(只可能是大于、小于、等于这三种的其一);若对多个字段进行索引,必须指定各个字段的优先级,形成一个组合字段,但是GIS 中空间数据具有多维性,在任何方向上并不存在优先级,无法用于搜索具有多维特征的空间对象。
散列表方法是假定数据项中关键字与存储位置(存储桶号)存在哈希函数(H ashing)对应关系[1],这在多维空间中也是无法控制的。
另外,GIS 中存储了海量的空间数据,一般数据库所使用的索引机制并不适合空间对象的查询,要管理和检索这些海量空间数据,需要采用高效的多维空间索引技术。
数据库中空间数据的索引与查询优化
数据库中空间数据的索引与查询优化随着大数据时代的到来，空间数据的应用越来越广泛。
在许多领域，如地理信息系统、位置服务、物流管理等，空间数据的管理和分析变得至关重要。
数据库作为存储和管理数据的重要工具，对于空间数据的索引和查询优化也提出了新的挑战。
一、空间数据的索引传统的数据库索引主要是基于B树或B+树的结构，但是这种索引对于空间数据的查询效率并不高。
因此，研究者们提出了一些专门用于空间数据的索引结构，如R树、R*树、Quadtree等。
R树是一种经典的空间数据索引结构，它能够有效地支持范围查询和最近邻查询。
R树的基本思想是将空间对象划分为不同的矩形区域，然后将这些区域组织成一颗树。
通过递归地划分和合并矩形区域，R树能够将相似的空间对象聚集在一起，提高查询效率。
R*树是对R树的改进，它通过动态调整矩形区域的大小和位置，使得树的负载更加均衡。
R*树在范围查询和最近邻查询方面的性能比R树更好。
Quadtree是一种递归的四叉树结构，它将空间对象划分为四个象限，每个象限又可以继续划分为四个象限，以此类推。
Quadtree能够有效地支持范围查询和点查询。
除了这些经典的索引结构，还有一些新的索引结构被提出，如R+树、HilbertR树等。
这些索引结构在特定的应用场景下能够提供更好的查询性能。
二、空间数据的查询优化空间数据的查询优化是提高数据库性能的关键。
在设计查询语句时，可以采用一些优化策略来提高查询效率。
首先，可以使用空间索引来加速查询。
通过在空间数据上建立索引，可以减少查询的扫描范围，提高查询效率。
在选择索引时，需要根据具体的查询需求和数据特点来选择合适的索引结构。
其次，可以使用空间分区来优化查询。
将空间数据划分为多个分区，可以将查询范围缩小到特定的分区，减少查询的开销。
同时，可以将热点数据放置在同一分区，提高查询的局部性。
另外，可以使用聚集索引来提高查询性能。
聚集索引是将数据按照某个属性的顺序存储，可以减少磁盘的随机访问，提高查询效率。
基于聚类的空间数据多比例尺索引树
Ｍ ｕ ｔ－ｃ ｌ ｎ ｅ ｒ ｅ０ ｐ ｔａ ｔ ｓ ｄ ０ ｕｓｅ ｉ ｇ ｌｉｓ ａ ｅＩ ｄ ｘ Ｔ ｅ ｆＳ ａ ｉ ｌ Ｄａ ａ Ｂａ ｅ ｎ Ｃｌ ｔ ｒ ｎ
Ｚｏ Ｕ ｉｗｅ ， ＥＩＨｏ ｇ ｚ ｅ ＬＩＧｅ Ｚｈ － ｎ Ｆ ｎ － ｈ ， ｎ
ｓａ ａ ｄｔ， ｎ ｓｓ — ａ ｓ ｇｒ ｍ ｌｓ ｒｇｏ ｐ ｎｔｅｓｍｅｌｖｌ ｆｓａ ａｏ ｊｃｓ ｒｄ ｃｎ ｏ ｅａｅａｄｏ ｅｌｐ ｉｇｒｇｏ ｓ ｆ ｐ ｃ． ｐｔ ａ ａ ｄｕｅ ｍｅ ｏｉ ｔ ｃｕｔ ｒｕ ｓｏ ａ ｅ ｔ ｌ ｂｅｔ，ｅ ｕｉｇｃｖ ｒｇ ｖｒ ｐｎ ｉｎ ａｅ ｉ ｌ ａ ｋ ｎ ａ ｌ ｈ ｔ ｏ ｅ ｈ ｅ ｏ ｐｉ ｎ ａ ｅ ｏｓ
率 ，机械地将 Ｈ ｌｅｔ ｉ ｒ值最小 的 个对象索 引记录（ ｂ 为叶子 结点 的扇 出系数） 填充叶子结点Байду номын сангаас， 会使距离较远 的对象也放入
ｃ ｕｓｅ － ｓ ｄ ｍｕ ｔ—ｃ ｅ ｓ ａ ａ ａ ａ ｉ ｄ ｘ ｎｇ ｓｒ ｃ ｕ ｅ ｂ ｓ ｄ ｏ ｔｅ ｎ ｅ ，ｗｈｉｈ ｕ ｅ ｉ ｒ ｒ ｈ ｃ ｌｔｅ ｅ ｅ ｔ ｔ ｅ ｍｕｌ — ｃ ｌ ｅ ｔ ｒ ｓ ｏ ｌ ｔ ｒｂａ ｅ ｌ ｓ ａ ｐ ｔ ｄ ｔ ｎ ｅ ｉ ｔ ｔ ｒ ａ ｅ ｎ Ｒ—ｒ ｅ ｉ ｄ ｘ ｉ ｌ ｉ ｌ ｕ ｃ ｓ ｓ ｈ ｅ ａｃ ｉ ａ ｒ ｅ ｔ ｒ ｆ ｃ ｈ ｏ ｌ ｔ ｓａｅ ｆａｕｅ ｆ ｉ
比例尺变小 时，内容变得更简略 ，一些次要要素被剔除。空
比经典 Ｒ树更小 的区域覆盖和区域重叠 面积 ，具有 更高的查
询效率 。 是由于 Ｈｉ ｅｔ 但 ｌ ｒ 曲线不能完全反映出空间实体 的分 ｂ 布情况 ，因此在将高维空间映射到一维空间时 ，空间位 置上 相邻对象 的 Ｈｉ ｅｔ ｌ ｒ值并不一定相近 。 ｂ 尤其在数据分布不均匀 的情况下 ， 存储空间率越 高，结点之 间的区域重叠面积越大 ， 对索 引结构的性能影响越大 。 Ｊ
一种基于QAAR-树的空间索引方法
它 直接 影 响空 间数据 的存储 效 率 以及 空 间检 索 的 性能 。因此 ， 究空 间数据索 引方法 具有非常 重要 研 的意义 Ⅲ 。
树 处理海量 空 问数据 时查询 效率低 的缺 陷 ， 通过 改
进 的 Ｋ— ａ ｓ聚类 将检索过 程 中涉及 到 的查 找空 ｍｅｎ 间限制在更 小 的区域 中 ，提 高 了查询 性能 。 虽然 上 述混 合 索 引结 构在 一 定程 度上 提 高 了
第３ ４卷 第 ５期 ２ １ 年 ９月 ００
燕 山大 学 学 报
Ｊ ｕ ｎ ｌ ｆ ｎ ｈ ｎ Ｕｎ ｖ ｒ ｉ ｏ ｒ ａ Ｙａ ｓ ａ ｉ ｅ ｓｔ ｏ ｙ
Ｖｌｌ ４ Ｏ．５ ０ ＿３ Ｎ Ｓ ｐｔ ２０１ ｅ ． ０
文章编号 ：１ ０ －９ （０ ）０ －４ １０ ７７ １ ２ １ ０ Ｘ ０ ５０ ３ －７
目前 被 广泛 采用 的空 间数 据 索 引结构 主 要有
Ｒ． 树及其变种 结构 、２ 树 结构 、网格 索引结构 以 及 混合索 引结 构等 。 混合 索引结构 克服 了单一结构 处 理海量数据 时 的不足 ， 在大型数 据库 中得到 了广 泛应用 ， 尤其是 Ｒ 树及其家族 和２ 树 的混 合索 引 一 叉 结构成 为近年 的研究热 点 。 今为止 ，研究 人员提 迄 出了多种 Ｒ 树及其 家族和２ 树 的混合索 引结构 。 － 叹 ２０ ０ ３年伏玉琛等 人提 出了一种 ２ 树与 Ｒ 树 相结 一 合 的空 间索引结构 ＱＲ 树 口 一 四叉树 将整个 索引 ，用 空 间划分 成 多级 子索 引空 间，用 Ｒ一 树索 引每 级的
采 用 Ｋ ｍｅｎ 算法来 构建 Ｒ ｌ ｋ树 ，使 Ｒ ｌ ｋ树 — ａｓ —ｎ 一 ｉ －ｎ 一 ｉ
各 子节 点紧凑 、聚类 性 能高 ，提 高 了 Ｒ ｌ 一 的 —ｎ 树 ｉ ｋ 查 询效率 。 ０ ０ 高 云提 出 Ｑ Ｒ一 ２１年 Ｃ 树 是 针对 Ｑ 一 Ｒ
树 处理海量 空 问数据 时查询 效率低 的缺 陷 ， 通过 改
进 的 Ｋ— ａ ｓ聚类 将检索过 程 中涉及 到 的查 找空 ｍｅｎ 间限制在更 小 的区域 中 ，提 高 了查询 性能 。 虽然 上 述混 合 索 引结 构在 一 定程 度上 提 高 了
第３ ４卷 第 ５期 ２ １ 年 ９月 ００
燕 山大 学 学 报
Ｊ ｕ ｎ ｌ ｆ ｎ ｈ ｎ Ｕｎ ｖ ｒ ｉ ｏ ｒ ａ Ｙａ ｓ ａ ｉ ｅ ｓｔ ｏ ｙ
Ｖｌｌ ４ Ｏ．５ ０ ＿３ Ｎ Ｓ ｐｔ ２０１ ｅ ． ０
文章编号 ：１ ０ －９ （０ ）０ －４ １０ ７７ １ ２ １ ０ Ｘ ０ ５０ ３ －７
目前 被 广泛 采用 的空 间数 据 索 引结构 主 要有
Ｒ． 树及其变种 结构 、２ 树 结构 、网格 索引结构 以 及 混合索 引结 构等 。 混合 索引结构 克服 了单一结构 处 理海量数据 时 的不足 ， 在大型数 据库 中得到 了广 泛应用 ， 尤其是 Ｒ 树及其家族 和２ 树 的混 合索 引 一 叉 结构成 为近年 的研究热 点 。 今为止 ，研究 人员提 迄 出了多种 Ｒ 树及其 家族和２ 树 的混合索 引结构 。 － 叹 ２０ ０ ３年伏玉琛等 人提 出了一种 ２ 树与 Ｒ 树 相结 一 合 的空 间索引结构 ＱＲ 树 口 一 四叉树 将整个 索引 ，用 空 间划分 成 多级 子索 引空 间，用 Ｒ一 树索 引每 级的
采 用 Ｋ ｍｅｎ 算法来 构建 Ｒ ｌ ｋ树 ，使 Ｒ ｌ ｋ树 — ａｓ —ｎ 一 ｉ －ｎ 一 ｉ
各 子节 点紧凑 、聚类 性 能高 ，提 高 了 Ｒ ｌ 一 的 —ｎ 树 ｉ ｋ 查 询效率 。 ０ ０ 高 云提 出 Ｑ Ｒ一 ２１年 Ｃ 树 是 针对 Ｑ 一 Ｒ
空间索引原理
空间索引原理在计算机科学领域中，空间索引是用于管理和查询空间对象的一种数据结构。
它的作用是将具有空间延伸的数据组织在一起，使得查询操作更加高效。
空间索引是空间数据库技术的核心，通常被应用于地理信息系统、遥感技术和计算机图形学等领域。
这篇文章将介绍空间索引的原理和常用的空间索引结构。
空间索引结构通常由两个部分组成：空间索引节点和数据节点。
空间索引节点包含了对数据节点的引用，而数据节点则包含了对实际数据的引用。
空间索引节点通常按照一定的规则来组织，以便于查询操作的执行。
下面我们将介绍一些常用的空间索引结构。
1. R树R树是一种高效的空间索引结构，它主要针对范围查询这种场景进行优化。
R树的每个节点都表示一个矩形范围，而每个子节点则包含了更小的矩形范围。
根据这种方式，R树可以有效地组织大规模空间对象数据。
2. QuadtreeQuadtree是一种基于四叉树的空间索引结构。
它将一个二维空间划分为四个象限，每个象限又按照同样的方式划分为四个象限，以此类推。
Quadtree的每个节点都代表一个区域，而每个子节点则代表更小的区域。
Quadtree通常用于处理离散点数据，例如地图上的地理位置坐标。
3. KD treeKD tree是一种基于分割维度的空间索引结构，它可以有效地处理高维数据。
在KD tree中，每个节点代表一个超矩形区域，而每个子节点则代表该区域内的子集。
KD tree 的基本思路是根据数据特征进行递归划分，以便将数据按照一定的规律组织在一起。
BSP tree是一种基于二分法的空间索引结构，它主要用于分割多边形数据。
在BSP tree中，每个节点代表一个平面构成的空间体积，而每个子节点则代表该空间体积内的多边形集合。
BSP tree通常用于图形渲染和游戏开发等领域。
以上介绍的空间索引结构都是针对不同数据类型和应用场景的需求而设计的。
当我们需要选择一个具体的空间索引结构时，需要考虑以下几个因素：1. 数据类型：不同类型的数据需要不同的数据结构进行管理。
一种存储复杂多边形包含关系的四叉树索引
一种存储复杂多边形包含关系的四叉树索引四叉树是一种常用的空间索引结构，适用于存储和查询平面上的点、线段、矩形等几何对象。
然而对于复杂多边形的包含关系，四叉树的传统实现存在一定的局限性，因为复杂多边形的边界不再是分割空间的垂直或水平直线。
为了解决这一问题，可以引入一种基于四叉树的新的索引结构，用于存储和查询复杂多边形的包含关系。
该索引结构的基本思想是将复杂多边形划分为一系列较小的矩形块，然后构建四叉树来管理这些矩形块。
每个矩形块都可以表示一个简化后的多边形区域，从而提供了可靠的包含关系判断。
具体实现时，可以采用递归的方式构建四叉树。
将整个坐标范围划分为四个等大小的子块，然后对每个子块进行递归处理。
如果当前子块完全包含在复杂多边形内部，则该子块的包含关系设置为true；如果当前子块与复杂多边形存在部分交集，则继续划分该子块。
递归终止条件是当子块的边界长度小于某个预定义的阈值时，认为该子块已达到最小精度，不再继续划分。
在查询时，可以利用四叉树的包含关系来进行快速判断。
根据查询点或者查询多边形所在的子块，确定查询范围。
然后，通过遍历四叉树的递归过程，逐层判断每个子块的包含关系，直到找到最终的包含或不包含的结果。
该四叉树索引结构的优势在于能够有效地存储和查询复杂多边形的包含关系。
相比传统的分割直线的四叉树实现，它能够克服复杂多边形边界不是直线的问题。
该索引结构还具有一定的扩展性，可以根据需要增加更多的子块，并进行适当的剪枝操作，以提高索引结构的性能。
一种存储复杂多边形包含关系的四叉树索引结构能够有效地提供对复杂多边形的存储和查询功能。
在实际应用中，可以根据具体的数据特点和查询需求，对索引结构的参数进行调整，以达到更好的性能和准确性。
一种基于四叉树和R_树的索引结构_QR_树
QR* 树是一种基于四叉 树和 R* 树的 空间 索引 结构 , 它 结合 了四叉树和 R 树 的优 点 , 可以 将搜 索范 围限 定在 索引 空间 的某一部分 , 然后再用类似 R* 树 的搜索 算法来进 行查询 , 因 此提高了数 据的查询效率 , 尤其 是在数 据量非 常巨大 的应用 领域中。
125
了几个兄弟 结点的重叠区 域 , 则 以这些 结点为 根的子 树都将 被搜索 , 这会降低搜索效率 , 也很难对搜索效率进行预测。随 后的结构改善了这个问题。 R+ 树是 R 树和 K D B 树 [ 7] 结合 的产物 , 它将对象标识进行复制以使结点不产生重叠 , 因此在 搜索中避免了点查询在 R 树 中的多 路径搜 索。 R* 树 则尽量 减小结点间的重叠面积 , 它对上溢结点进行删除 , 并强制重插 入该结点中的所有对象。 X 树在侦测到所有可能的分裂都会 造成大的重叠时 , 通过不 分裂结 点的策 略来达 到降低 重叠的 目的。这种不分裂的结点称为超结点 ( Super node) , 但是这种 方法也带来 另一个问题 , 即一个 超结点 的孩子 个数是 不固定 的 , 且有可能超结点会很大 ( 尤其是在维度很高的情况下 ) , 这 会使得搜索超结点的时 间变长。 SR 树 的最小 约束盒是 最小 约束矩形和 最小约束球相 交的区域 , 这 种结构 可降低 结点的 重叠是因为 : 在高维空间 中超矩 形的平 均体积 要小于 超球的 体积 , 而超矩形的平均直径却要大于超球。然而 SR 树的插入 和删除操作代价很高且存储需求也相应增加了。
d- 1 l= 0
结构。设 d> 0, n=
( 2k) l , ( k 为空间 的维 数 , d 为 Quadtree
深度 ) , 则 QR* 树由一棵深 度为 d 的 四叉树 Qt 和 n 棵 R* 树 组成。 Q t 共 有 n 个 结点 , 依次 为 : Qt 0 , Qt 1 , , Qt n- 1 。 Qt 将 整个 数据 空间 S 划分 成 n 个 d 级子 空间 , 依次 记为 : S 0 , S1 , , S n- 1( 其中 S 0 = S) 。 每一级的所 有子空间 两两不相交 , 且 一起构成整个索引空间 S 。 n 棵 R* 树 : Rt 0 , Rt 1, , R t n- 1 分别 与 Q t 的 n 个 结 点及 Qt 划分的 n 个子空间相关联。 S i 与 Rt i 相关联 , 即 Rt i 用于索 引属于 S i 的 空间目 标。一空间 目标 P 属 于 S i 是 指 : ( a) P 完 全落于 Si 或 Si 完全包 围 P; ( b) S i 是 所有完 全包 围 P 的 子空 间中的最小者。 图 1 是二维空间 QR * 树的一个例子。在该例中 , Q R* 树 由一棵深度为 2 的 Quadtree 树和 5 棵 R* 树 组成。整 个空间 被划分为 2 级共 5 个子空间 : S 0, S1 , S 2, S3 , S 4( S0 = S1
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
125
了几个兄弟 结点的重叠区 域 , 则 以这些 结点为 根的子 树都将 被搜索 , 这会降低搜索效率 , 也很难对搜索效率进行预测。随 后的结构改善了这个问题。 R+ 树是 R 树和 K D B 树 [ 7] 结合 的产物 , 它将对象标识进行复制以使结点不产生重叠 , 因此在 搜索中避免了点查询在 R 树 中的多 路径搜 索。 R* 树 则尽量 减小结点间的重叠面积 , 它对上溢结点进行删除 , 并强制重插 入该结点中的所有对象。 X 树在侦测到所有可能的分裂都会 造成大的重叠时 , 通过不 分裂结 点的策 略来达 到降低 重叠的 目的。这种不分裂的结点称为超结点 ( Super node) , 但是这种 方法也带来 另一个问题 , 即一个 超结点 的孩子 个数是 不固定 的 , 且有可能超结点会很大 ( 尤其是在维度很高的情况下 ) , 这 会使得搜索超结点的时 间变长。 SR 树 的最小 约束盒是 最小 约束矩形和 最小约束球相 交的区域 , 这 种结构 可降低 结点的 重叠是因为 : 在高维空间 中超矩 形的平 均体积 要小于 超球的 体积 , 而超矩形的平均直径却要大于超球。然而 SR 树的插入 和删除操作代价很高且存储需求也相应增加了。
* * +
象限 ( 子象限 ) , 直到子象限 完全被 图像充 满或完 全没有 图像 为止。这样的 块即 为叶 结点。 非叶 结点 只有 部分 被 图像 覆 盖 , 因此要进一步进行分 解。区域 四叉树的 建立是 通过将 子 象限按某种空 间填 充曲 线排 序后 的顺 序插 入到 树中 来实 现 的。 M X 四叉 树与区 域四叉 树的组织 方式类 似 , 区别是 叶子 结点为黑结点或空结点 分别表示数据空间某一位置空间点的 存在与否。 M X 四叉树的高度是平衡的、 空间划 分是等分的 , 因此结构简单。但其插入 ( 删除 ) 一个点可 能导致树的深度增 加 ( 减少 ) 一 层或 多层 , 且 所有 的叶 子结 点都 必须 重新 定位。 另外 , M X 四叉树的高度往往很大 , 这无疑也 会影响其搜 索效 率。 2. 2 基于 R 树的索引结构 自从 G uttman 于 1984 年提 出了 R 树 的概 念 之后 , 许 多
QR * 树
摘 要: 目前, 许多应用领域频繁地涉及到大的数据集和高维数据对象, 如 CAD、 图形数据库等。 * * * 文中介绍了一种新的空间索引结构 QR 树 。QR 树的存储开销仅略大于 R 树 , 而在插入 、 删除 , 尤 * 其是查找性能上要优于 R 树。 关键词: 空间索引; 空间数据库; QR* 树 中图分类号: T P311. 132. 1 文献标识码 : A
2
相关工作
空间索引结构的种类很 多 , 但 大多数 空间索 引结构 可以
收稿日期 : 2003- 03- 03
作者简介 : 邱建华 ( 1976- ) , 男, 硕士研究生 , 主要研究方向 : 科学计算可视化、 空间数据库索引技术 .
第 8期
邱建华等: 一种基于四叉树和 R
*
树的索引结构
QR
*
树
1
引言
目前 , 许多应用领域频 繁地涉 及到大 的数据 集和高 维数
据对象 , 如数据挖掘、 图形 数据库、 CA D、 G IS 、 机器人 、 计 算机 视觉等 , 而且在很多应用中 , 对象需要动态更新 , 如插入 、 删除 等。怎样组 织/ 索 引这 类数 据成 为一 个富 有 挑战 性 的问 题。 一种空间索引 结构要尽量 追求数据 存储、 数据搜索 ( 查询、 检 索) 、 数据更 新等方面的 效率。这三 个方面 与应用相 关 , 不同 的应用要求各有差异 , 但要同时做到这三方面 却非常困难。 近年来 , 国内外学者提出了许多不同的空间索引方 法 : 包 括 R 树 [ 1] 、 R+ 树 [ 2] 、 R* 树 [ 3] 、 区 域四 叉树 [ 4] 等 , 但这 些 索引 方法各有优缺点。例如 : R 树采用 最小约 束矩形 来递归 分解 索引空间 , 其存储效率相对较高 , 但由于矩形区域之间可能产 生重叠 , 因此区域搜索可能需要沿多条路径进行 , 从而降低了 搜索效率。 R 树虽然避免了矩形区域的重叠 , 但它 可能需要 在不同的结 点中存储同一 个矩形的 标识 , 从而 降低其 存储效 率。R 树与 R 树有 类似缺点。 本文介 绍一种新的 空间数据 库的索 引结 构
QR* 树。
学者对这种索引结 构产生 了兴趣。到 目前为 止 , 相 继提出 了 许多 基 于 R 树 的 结 构 , 如 R+ 树 [ 2] 、 R* 树 [ 3] 、 X 树 [ 5] 和 SR 树 [ 6] 等。基于 R 树的索引结构的基本 思想都是一 样的 : 每个 非叶 结 点 有 一 个 与 之 相 关 的 最 小 约 束 盒 M BB( M inimum Bound Box ) , 所有在这个 M BB 中的 对象存 储在 以 M BB 为 根 结点的子树中。最小约束盒的大小依赖于 对象的分布和对象 的大小。基于 R 树的索引结构的平 均高度 为 O ( logN ) ( N 为 数据集的大小 ) 。 R 树是一种类似于 B + 树的结构。 R 树的主 要缺陷是结点的重叠。如果待查询的区域包含
3
QR 树
在 R* 树中 , 中间结点的索引 空间重 叠是不可 能避免 的 ,
*
当进行查找 时往往会产生 多条查找 路径 , 且其 中有些 是失败 查找路径 , 这使得 R* 树的查找性 能受到 影响 , 尤其是 当失败 查找路径较长时 , 对查 找性能 影响很 大。如果能 设计出 一种 索引结构 , 能将 R* 树的查找限定 在空间 的某一部 分来进 行 , 则会大大提高查找性能。为此本文提出了一种新的空间索引 结构 3. 1 QR* 树。 Q R* 树的结构 QR* 树是 结合 Quadtree 和 R 树而 提出 的一 种空间 索引
*
S2
S3
S 4) , Rt 0 , Rt 1 , Rt 2, Rt 3 , Rt 4 这 5 棵 R 树 分别 与之 相关 联。 完全包围 r1 的最小子空 间为 S 1 , 因 此 r1 被分配 给 Rt 1 ; 完全 包围 r2 的最小子空间了 S 0, 因此 r2 被分配给 Rt 0 。 因此 Q R* 树 的 结 构 由 Q uadtree 和 R* 树 的 结 构 组 成。 R * 树的结点结构如下所示 : 叶子 结 点 : ( COU N T , LEVEL , < OI1 , M BR1 > , < OI2 , M BR2> , M BR2> , , < O Im , M BR m> ) ;
An Index Structure Based Quad tree and R* tree
QIU Jian hua, TANG Xue bing , HUANG Hua g uo
QR* tree
(Comp uter College, W uhan Univer sity , Wuhan H ubei 430072 , China) Abstract: T he o peration of spatial data objects is fr equently involv ed in many applicat ions w ith larg e data sets and many of t he objects are high dimensio nality , such as CAD, image databases. T his paper intro duces an architectur e spatial index structure called Q R* tree, w hich uses a bit mor e storage than R* tree, however ex cels R* tr ee in insertion, delete, especially in sear ching. Key words: spatial index ; spatial database; Q R* tr ee 归为两大类 : 以区域 规则 划分 为基础 的索 引结 构 ; 基于 R 树 的索引结构。 2. 1 区域四叉树 区域四叉树 [ 4] 将 索引 空间 递归 分解 成四 个相 等 大小 的
d- 1 l= 0
结构。设 d> 0, n=
( 2k) l , ( k 为空间 的维 数 , d 为 Quadtree
深度 ) , 则 QR* 树由一棵深 度为 d 的 四叉树 Qt 和 n 棵 R* 树 组成。 Q t 共 有 n 个 结点 , 依次 为 : Qt 0 , Qt 1 , , Qt n- 1 。 Qt 将 整个 数据 空间 S 划分 成 n 个 d 级子 空间 , 依次 记为 : S 0 , S1 , , S n- 1( 其中 S 0 = S) 。 每一级的所 有子空间 两两不相交 , 且 一起构成整个索引空间 S 。 n 棵 R* 树 : Rt 0 , Rt 1, , R t n- 1 分别 与 Q t 的 n 个 结 点及 Qt 划分的 n 个子空间相关联。 S i 与ห้องสมุดไป่ตู้Rt i 相关联 , 即 Rt i 用于索 引属于 S i 的 空间目 标。一空间 目标 P 属 于 S i 是 指 : ( a) P 完 全落于 Si 或 Si 完全包 围 P; ( b) S i 是 所有完 全包 围 P 的 子空 间中的最小者。 图 1 是二维空间 QR * 树的一个例子。在该例中 , Q R* 树 由一棵深度为 2 的 Quadtree 树和 5 棵 R* 树 组成。整 个空间 被划分为 2 级共 5 个子空间 : S 0, S1 , S 2, S3 , S 4( S0 = S1
第 23 卷第 8 期 2003 年 8 月
文章编号 : 1001- 9081( 2003) 08- 0124- 03