Key-Value数据库上连接操作的查询处理与优化

论文摘要

伴随着互联网技术的高速发展,各种类型的应用层出不穷,在这个云计算的大环境下,数据存储技术出现了新的特点：支持海量的数据和流量,更低的读写延迟,强大的可用性,较低的运营成本等。在过去的几十年中,传统数据库虽然已经在业界占据了不可动摇的地位,但是面对时代的新需求,其扩展困难,读写慢,成本高,支撑容量有限等缺点不断显现出来。为了解决上述问题,NoSQL数据库应运而生。这类数据库在设计支持海量的存储,具有强大的可用性,并且可以运行在普通的PC机构建的集群中,运营成本低,易维护。因为一般都采用key-value的数据模型。所以习惯上又称key-value database,即KVDB.在key-value数据库中,元组之间并没有传统数据库中的强关联关系。这使得在key-value数据库中的SQL查询变得很难实现,而其中最为复杂的部分就是连接操作。针对此问题,本文通过对目前较为流行的一款环形KVDB:Cassandra进行分析,设计了针对环形架构列值索引,并基于这种索引提出了支持大数据量的预连接操作的查询处理算法,并做了相应的优化。另外作为补充,同时也设计了实时连接算法。本文的内容总结如下：1.首先介绍了NoSQL中的常见数据模型、架构和读写策略等相关知识。2.针对环形架构设计了相应的列值索引,给出了相关算法。并基于这种索引结构,设计并优化了预连接算法。3.设计了实时连接算法。同时针对实时连接算法,设计了双重索引,提高了实时连接算法的效率。4.针对本文提出的算法进行了实验测试,验证了算法的性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 问题的提出及研究意义
• 1.3 本文贡献点
• 1.4 本文的组织结构
• 第2章 NOSQL相关技术介绍
• 2.1 NoSQL发展现状
• 2.2 CAP理论
• 2.3 ACID/BASE
• 2.4 JSON格式和数据类型介绍
• 2.5 NoSQL系统架构
• 2.6 数据模型
• 2.7 副本策略
• 2.8 一致性策略
• 2.9 节点间通信
• 2.10 本章小结
• 第3章 预连接表的生成算法
• 3.1 理论基础
• 3.1.1 数据模型
• 3.1.2 一致性哈希
• 3.1.3 读写原理
• 3.2 预连接表的生成算法概述
• 3.3 列值索引的构建
• 3.3.1 索引的结构
• 3.3.2 使用方法
• 3.3.3 相关操作
• 3.4 预连接表的生成算法
• 3.4.1 预连接计划的生成
• 3.4.2 计算过程优化
• 3.4.3 预连接表的生成算法描述
• 3.4.4 更新与维护
• 3.4.5 预连接实例
• 3.5 本章小结
• 第4章 实时连接算法
• 4.1 基于索引的一般实时连接算法
• 4.2 改进的实时连接算法
• 4.2.1 分析
• 4.2.2 双重索引
• 4.2.3 改进后的实时连接算法描述
• 4.2.4 相关操作
• 4.3 代价分析
• 4.4 本章小结
• 第5章 实验与分析
• 5.1 实验环境
• 5.2 评价标准
• 5.3 测试内容
• 5.4 列值索引相关实验与分析
• 5.4.1 创建列值索引
• 5.4.2 选择查询的响应时间
• 5.4.3 列值索引的数据分布均匀性和算法并行度
• 5.5 预连接算法相关实验与分析
• 5.5.1 预连接算法
• 5.5.2 连接查询的响应时间
• 5.5.3 预连接表的数据分布均匀性和预连接算法并行度
• 5.6 实时连接算法相关实验与分析
• 5.6.1 连接查询的响应时间
• 5.7 本章小结
• 第6章 结束语
• 6.1 全文总结
• 6.2 下一步工作
• 参考文献
• 致谢
• 攻读硕士期间发表的论文和参加的项目