基于lsm树的nosql数据库索引研究

《基于lsm树的nosql数据库索引研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于LSM树的NoSQL数据库索引研究付佳2016年1月中图分类号：TP392UDC分类号：004.65基于LSM树的NoSQL数据库索引研究作者姓名付佳学院名称计算机学院指导教师戴林副教授答辩委员会主席廖乐健教授申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2016年1月ResearchonNoSQLDatabaseIndexBasedonLSMTreeCandidateName：JiaFuSchoolorDepartment:ComputerScienceandTechno

2、logyFacultyMentor:Ass.Prof.LinDaiChair,ThesisCommittee：Prof.LejianLiaoDegreeApplied:MasterofEngineeringMajor：ComputerScienceandTechnologyDegreeby:BeijingInstituteofTechnologyTheDateofDefence：Janurary,2016研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所

3、知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：北京理工大学硕士学位论文摘要随着近些年来互联网的不断发展以及移动互联网的慢慢兴起，网络已近渗透到我们生活的方方面面。每天产生的数据量已经超过以往任何时期。我们已经迎来一个大数据的时代。大数据的大不仅体现在数据量上，还体现在数据种类种类繁多和数据产生

4、的速度也非常快。而这些数据还具有很高的商业价值。如何存储并有效利用这些数据已经成为大数据时代下的一大难题。传统关系型数据库无法为大数据提供行之有效的服务，而另一种完全不同的数据库体系正在兴起。这种数据库体系统称为非关系型数据库，即NoSQL数据库。NoSQL数据库近几年得到了非常迅猛的发展，它为数据的存储提供了一种新选择。索引是数据库研究中最关键的一部分，而B+树是最常用的数据库索引结构之一，关系型数据库都采用B+树作为其索引结构。但是NoSQL数据库并不像关系型数据库那样采用表结构进行存储，它提供了许多不

5、同的数据组织方式。因此，传统的索引方式已经无法满足NoSQL的索引需求。本文对NoSQL数据库索引的现状进行分析，针对NoSQL数据库索引存在的问题，设计一种新的索引方案。本文通过对常见索引结构进行调研，分析不同索引结构的优缺点。针对广泛使用的LSM树作为研究对象，设计并实现了一种基于LSM树的索引结构——iLSM树。该结构针对LSM树中存在的不足，即通过牺牲数据查询效率的方式来获得数据写入效率的大幅度提升。通过分析LSM树执行数据查询的过程发现在进行数据查询的过程中，LSM树需要先访问所有子树以确定数据是

6、否在其中，然后在对存有目标数据的子树进行查询。由于LSM树中的子树绝大多数都存储在磁盘上，因此，访问所有子树这个过程需要耗费大量的时间。本文通过添加对LSM树中子树的索引，来减少查询过程中需要访问的子树的数量，以减少查询整体需要消耗的时间，达到提高查询效率的目的。本文在HBase中对这一索引思想进行实现，并将新实现的系统与HBase的LSM树索引进行一系列对比试验。实验结果表明iLSM树能够在牺牲少量内存空间的前提下大幅度提升查询性能，同时保证iLSM树的写性能与LSM树基本保持一致。关键词：NoSQL；索

7、引；LSM树；HBaseI北京理工大学硕士学位论文AbstractWiththedevelopmentofInternetandthepopularityoftheMobileInternet,theInternethasalmostpenetratedintoeveryaspectofourlives.Theamountofdatageneratedbyusismuchfasterthaneverbefore.Wearesteppingintoaneraofbigdata.Thefeatureofbigd

8、ataisnotonlyreflectedinthevolumnofdata,butalsointhevarietyandthevelocityofdata.Howtostoreandusethesedataeffectivelyhasbecomeadifficultproblemintheeraofbigdata.Traditionalrelationaldatabasecannotprovideservice