浅论分布式并行索引研究

《浅论分布式并行索引研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、电子科技大学博士学位论文分布式并行索引研究姓名：杨峰申请学位级别：博士专业：计算机系统结构指导教师：刘心松2003.3.1电子科技大学博士学位论文摘要随着计算机应用领域的不断扩大，数据的规模越来越大，查询也越来越复杂，分布式并行索引以其高性能而逐渐成为解决这类复杂问题的有效手段，并且成为数据挖掘、数据仓库、网格计算和普适计算等研究中的一个热点问题。本文首先对分布式并行索引的研究现状做了详细的分析，在此基础上，提出一种新的、全面的分布式并行索引处理框架一DPIF，并对相关的索引结构、索引数据分配、索引复制策略、索引数据迁移和重构进行了深入

2、研究。在对索引结构的研究中，我们提出一种适合于分布式并行的新索引树结构——DPB+-Tree，此索引树以B+树和hash结构为基础，其叶子结点被组织为有11个散列表元的hash表链，并且从树的根结点到叶子结点，结点的副本数量逐渐减少。DPB+-Tree综合了B+树和hash表结构的优点，同时考虑了副本更新、数据迁移和负载均衡等各个方面的性能。在DPB+．Tree结构的基础上，我们研究了索引数据分配和副本分配策略。其中索引数据分配采用了基于值范围分片的策略，并通过调整范围的上下界来调整每个分片单元的大小。而副本的分配是动态的，其处理准则是

3、根据系统的访问统计数据，触发对系统副本的添加或者是减少，或者是副本的迁移，从而达到最佳的负载平衡。在索引复制策略的研究中，首先考虑了副本复制的原则，其包括更新／检索比、节点机负载和可靠性需求。然后描述了索引副本的建立过程和更新机制，其中索引副本的建立允许一个新的副本学习先前的副本，而索引副本更新主要基于消息来完成。此外，根据DPB'-Tree中索引数据的多副本特性，采用了一种模糊调度机制来进行副本间的任务调度，以改善系统的负载均衡和响应特性。接下来对索引数据迁移和重构进行了研究。首先根据DPB+-Tree的特点，提出一种开销较小的索引重

4、构策略，此策略通常情况下只会影响索引的两级。然后提出一种纯分布的基于阙值的数据迁移策略，通过两个阈值的设置，来判断节点机上的索引负载系数是否超过了临界值并且有别的节点能够接收数据，若是则触发数据迁移，数据迁移的过程主要由结点迁移来完成。电子科技太学博士学位论文最后，为了验证DPl3+．Tree系统的有效性及评估其性能，我们在响应时间、吞吐率、资源利用率和负载平衡度四个方面对DPB+-Tree进行了大量的模拟研究。模拟结果表明，DPB+-Tree系统不仅极大地提高了系统查询效率，而且还较好地解决了分布式并行索引系统中索引更新开销问题，在与

5、其它相关策略，如CPB方法的比较中具有明显优势。关键词：分布式并行索引，DPB+．Tree，索引数据分配，索引复制策略，索引数据迁移和重构电子科技大学博士学位论文AbstractAlongwiththecontinuouslyextendingofcomputerapplicationfield，thenumberofdatabecomemoreandmorelarge，andthesearchoperationbecomemoreandmorecomplicated．Thedistributedandparallelindexgrad

6、uallybecomethevalidmeansofresolvingthiscomplicatedproblembecauseitshighperformance，andbecomethefocusofDataMining，DataWarehouse，GridComputingandUbiquitousComputingetc．Thispaperhasanalyzedtheactualstudyingstateofdistributedandparallelindex．Thenpresentedanewdistributedandpa

7、rallelindexframeandlucubratedtherelatedindexstructure，indexdataassignment，indexreplicationstrategy,indexdatamigratingandrestructuring．Instudyingofindexstructure，wepresentedanewtreeindexstructurethatsuitablefordistributedandparallelandthistreewasnamedDPB+-Tree．DPB+．Treeis

8、basedonB+-Treeandhashdatastructure．InDPB+-Tree，theleafnodeisorganizedforahashlistandthenodescopiesgradu