基于LSM树的NoSQL数据库索引研究

发布时间：2017-05-03 19:07

  本文关键词：基于LSM树的NoSQL数据库索引研究，，由笔耕文化传播整理发布。

【摘要】：随着近些年来互联网的不断发展以及移动互联网的慢慢兴起,网络已近渗透到我们生活的方方面面。每天产生的数据量已经超过以往任何时期。我们已经迎来一个大数据的时代。大数据的大不仅体现在数据量上,还体现在数据种类种类繁多和数据产生的速度也非常快。而这些数据还具有很高的商业价值。如何存储并有效利用这些数据已经成为大数据时代下的一大难题。传统关系型数据库无法为大数据提供行之有效的服务,而另一种完全不同的数据库体系正在兴起。这种数据库体系统称为非关系型数据库,即No SQL数据库。NoSQL数据库近几年得到了非常迅猛的发展,它为数据的存储提供了一种新选择。索引是数据库研究中最关键的一部分,而B+树是最常用的数据库索引结构之一,关系型数据库都采用B+树作为其索引结构。但是NoSQL数据库并不像关系型数据库那样采用表结构进行存储,它提供了许多不同的数据组织方式。因此,传统的索引方式已经无法满足NoSQL的索引需求。本文对NoSQL数据库索引的现状进行分析,针对NoSQL数据库索引存在的问题,设计一种新的索引方案。本文通过对常见索引结构进行调研,分析不同索引结构的优缺点。针对广泛使用的LSM树作为研究对象,设计并实现了一种基于LSM树的索引结构——iLSM树。该结构针对LSM树中存在的不足,即通过牺牲数据查询效率的方式来获得数据写入效率的大幅度提升。通过分析LSM树执行数据查询的过程发现在进行数据查询的过程中,LSM树需要先访问所有子树以确定数据是否在其中,然后在对存有目标数据的子树进行查询。由于LSM树中的子树绝大多数都存储在磁盘上,因此,访问所有子树这个过程需要耗费大量的时间。本文通过添加对LSM树中子树的索引,来减少查询过程中需要访问的子树的数量,以减少查询整体需要消耗的时间,达到提高查询效率的目的。本文在HBase中对这一索引思想进行实现,并将新实现的系统与HBase的LSM树索引进行一系列对比试验。实验结果表明iLSM树能够在牺牲少量内存空间的前提下大幅度提升查询性能,同时保证iLSM树的写性能与LSM树基本保持一致。
【关键词】：NoSQL 索引 LSM树 HBase
【学位授予单位】：北京理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要5-6
• Abstract6-9
• 第1章 绪论9-17
• 1.1 研究背景和意义9-12
• 1.2 国内外研究现状12-14
• 1.2.1 NoSQL研究现状12-13
• 1.2.2 索引研究现状13-14
• 1.3 论文研究内容14-15
• 1.4 论文章节安排15-17
• 第2章 相关研究17-33
• 2.1 索引技术17-22
• 2.1.1 顺序索引17-18
• 2.1.2 散列索引18-19
• 2.1.3 树型索引19-22
• 2.2 No SQL22-24
• 2.3 HBase24-32
• 2.3.1 HBase基础架构24-28
• 2.3.2 HBase存储模型28-29
• 2.3.3 HBase索引29-32
• 2.4 本章小结32-33
• 第3章 iLSM树索引算法的设计33-43
• 3.1 设计思想33
• 3.2 数据模型33-36
• 3.3 操作36-42
• 3.3.1 插入36-37
• 3.3.2 查询37-38
• 3.3.3 树的合并38-39
• 3.3.4 INDEX的调整39-42
• 3.4 本章小结42-43
• 第4章 iLSM树索引算法的实现和评估43-57
• 4.1 索引算法实现43-51
• 4.1.1 索引结构43-47
• 4.1.2 数据写入47-48
• 4.1.3 数据查询48-51
• 4.2 性能测试51-55
• 4.2.1 点查询性能对比51-52
• 4.2.2 范围查询性能对比52-53
• 4.2.3 随机插入性能对比53-54
• 4.2.4 内存消耗情况对比54-55
• 4.3 本章小结55-57
• 总结与展望57-59
• 参考文献59-62
• 攻读学位期间发表论文与研究成果清单62-63
• 致谢63

【相似文献】

中国期刊全文数据库 前10条

1 ;本期广告商索引表[J];电子与电脑;2000年01期

2 ;本期编辑内容产品索引表[J];电子与电脑;2000年02期

3 ;本期广告商索引表[J];电子与电脑;2000年02期

4 ;本期编辑内容产品索引表[J];电子与电脑;2000年04期

5 ;本期广告商索引表[J];电子与电脑;2000年04期

6 ;本期编辑内容产品索引表[J];电子与电脑;2000年11期

7 ;本期广告商索引表[J];电子与电脑;2000年11期

8 ;本期编辑内容产品索引表[J];电子与电脑;1999年05期

9 ;本期编辑内容产品索引表[J];电子与电脑;1999年08期

10 ;本期编辑内容产品索引表[J];电子与电脑;1999年09期

中国重要会议论文全文数据库 前9条

1 石玮峰;杨冬青;唐世渭;关涛;;COBASE的索引管理技术[A];第十二届全国数据库学术会议论文集[C];1994年

2 王彦祥;王广林;;“索引之星”的研制和索引编制[A];2004年辞书与数字化研讨会论文集[C];2004年

3 王晓辉;王柏;;通过有效使用索引优化Oracle应用系统性能[A];第九届全国青年通信学术会议论文集[C];2004年

4 孙云峰;陈渝;史元春;张宝鹏;张曦;江文峰;;基于高精度室内定位系统的移动物体轨迹索引[A];第二届和谐人机环境联合学术会议(HHME2006)——第2届中国普适计算学术会议(PCC'06)论文集[C];2006年

5 王先胜;乔健;汪卫;何震瀛;;AX-Tree:基于RDBMS的粒度自适应XML数据索引[A];第二十五届中国数据库学术会议论文集（一）[C];2008年

6 邵雄凯;卢炎生;程学先;;用建立本地广播索引表的方法改善移动客户机的性能[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

7 薛巍;李维佳;穆飞;舒继武;;PDPI：一种面向多核的可扩展并行索引算法[A];全国网络与信息安全技术研讨会论文集（下册）[C];2007年

8 王鹏飞;洪晓光;;基于XML大文档的动态索引[A];第二十一届中国数据库学术会议论文集（技术报告篇）[C];2004年

9 杨彬;洪晓光;;基于XML大文档的动态索引[A];’2004计算机应用技术交流会议论文集[C];2004年

中国重要报纸全文数据库 前1条

1 裘宗燕;轻松做索引[N];中华读书报;2002年

中国博士学位论文全文数据库 前3条

1 张帆;搜索引擎中索引表求交和提前停止技术优化研究[D];南开大学;2012年

2 陈旭毅;基于索引云的企业搜索引擎实现研究[D];武汉大学;2011年

3 余利华;分布式数据存储和处理的若干技术研究[D];浙江大学;2008年

中国硕士学位论文全文数据库 前10条

1 周黎明;SYBASE数据库的索引压缩的设计与实现[D];上海交通大学;2015年

2 徐康;组学大数据的检索系统设计与实现[D];哈尔滨工业大学;2015年

3 周文辉;基于HBase和内存数据库的索引和查询技术研究与系统实现[D];南京大学;2014年

4 付佳;基于LSM树的NoSQL数据库索引研究[D];北京理工大学;2016年

5 王健;DWMS中索引选择策略的研究与实现[D];东华大学;2010年

6 胡玉乐;列存储DWMS中的索引关键技术研究[D];东华大学;2011年

7 张慧;一种基于位立方体的XML索引方式[D];山东大学;2007年

8 王学;面向SaaS应用交付平台的多租户数据索引研究[D];山东大学;2012年

9 石有滴;XML索引关键技术研究[D];华南理工大学;2011年

10 陈坚强;DB2数据库索引性能调整与优化[D];上海交通大学;2011年

  本文关键词：基于LSM树的NoSQL数据库索引研究，由笔耕文化传播整理发布。

本文编号：343563