结合LSM树的联动空间索引研究
发布时间：2021-05-24 08:00
随着地理信息数据采集设备的发展,空间数据的更新频率逐渐提高,空间数据的管理不仅要满足高效的查询需求,还需要兼顾快速的更新需求。在空间数据更新频率较高的情况下,现有的空间索引通常会导致对磁盘大量的随机读写,严重影响空间索引操作效率,难以满足当前空间数据更新需求。本文面向频繁插入和更新的空间数据,分析当前空间索引存在的缺陷,从空间索引结构和一二级索引实现出发,深入研究当前对空间数据高效更新和查询的需求,克服当前空间索引存在的更新效率低下问题,设计了一种高效更新的空间索引实现方案,为地理空间数据提供底层支持。具体研究内容如下:（1）改进了希尔伯特R树结构,在非叶子结点中存储希尔伯特值范围,提出了“从上至下”查询、“从下至上”调整的批量合并算法,解决了静态希尔伯特R树合并内存需求量过高以及动态希尔伯特R树合并效率较低的问题,达到了R树合并效率高、合并时内存占用较少、合并后空间利用率和查询效率较高等效果。为后续新的空间索引研究提供基础索引结构。（2）提出了将LSM树与改进希尔伯特R树融合实现结合LSM树的希尔伯特R树（LSM Hilbert R-Tree,LH R-Tree）,结合内存和磁盘分层...
【文章来源】：浙江大学浙江省 211工程院校 985工程院校 教育部直属院校
【文章页数】：83 页
【学位级别】：硕士
【文章目录】：
致谢
摘要
ABSTRACT
1 绪论
1.1 研究意义
1.2 国内外研究现状
1.2.1 空间索引研究现状
1.2.2 基于LSM树的索引研究现状
1.2.3 当前面向数据频繁更新的空间索引研究存在的不足
1.3 主要研究内容
1.4 论文组织结构与章节安排
2 LHR树空间索引构建
2.1 基于希尔伯特曲线构建的R树索引
2.1.1 空间填充曲线
2.1.2 希尔伯特R树
2.2 LSM树
2.2.1 LSM树结构
2.2.2 LSM树操作算法
2.3 改进希尔伯特R树
2.3.1 改进的希尔伯特R树节点设计
2.3.2 改进希尔伯特R树的高效合并算法
2.4 LHR树构建
2.4.1 设计思路
2.4.2 LHR树索引结构设计
2.4.3 LHR树的算法设计
2.5 本章小结
3 LSM B树与LH R树联动的空间索引
3.1 LSMB树主键索引
3.1.1 布隆过滤器
3.1.2 LSMB树主键索引实现
3.2 LSMR树二级空间索引
3.2.1 LSMR树空间索引设计
3.2.2 结合LSM B树的LSM R树二级空间索引
3.3 LSM B树和LH R树联动索引
3.3.1 一二级索引联动结构设计
3.3.2 一二级索引联动算法设计
3.4本章小结
4 空间索引的效率评估
4.1 实验准备
4.2 LHR树空间索引的效率对比
4.2.1 R树合并效率实验
4.2.2 R树查询效率对比实验
4.2.3 LHR树更新效率对比实验
4.3 LSM B树与LH R树联动的空间索引效率对比
4.3.1 LSM B树与LH R树联动索引更新效率对比
4.3.2 二级空间索引范围查询效率对比实验
4.4 本章小结
5 总结与展望
5.1 研究成果内容
5.2 研究特色
5.3 展望
参考文献
作者简历
【参考文献】：
期刊论文
[1]Key-Value型NoSQL本地存储系统研究[J]. 马文龙,朱妤晴,蒋德钧,熊劲,张立新,孟潇,包云岗. 计算机学报. 2018(08)
[2]基于LSM Tree的分布式索引实现[J]. 隆飞,翁海星,高明,张召. 华东师范大学学报(自然科学版). 2016(05)
[3]面向物联网海量传感器采样数据管理的数据库集群系统框架[J]. 丁治明,高需. 计算机学报. 2012(06)
[4]基于空间和属性数据的联合索引技术[J]. 彭勤生,方金云,张娟. 计算机工程. 2010(08)
[5]B+树在数据库索引中的应用[J]. 王英强,石永生. 长江大学学报(自然科学版)理工卷. 2008(01)
[6]空间填充曲线映射算法研究[J]. 徐红波. 科技信息(科学教研). 2007(35)
[7]N维Hilbert曲线生成算法[J]. 李晨阳,段雄文,冯玉才. 中国图象图形学报. 2006(08)
博士论文
[1]5G移动通信网络中缓存与计算关键技术研究[D]. 贾庆民.北京邮电大学 2019
[2]矢量大数据高性能计算模型及关键技术研究[D]. 周经纬.浙江大学 2016
硕士论文
[1]基于手机信令大数据的城市规划建模研究与应用[D]. 李长青.电子科技大学 2019
[2]一种面向时间依赖路网的空间索引技术研究与实现[D]. 臧寅旭.沈阳航空航天大学 2018
本文编号：3203855
【文章来源】：浙江大学浙江省 211工程院校 985工程院校 教育部直属院校
【文章页数】：83 页
【学位级别】：硕士
【文章目录】：
致谢
摘要
ABSTRACT
1 绪论
1.1 研究意义
1.2 国内外研究现状
1.2.1 空间索引研究现状
1.2.2 基于LSM树的索引研究现状
1.2.3 当前面向数据频繁更新的空间索引研究存在的不足
1.3 主要研究内容
1.4 论文组织结构与章节安排
2 LHR树空间索引构建
2.1 基于希尔伯特曲线构建的R树索引
2.1.1 空间填充曲线
2.1.2 希尔伯特R树
2.2 LSM树
2.2.1 LSM树结构
2.2.2 LSM树操作算法
2.3 改进希尔伯特R树
2.3.1 改进的希尔伯特R树节点设计
2.3.2 改进希尔伯特R树的高效合并算法
2.4 LHR树构建
2.4.1 设计思路
2.4.2 LHR树索引结构设计
2.4.3 LHR树的算法设计
2.5 本章小结
3 LSM B树与LH R树联动的空间索引
3.1 LSMB树主键索引
3.1.1 布隆过滤器
3.1.2 LSMB树主键索引实现
3.2 LSMR树二级空间索引
3.2.1 LSMR树空间索引设计
3.2.2 结合LSM B树的LSM R树二级空间索引
3.3 LSM B树和LH R树联动索引
3.3.1 一二级索引联动结构设计
3.3.2 一二级索引联动算法设计
3.4本章小结
4 空间索引的效率评估
4.1 实验准备
4.2 LHR树空间索引的效率对比
4.2.1 R树合并效率实验
4.2.2 R树查询效率对比实验
4.2.3 LHR树更新效率对比实验
4.3 LSM B树与LH R树联动的空间索引效率对比
4.3.1 LSM B树与LH R树联动索引更新效率对比
4.3.2 二级空间索引范围查询效率对比实验
4.4 本章小结
5 总结与展望
5.1 研究成果内容
5.2 研究特色
5.3 展望
参考文献
作者简历
【参考文献】：
期刊论文
[1]Key-Value型NoSQL本地存储系统研究[J]. 马文龙,朱妤晴,蒋德钧,熊劲,张立新,孟潇,包云岗. 计算机学报. 2018(08)
[2]基于LSM Tree的分布式索引实现[J]. 隆飞,翁海星,高明,张召. 华东师范大学学报(自然科学版). 2016(05)
[3]面向物联网海量传感器采样数据管理的数据库集群系统框架[J]. 丁治明,高需. 计算机学报. 2012(06)
[4]基于空间和属性数据的联合索引技术[J]. 彭勤生,方金云,张娟. 计算机工程. 2010(08)
[5]B+树在数据库索引中的应用[J]. 王英强,石永生. 长江大学学报(自然科学版)理工卷. 2008(01)
[6]空间填充曲线映射算法研究[J]. 徐红波. 科技信息(科学教研). 2007(35)
[7]N维Hilbert曲线生成算法[J]. 李晨阳,段雄文,冯玉才. 中国图象图形学报. 2006(08)
博士论文
[1]5G移动通信网络中缓存与计算关键技术研究[D]. 贾庆民.北京邮电大学 2019
[2]矢量大数据高性能计算模型及关键技术研究[D]. 周经纬.浙江大学 2016
硕士论文
[1]基于手机信令大数据的城市规划建模研究与应用[D]. 李长青.电子科技大学 2019
[2]一种面向时间依赖路网的空间索引技术研究与实现[D]. 臧寅旭.沈阳航空航天大学 2018
本文编号：3203855
本文链接：https://www.wllwen.com/kejilunwen/dizhicehuilunwen/3203855.html
