基于二分混合空间曲线的HBase多维索引构建及查询优化问题研究

目录
1 绪论 1
1.1 研究背景与意义 1
1.2 国内外研究现状 2
1.2.1 索引技术 2
1.2.2 空间填充曲线 5
1.3 论文主要工作 6
1.4 论文章节安排 7
2 相关理论基础与技术简介 8
2.1 大数据存储与计算技术 8
2.1.1 Hadoop生态圈 8
2.1.2 HDFS 8
2.1.3 HBase 9
2.1.4 Spark Streaming 10
2.3 索引相关技术 11
2.3.1 二级索引 11
2.3.2 聚簇索引 12
2.3.3 多维索引 13
2.3 空间填充曲线 14
2.4 本章小结 17
3 基于可变阶数的二分混合空间填充曲线 18
3.1 问题描述 18
3.2 二分混合空间填充曲线 18
3.2.1 基本概念 18
3.2.2 编码方法 19
3.2.3 解码方法 20
3.2.4 编解码时空复杂度 21
3.2.5 可变阶数设置 22
3.3 空间填充曲线评价指标定义和说明 22
3.3.1 局部性 22
3.3.2 聚集度 26
3.4 空间填充曲线实验对比与分析 26
3.5 本章小结 31
4 基于二分混合空间填充曲线的多维流式全量索引 32
4.1 问题描述 32
4.1.1 数据倾斜与齐夫分布 32
4.1.2 线性化技术索引方案存在的问题 33
4.2多维流式全量索引SFI-HBase 36
4.2.1 SFI-HBase索引结构 36
4.2.2 范围查询 40
4.2.3 KNN查询 46
4.3索引性能实验对比与分析 49
4.3.1 插入效率对比 50
4.3.2 范围查询效率对比 52
4.3.2 KNN查询效率对比 54
4.4 本章小结 56
5 基于SFI-HBase的海量数据分析平台设计与实现 57
5.1 系统需求分析 57
5.1.1 功能性需求分析 57
5.1.2 非功能性需求分析 58
5.2 系统设计 58
5.2.1 系统架构设计 58
5.2.2 功能模块设计 59
5.2.3 数据库设计 60
5.3系统实现 62
5.3.1 员工管理模块 62
5.3.2 数据同步模块 65
5.3.3 订单查询模块 66
5.3.4 统计信息模块 70
5.4 系统测试 71
5.4.1 功能测试 72
5.4.2 性能测试 73
5.5 本章小结 74
6 总结与展望 75
6.1 总结 75
6.2 展望 76
参考文献 77
1.3 论文主要工作
针对HBase在非主键多维查询的问题和不足，本文从空间填充曲线和索引结构上作出改进，在HBase之上建立了一个多维流式全量索引层，并设计了基于该索引层的数据插入、查询算法，搭建了相关实验环境，与其他经典系统进行了比对。主要工作如下：
（1）二分混合空间填充曲线：研究了Z、Hilbert、Gray、Onion等空间填充曲线的编码解码算法，并研究了这些曲线的局部性、聚集度等相关性质。在此基础上，以本文索引系统的实际需求为前提，基于可变阶数设计出了一种二分空间填充曲线曲线。在实验中以Z曲线为基础，混合了Hilbert、Gray、Onion曲线，测量了Z-Hilbert、Z-Gray、Z-Onion 曲线的理论性质，使得混合的曲线在具备Z曲线优秀裁剪能力的同时，增强了其在局部性、聚集度上的表现。
（2）多维流式全量索引：在桶索引的基础之上，针对桶分裂时需要扫描桶数据、无法支持并发插入的缺点，在索引层加入了可动态设置桶大小的全量索引层，并移除了冗余的桶索引层。在数据插入方面，采用Spark Streaming流式批处理计算提前在内存中进行预聚合，提供了对数据并发的支持、加快了插入的速度，大大减少了插入数据在索引层的时间损耗。在查询方面，设计了根据查询数据量动态计算桶大小的算法，以此为基础设计了高效的范围查询、KNN查询算法。
（3）交互系统代码实现
调研学习了Hadoop、HBase、Kakfa、Spark Streaming等大数据开源组件，在实验环境下搭建了由三台虚拟机构成的大数据集群。使用Java语言编写了多维流式全量索引的插入、查询代码，并以此为基础，设计编写了网约车离线分析平台，将本文提出的HBase多维索引结构运用到了真实的应用场景中。
1.4 论文章节安排
本文包含六个章节，每个章节阐述的内容如下：
第一章 绪论。首先概述了本文的研究背景、目的以及其意义，随后对国内外研究现状进行了综述，并简要介绍了本文的主要研究内容。最后，给出本文的整体结构和各章节的概述。
第二章 相关技术介绍。首先介绍本文所涉及到的大数据存储与计算组件，然后介绍常见的索引技术，最后介绍空间填充曲线。
第三章 二分混合空间填充曲线。首先从空间填充曲线理论性质出发，指出划分性质、局部性和聚集度等理论性质对多维索引的重要性。接着，介绍了二分混合空间填充曲线的概念、编解码方法、时空复杂度和可变阶的设置方法。接着给出了空间填充曲线的局部性、聚集度指标定义。最后通过实验测量了部分二分混合空间填充曲线及其组成曲线在局部性、聚集度上的性质。
第四章 多维流式全量索引。首先介绍了数据倾斜和齐夫分布，并指出在设计索引结构时需要注意的地方和一些解决方案的不足之处。接着提出了多维流式全量索引结构SFI-HBase，并针对该索引结构设计了插入、范围查询和KNN查询算法。最后，复现了多个经典的HBase非主键多维索引结构，并将其与本文所提出的索引结构进行了实验对比，以验证本文所提出索引结构的效率。
第五章 网约车离线分析平台设计与实现。根据第四章提出的模型和算法，在实验环境下搭建了集群，并实现了一个简单的交互系统。
第六章 总结与展望。总结全文的研究内容，提出下一步的研究重点和工作内容。