面向流数据的快速索引构造及查找研究

《面向流数据的快速索引构造及查找研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、广东工业大学硕士学位论文（工学硕士）面向流数据的快速索引构造及查找研究卢子杰二○一八年五月分类号：学校代号：11845UDC：密级：学号：2111505012广东工业大学硕士学位论文（工学硕士）面向流数据的快速索引构造及查找研究卢子杰指导教师姓名、职称：蔡瑞初教授专业或领域名称：计算机科学与技术学生所属学院：计算机学院论文答辩日期：二○一八年五月ADissertationSubmittedtoGuangdongUniversityofTechnologyfortheDegreeofMaster（MasterofEngineeringScience）ResearchonIndex

2、ingandQueryoverDataStreamsCandidate:LuZijieSupervisor:Prof.CaiRuichuMay2018SchoolofComputerScienceandTechnologyGuangdongUniversityofTechnologyGuangzhou,Guangdong,P.R.China,510006摘要摘要从物联网和有全球位置定位系统（GPS）的智能设备来的大规模数据流正流入数据库系统作进一步的处理和分析。实时检索新数据和历史数据的能力成为了智慧制造和智慧城市等现实应用的关键。然而已有的解决方案，例如HBase，因为它在索

3、引更新上有大量的开销，所以并不能提供满意的性能。而以Druid为代表的时间序列数据库同样不能提供很好的性能。因为时间序列数据库缺少第二维度的范围索引所以它不能在非时间属性上提供高性能的范围查询。本文针对实时插入和实时范围检索的应用提出了一个简单而有效的分布式解决方案，使得系统支持每秒百万个元组的插入和自定义的毫秒级别延迟查询的时间范围查询。本文提出了一个新的数据划分方法。这种新的数据划分方法能利用工作负载的特点和避免全局数据合并。而全局数据合并的代价是十分昂贵的，这会使得系统性能降低。为了解决系统吞吐量不足的性能问题，基于进入系统的元组的数据分布相对稳定的前提条件和假设，本文提

4、出了一个模板依据的索引方法来避开不必要的索引结构调整。本文提出的共享分布式文件系统架构的解决方案通过模板B+树索引，充分利用了有限的计算资源和网络带宽。插入操作仅仅包括读取模板B+树中的中间结点，仅仅在叶子结点中可能会有少量的竞争锁的操作，从而保证了高并发的索引更新和查询。为了系统能并行进行数据插入和查询处理，本文提出了一个有效的调度算法和有效的负载均衡策略来更好地使用计算资源。为了测试系统的性能，本文在人造和现实数据集上进行了大量的实验，首先测试模板B+树的索引性能和数据块大小对系统性能的影响，然后测试了系统对于数据分布的适应性，最后测试了整个系统的插入性能并和已有的解决方案

5、HBase,Druid等作对比。实验结果表明，无论在人造还是现实数据上，本文的系统都比已有的系统性能表现至少好一个数量级。系统的性能表现优异的主要原因在于系统采用了两层的索引架构，同时使用模板B+树来减少索引结构维护的开销。此外，系统的查询调度算法和负载均衡方案能更好地利用计算资源。关键字：流数据；索引；查询处理；分布式系统；模板B+树；IABSTRACTABSTRACTMassivedatastreamsfromsensorsinInternetofThings(IoT)andsmartdeviceswithGlobalPositioningSystem(GPS)arenow

6、floodingtodatabasesystemsforfurtherprocessingandanalysis.Thecapabilityofreal-timeretrievalfrombothfreshandhistoricaldataturnsouttobethekeyenablertotherealworldapplicationsinsmartmanufacturingandsmartcityutilizingthesedatastreams.However,state-of-the-artsolutions,e.g.HBase,donotrendersatisfac

7、toryperformance,duetothehighoverheadonindexupdate.Timeseriesdatabases,e.g.Druiddonotrendersatisfactoryperformanceaswell.Theydonotrenderefficientrangequeriesovernon-temporalattributesduetothelackofsecondaryrangeindexes.Inthispaper,wepresentasimplean