跳表权值的分布式数据存储与定位方法

© 2013作者。出版社：Elsevier B.V.由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）120 - 1252013年AASRI并行和分布式计算与系统会议跳表权值的分布式数据存储与定位方法邵碧琳a，卞根庆b*，张伟奇aaXi建筑科技大学管理学院bXi建筑科技大学信息与控制工程学院摘要针对现有定位技术限制算法性能的问题，提出了基于跳表权值的分布式数据定位策略DLPSL。通过对跳表中的节点进行加权，使查找到的存储节点优先定位率高，缩短了查找路径，提高了存储和定位效率。系统分析表明，DLPSL的节点插入、删除、定位等操作都比单链表存储结构和跳图高效。其时间复杂度为0（log n），空间复杂度为0（n）。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：跳表权值，分布式存储，数据定位1. 介绍存储信息的目的是为了获取和利用。在分布式存储系统中，存在着大量数据的存在以及如何快速准确地找出分散的数据等问题通常，经典的索引机制有以下三类[1]：一种典型的代表，如可扩展HASH（EH）、线性HASH（LH）、冲突链HASH（CBH）和受控搜索多方向HASH（CSMH），是基于哈希函数的随机数据组织索引机制;另一种典型的索引机制是基于查询树的有序数据组织索引机制，如B树、B+树、AVL树、T树、T * 树、T-tail树等;第三个典型代表是Chanho Ryu[2]提出的混合索引机制Hybrid-HT，它是一种结合了哈希表和查询树特点的混合二叉搜索树会产生退化树，虽然AVL搜索树可以保证良好的性能，但同时增加了系统实现的难度[3]。跳转表通过随机性获得了较好的平均时间复杂度，在动态集和字典中使用跳转表可以获得较好的计算性能。在文献[4]中，马跃等设计了一种基于跳表数据结构的区间跳表，用于相交区域的快速搜索，分析了区间跳表的结构原理和基本操作过程，提出了基于区间跳表的相交区域搜索算法，解决了现有的一些动态区域搜索算法效率和准确性较低的问题。文献[5]提出了跳跃图*通讯作者。联系电话：13319273850;邮箱：bgq_00@163.com2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.067Bi-lin Shao等人/ AASRI Procedia 5（2013）120121····25212521····1919····12171712····796976···21191217·362621121992576267326363····其在插入、删除和查找时具有更高的效率，跳转图的功能类似于跳转表和二叉查找树。HammurabiMendes等人[6]研究了跳转图的一致性，并使用同步锁原语进行同步操作，以提高P2P分布式环境中的搜索效率Ying Jun等人[7]提出了一种大规模搜索算法来解决手持设备计算处理数据较弱的问题。John Risson等[8]提出了P2P下的搜索模型，该模型的索引机制是基于关键字搜索，可以用于信息恢复和数据管理。受跳表创建和索引机制的启发，提出了基于权值跳表的分布式数据定位策略（DLPSL），使定位率高的存储节点优先找到，缩短搜索路径，提高定位效率。2. 跳表结构跳转表是William Pugh在1990年发明的一种概率数据结构，它的链表基于并行链表，运算效率相对于二叉查找树有显著的提高（对于大多数运算，平均时间需要O（log n））[9]。它几乎是一种二叉树数据结构，其实现比平衡树更简单[10，11]。它是链表的扩展，而跳转表与链表的区别在于跳转表的每个节点（Node）中有多个前向指针，以实现快速检索这些指针构成多级指针30级链包含所有指针，1级链是0级链的子集i级链是（i-1）级链的子集一 ··B ··C ········D····e············图1. 不同系列的跳表在图1中，为了找到一个节点，需要遍历链表a中的N/2个节点，链表b中的N/4个节点，链表c中的N/8个节点，以及链表d中的N/16个节点如果有i层，则将遍历N/2i个节点跳表的优点是可以跳过一些节点，减少检索过程中关键字比较的次数。例如，当你检索一个有两个指针的跳转表时，你将沿着第一个主指针遍历，直到找到一个比搜索键更好的节点值，然后再回到次指针。在检索过程中，它将从最高级别的指针开始，并根据需要跳过尽可能多的记录以缩短步幅。无论成功与否，检索过程都会跳过一些节点值比较;在多级指针的跳转表中，检索过程会跳过更多的节点值比较。3. 分布式数据定位策略DLPSL3.1 一种分布式数据存储系统结构···191217··2626无无717325无无无·9 ··21 ····9 ···25 ··122Bi-lin Shao等人/ AASRI Procedia 5（2013）120如图2所示，系统由客户端、服务器和内存组成，内存包含一个或多个存储节点。客户端服务器存储器存储节点1存储节点2存储节点3存储节点N图2. 一种分布式数据存储系统结构客户端：通过分布式存储算法将需要保存的数据分离出来，然后将分离出来的信息提交给服务器。当数据需要恢复时，客户端向服务器发送请求，在收到服务器确认后，计算自己的服务器端：接受客户端信息请求的访问，使用DLPSL快速从Meta目录存储表中查找数据，返回相应的存储节点后，将数据逐一返回给客户端内存：接收来自服务器端I/O的访问，每个内存都有一个唯一的ID标识号（16），存储在服务器单元目录存储表中。3.2DLPSL的实现过程DLPSL采用基于权值的双跳表存储结构存储节点，其主要操作包括：节点初始化、定位、插入、删除和权值更新等。- 是的DLPSL节点由存储索引值（SID）、数据信息（Data）、存储节点ID（CID）、权重（优先级）和指针字段组成所有存储的索引值往往在-和+之间，而索引值是服务器查找指定用户数据的基础，它被定义为一个32位的二进制数。数据信息用于存储相关信息的数据，并将初始值设置为NULL。存储节点ID是对应文件分片的存储ID，一般有多个ID地址。初始化节点时，所有权重都设置为0。每个节点的层次由随机函数产生，然后根据搜索速率动态调整权值;节点所在的层将根据权值的大小动态变化节点定位。当客户端访问存储数据时，根据系统返回的客户端SID，采用DLPSL策略查找Meta目录存储表。在查找到SID号后，将相应的CID返回给服务器端，然后根据CID取出相应的数据段，最后服务器端将数据段返回给客户端。在删除和插入节点之前，定位节点必须是最高优先级的，粗体的行显示了下图3中查询节点63的路径。拆分和合并数据°双跳表权重目录存储表D1D2D3…DN…………Bi-lin Shao等人/ AASRI Procedia 5（2013）12012343210头图3.节点63Search（list，searchKey）x = list->headerfor i = list->level down to 1while x-> pointArray [i]->key searchKey do//pointArray[]是指针数组x = x-> pointArray [i]并返回x = x-> pointArray [1]如果x->key = search则返回x->value否则返回失败节点插入。完成插入操作的主要步骤是：首先定位节点的插入位置，然后创建新的节点，最后修改改变指针的值。插入操作将在更新节点时使用，其时间效率主要取决于定位算法的效率。Insert（list，searchKey，newValue）local data 1 [MaxLevel]//data 1 []是辅助数组x = list->headerfor i = list->level down to 1while x-> pointArray [i]->key searchKey dox = x-> pointArray [i]数据1 [i]= xx = x-> pointArray [1]如果x->key = search，则x->value = newValueelselal = randomLevel（）//|一|是随机生成的层，如果lal > list->level，则对于i = list->level +1，|一|dodata1 [i]= list->headerlist->level=|一|x = makeNode（lal，searchKey，newValue）for i = 1 to lal dox-> pointArray [i]= data1 [i]-> pointArray [i]data1 [i]-> pointArray [i]= x节点删除。删除节点与插入节点类似首先定位需要删除的节点，然后判断是否能找到该节点。如果能找到节点，则修改相关指针值并删除节点。如果没有找到节点节点删除的时间效率也取决于定位算法的效率。Delete（list，searchKey）local data1 [MaxLevel]//MaxLevel是Max Level x =list->headerfor i = list->level down to 1while x-> pointArray [i]->key searchKey dox = x-> pointArray [i]--x->key searchKey = x-> pointArray->key data1[i]= xx = x-> pointArray [1]如果x->key = searchKey，则V0V1V2V3V4V512 20 39 45 5155 59 63 6571 76 89124Bi-lin Shao等人/ AASRI Procedia 5（2013）120pMfor i = 1 to list->level doif data [i]-> pointArray [i]！= x then breakdata1 [i]-> pointArray [i]= x-> pointArray [i]free（x）while list->level> 1，list->header-> pointArray [list->level]= NILdo list->level = list->level -1重量更新。DLPSL更新时，判断第一层节点的权值是否大于或等于5，如果节点权值大于5，则节点序列加1，节点权值置零。通过这种方式，结合跳表中序列高位节点可以优先识别的特性，可以保证快速找到定位率高的节点，从而减少搜索时间。Updata（list，searchKey）如果x->key =searchKey，则优先级++如果优先级>=5优先级=0，优先级++4. 示范分析4.1 时间复杂度引入概率影响因子p（p通常取1/2），p介于指针i和指针i+1之间的L（n）log1n节点数由p表示 ，并且L（n）的最大值为：L（n）1（一）pk）nnpki层链中有n/2个i元素，插入时新元素属于i层链的概率为1/p。因此，根据i级链的元素识别的新元素的可能性为pi。C链序列是[logg 1 n]+1f或将军岬在这种情况下，在每个1 / p中，i层链中有一个元素 （i-1）-级链。当跳转表中有n个元素时，查找、插入和删除操作的复杂度为O（n+MaxLevel）在最坏的情况下，只有一个MaxLevel级别的链元素，所有剩余的元素都在0级链中如果i>0，则在i层链中的时间复杂度为O（MaxLevel），而在0层链中的时间复杂度为O（n）.跳转表的每个操作（搜索，插入和删除）的平均复杂度为O（logn），证明如下：m作为层，每层有两个元素跳过最后一个元素，时间复杂度为T namMA.M111m11Tm mna m，宣布Tm0，则a我，TmnM1百万美元（一） m）nm1。M的值越大，a 的值越小，a 的最小值为2。然后记录21log n，1log2n，T2logn. 时间复杂度为O（log n）。2米1米2 米1米24.2 空间复杂度空间复杂度，即在最坏的情况下所有元素都可以是MaxLevel级别，每个元素需要MaxLevel+1个指针。因此，需要存储n个元素，同时也需要存储链指针（所需空间为O（n * MaxLevel））。通常，一级链中只有n*p个元素，二级链中只有n*p个元素，i级链中只有n* pi个元素所以指针字段的平均值（不包括头到尾节点指针）为npin/（1p）。虽然需要大空间，最坏的情况下，但平均水平的要求并不低。当np=0i. 5时，存在一个平均空间（包括n的点ersnodes）大约是2n个指针的空间，证明如下：第一层n，第二层n/2，第三层n/22，因此，总的空间需求是：S = n + n/2 + n/22 +.+ n/2log n n（1 +1/2 + 1/22 +.+1/2）=2n。因此，它的空间复杂度是2n = O（n）。Bi-lin Shao等人/ AASRI Procedia 5（2013）120125在分布式环境中，jumps map[12]的时间复杂度为O（nlogn），空间复杂度为O（n）。在相同的环境下，本文提出的算法时间复杂度优于跳图算法，空间复杂度相同，总体上优于跳图算法。5. 结论分析了现有分布式存储系统的特点和数据定位机制的不足，提出了权值跳表分布式数据定位（DLPSL）策略，设计并实现了分布式存储系统。分析表明，DLPSL的插入、删除和定位效率与单表存储结构和不带权值的双向链表结构相比，引入权值能更好地解决分布式存储系统中数据定位效率的问题，具有快速高效的搜索效率，具有较好的应用价值。确认本论文得到了国家自然科学基金（No.6107319661272458）和山西省自然科学基金（No.6107319661272458）的资助2011JM 8026）。通讯作者：作者姓名：边根庆Email:bgq_00@163.com手机：13319273850通讯地址：Xi建筑科技大学信息与控制工程学院邮编：710055引用[1] 刘伟，刘伟，刘伟.一种存储系统工作负载分析仪，CS 06 -02-00[R].开普敦，开普敦大学[2] 刘晓波，刘晓波，等.第五届国际会议的议程Hiroshima，IEEE.1998：303-310.[3] 林X，史洛夫N B。一种基于优化的高带宽网络QoS路由方法[J].IEEE/ACM Transactions on Networking，2006，14（6）：1348-1361.[4] 马跃，战大勇，靳义成。基于跳表的DDM相交区域快速查询算法[J]计算机仿真杂志，200522（7）：46-49.[5] J.Aspnes和G. Shah.跳跃图[J].ACM Trans.on Algorithms，2007 3（4）：37-42.[6] Aspnes，J.，Wieder，U.跳跃图的扩张和混合时间及其应用[C]//ACM.在第十七届年度ACM研讨会上，算法和架构中的并行性New York，ACM，2005：126[7] 杨斌茂.一种大规模数据的多重索引快速搜索算法[J].计算机科学杂志，2009 36（3）：258-260.[8] 约翰·里森蒂姆·摩尔斯鲁棒对等网络研究综述：搜索方法[J]计算机网络2006，50（17）：3485-3521.[9]吴晓刚.跳表：平衡树的一种概率替代方法美国计算机学会通讯[10] W Pugh。跳表：平衡树的一种概率替代方法[J]. ACM通信，1990，33（6）：668-676.[11] 王晓刚.数据结构与算法分析[M].北京：清华大学出版社.波士顿Addison-Wesley出版，2006：85-126。[12] 题名其余部分：Cristina G.Skip图的并发实现离散元数据中的电子票据.