没有合适的资源?快使用搜索试试~ 我知道了~
0AASRI Procedia 5 ( 2013 ) 120 – 12502212-6716 © 2013 The Authors. 由ElsevierB.V.出版。由美国应用科学研究学会负责选择和/或同行评审 doi: 10.1016/j.aasri.2013.10.0670ScienceDirect02013 AASRI并行与分布式计算与系统会议0基于跳转表权重的分布式数据存储和定位方法0表0邵碧琳 a ,卞根庆 b * ,张伟琪 a0a 西安建筑科技大学管理学院,中国西安,7100550b 西安建筑科技大学信息与控制工程学院,中国西安,7100550摘要0针对现有的位置技术限制了算法的性能,提出了基于跳转表权重的分布式数据位置策略DLPSL来解决效率问题。在跳转表的节点上添加权重,以便找到存储节点的高定位速率,缩短搜索路径,并提高存储和定位效率。系统分析表明,DLPSL上的节点插入、删除和定位比单链表存储结构和跳跃图更高效。其时间复杂度为0(log n),空间复杂度为0(n)。0关键词:跳转表权重,分布式存储,数据位置01. 引言0例如,存在大量数据以及如何快速准确地找到分散的数据。通常,有三种经典的索引机制类别,如下所示[1]:典型代表,例如可扩展哈希(EH)和线性哈希(LH)以及冲突链哈希(CBH)和可控搜索多方向哈希(CSMH),是基于哈希函数的随机数据组织的索引机制;另一种典型的索引机制是基于查询树的数据有序组织的索引机制,例如B树、B+树、AVL树、T树、T*树、T-tail树等;第三种典型代表是Chanho Ryu提出的混合索引机制Hybrid-HT [2],它是一种将哈希表的特性与查询树结合的混合机制。二叉搜索树会产生退化树,尽管AVL搜索树可以保证良好的性能,但同时也增加了实现系统的难度[3]。跳转表通过使用随机性获得更好的平均时间复杂度,并且可以在动态集合和字典中使用跳转表获得良好的计算性能。0在文献[4]中,马悦等人设计了一种基于跳转表数据结构的区间跳转表,用于快速0在交叉区域搜索中的搜索,分析了区间跳转表结构原理和基本操作过程,提出了基于区间跳转表的交叉区域搜索算法,并解决了现有动态区域中某些搜索算法效率和准确性低的问题。文献[5]提出了跳转图的概念0* 通讯作者。电话:13319273850;电子邮件地址:bgq_00@163.com。0在 www.sciencedirect.com 上在线提供0© 2013 The Authors. 由Elsevier B.V.出版。由美审0以CC BY-NC-ND许可证开放访问。0以CC BY-NC-ND许可证开放访问。0121 毕琳∙邵等 / AASRI Procedia 5 ( 2013 ) 120 – 1250在插入、删除和搜索方面具有更高的效率,跳转图的功能类似于跳转表和二叉搜索树。Hammurabi Mendes等 [6]研究了跳转图的一致性,并使用同步锁原语进行同步操作,以提高P2P分布式环境中的搜索效率。Ying Jun等人 [7]0提出了一种大规模搜索算法来解决手持设备计算处理数据较弱的问题。John Risson等人 [8]提出了基于P2P的搜索模型,该模型的索引机制是基于关键字搜索,可用于信息恢复和数据管理。受跳转表创建和索引机制的启发,本文提出了基于权重跳转表的分布式数据定位策略(DLPSL),以便找到存储节点的高定位速率,缩短搜索路径并提高定位效率。02. 跳转表结构0跳转表是一种概率数据结构,由WilliamPugh于1990年发明,其列表基于并行链表,并且与二叉搜索树相关的操作效率有显著改进(对于大多数操作,平均时间需要O(log n))[9]。它几乎是一种二叉树数据结构,其实现比平衡树更简单[10,11]。它是链表的扩展,跳转表与链表的区别在于每个节点(Node)的跳转表中有多个向前指针,以实现快速检索。这些指针在原始链表的基础上形成多级指针链; 0级链包含所有指针,1级链是0级链的子集,i级链是(i-1)级链的子集。0图1. 一系列不同的跳转表0如图1所示,在链表a中查找一个节点需要遍历N/2个节点,在链表b中需要遍历N/4个节点,在链表c中需要遍历N/8个节点,在链表d中需要遍历N/16个节点。如果有i层,则需要遍历N/2i个节点。跳转表的优势在于它可以跳过一些节点并减少检索过程中的键比较次数。例如,当您使用两个指针检索跳转表时,将沿着第一个主要指针遍历,直到找到一个比搜索键更好的节点值,然后返回到次要指针。在检索过程中,它将从最高级指针开始,并跳过所需数量的记录以缩短步幅。无论成功与否,检索过程都会跳过一些节点值比较;在具有多级指针的跳转表中,检索过程将跳过更多的节点值比较。03. 分布式数据位置策略DLPSL03.1 分布式数据存储系统结构0∙ ∙ ∙ ∙ ∙ ∙0∙ ∙ ∙ ∙ ∙0∙ ∙ ∙0∙∙ ∙ ∙ ∙0NIL0NIL0NIL0NIL0NIL0a0b0c0d0e0122 毕琳∙邵等 / AASRI Procedia 5 ( 2013 ) 120 – 1250如图2所示,该系统由客户端、服务器和包含一个或多个存储节点的内存组成。0图2. 分布式数据存储系统结构0Client:通过分布式存储算法将需要保存的数据分离,并将分离的信息提交给服务器。当需要恢复数据时,客户端向服务器发送请求,在接收到服务器确认后,自己计算原始数据。 Server: 接受来自客户端的信息请求访问,使用 DLPSL快速从元目录存储表中查找数据,并在返回相应的存储节点后逐个返回数据给客户端。 Memory: 接收来自服务器端 I/O的访问,每个内存都有一个唯一的 ID 识别号(16),存储在服务器元素目录存储表中。03.2 实现 DLPSL 的过程0DLPSL 采用基于权重的双跳表存储结构,其主要操作包括:节点初始化、定位、插入、删除和权重更新等。0Initialization. DLPSL 节点由存储索引值 (SID)、数据信息 (Data)、存储节点 ID (CID)、权重 (priority)和指针字段组成。所有存储索引值通常在-和+之间,并且索引值是通过服务器使用32位二进制数来查找指定用户数据的基础。数据信息用于存储相关信息的数据,并将初始值设置为NULL。存储节点 ID 是对应文件分片的存储 ID,通常有多个 ID地址。初始化节点时,所有权重都设置为0。每个节点的层级由随机函数生成,然后根据搜索率动态调整权重的大小来动态改变节点所在的层级。0Node Locating. 当客户端访问存储的数据时,根据系统返回的客户端 SID,使用 DLPSL策略在元目录存储表中进行搜索。在搜索到 SID 号后,将返回相应的 CID 给服务器端,然后根据 CID取出相应的数据段,最后服务器端将数据片段返回给客户端。在删除和插入节点之前,首先必须定位节点,下划线表示查询节点63 的路径如下图3所示。0° Client0Server0Memory0Splitting andCombining the data0Double jump tablePointer of weights0met 目录存储表0storage node 2 storage node 3 storage node N storage node 10d1 d2 d3 … dn 4 3 2 1 0 12 20 39 45 51 55 59 63 65 71 76 89 0123 Bi-lin Shao 等 / AASRI Procedia 5 ( 2013 ) 120 – 1250图3. 节点 63 的搜索过程0Search(list, searchKey) x = list->header for i = list->level downto 1 do while x-> pointArray [i]->key < searchKey do //pointArray[] 是指针数组 x = x-> pointArray [i] and return x = x-> pointArray [1] if x->key = search then returnx->value else return failure Node Inserting.完成插入操作的主要步骤是:首先,定位节点的插入位置,其次创建新节点,最后修改改变指针值。插入操作将用于更新节点,其时间效率主要取决于定位算法的效率。 Insert(list, searchKey, newValue) local data1[MaxLevel] //data1[] 是辅助数组x = list->header for i = list->level downto 1 do while x-> pointArray [i]->key < searchKey do x = x-> pointArray [i]data1 [i]= x x = x-> pointArray [1] if x->key = search then x->value = newValue else lal = randomLevel() //|a|是一个随机生成的层 if lal > list->level then for i = list->level + 1 to |a| do data1 [i]= list->header list->level = |a| x= makeNode(lal, searchKey, newValue) for i = 1 to lal do x-> pointArray [i]= data1 [i]-> pointArray [i] data1 [i]->pointArray [i]= x Node Deleting.节点删除与插入类似。首先要定位需要删除的节点,然后判断是否找到该节点。如果能找到该节点,则修改相关指针值并删除节点。如果找不到该节点,则返回删除节点失败。节点删除的时间效率也取决于定位算法的效率。 Delete(list, searchKey) localdata1 [MaxLevel] //MaxLevel 是最大层次 x = list->header for i = list->level down to 1 do while x-> pointArray[i]->key < searchKey do x = x-> pointArray [i] --x->key < searchKey <= x-> pointArray ->key data1 [i]= x x = x->pointArray [1] if x->key = searchKey then00124 Bi-lin Shao 等 / AASRI Procedia 5 ( 2013 ) 120 – 1250for i = 1 to list->level do if data1 [i]-> pointArray [i]! = x then break data1 [i]-> pointArray [i]= x-> pointArray [i]free(x) while list->level > 1 and list->header-> pointArray [list->level]= NIL do list->level = list->level - 1 WeightsUpdating. 当存储节点被查询一次时,其权重值将增加1。在通过 DLPSL进行更新时,判断第一层节点的权重是否大于或等于5,如果节点的权重大于5,则节点序列将增加1,节点权重设置为零。通过这种方式,结合跳表中高级节点优先识别的属性,可以保证高定位率的节点能够快速找到,从而减少搜索时间。 Updata(list ,searchKey) If x->key = searchKey then priority ++ if priority >=5 then priority=0 and priority++04. 演示分析04.1 时间复杂度0引入了概率影响因子 p (p 通常取1/2数由0p L n n,L(n) 的最大值是:0( ) 1 (1 k ) n k L n p np0在 i 级链中有 n/2 i 个元素,当插入新元素时,新元素属于 i-级链的概率为 1/p。因此,新元素被识别为 i-级链元素的可能性是0log 1 p n ] + 1 对于一般的p。在这种情况下,每个(i-1)-级链中的每1/p个(i-1)-级链中有一个元素。跳表中的搜索、插入和删除操作的复杂度为O(n+MaxLevel),其中跳表中有n个元素。在最坏的情况下,只有一个最高层元素和所有剩余的元素都在0级链中。如果i>0,在i-级链中时间复杂度为O(MaxLevel),在0级链中时间复杂度为O(n)。跳表的每个操作(搜索、插入和删除)的平均复杂度为O(logn),证明如下:设m为层次,每个层次中有两个跳过最后a个元素的元素,时间复杂度为m T m na ma。0m 1 T m mna m,声明0 T m,然后01 m i a n,0m m m m T m n mn m n。0M值越大,a值越小,a的最小值为2。0然后1 2 2 1 log 2 m log n,1 2 1 log m n,2log 2 T m n。即时间复杂度是O(log)n。04.2 空间复杂度0空间复杂度,即在最坏情况下所有元素可能为MaxLevel-level,并且每个元素需要MaxLevel+1个指针。出于这个原因,n个元素需要被存储,同时链指针也需要被存储(所需空间为O(n *MaxLevel))。通常,只有1级链中的n*p个元素,2级链中的n*p 2个元素,以及i级链中的n*p i个元素。因此,指针字段的平均值(不包括头尾节点指针)为1/(2*log n)。0即i从1到log n,有n个元素。所以,总空间需求为:0S = n + n/2 + n/2 2 + ... + n/2log n < n (1 + 1/2 + 1/2 2 + ... + 1/2 ) =2n.0因此,其空间复杂度为2n = O(n)。0125 Bi-lin Shao et al. / AASRI Procedia 5 ( 2013 ) 120 – 1250在分布式环境中,跳跃图的时间复杂度是O(nlogn),空间复杂度是O(n)。在相同的环境中,本文提出的算法的时间复杂度优于跳跃图,而空间复杂度相同,整体上优于跳跃图算法。05. 结论0本文分析了现有分布式存储系统的数据定位机制的特点和缺点,并提出了权重值跳表分布式数据定位(DLPSL)策略,并设计和实现了分布式存储系统。分析表明,与单表存储结构和不带权重的双向链表结构相比,DLPSL的插入、删除和定位的效率更高,引入权重值可以更好地解决分布式存储系统中数据定位的问题,具有快速高效的搜索效率和更好的应用价值。0致谢0本文得到了中国国家自然科学基金(No.61073196&61272458)和中国山西省自然科学研究基金(No.2011JM8026)的支持。0通讯作者:0作者姓名:卞根庆 电子邮件:bgq_00@163.com 手机电话:13319273850通讯地址:西安建筑科技大学信息与控制工程学院 邮编:7100550参考文献0[1]Sikalinda P G, Walters L, Kritzinger P S. A storage system workload analyzer, CS06-02-00[R]. Cape Town, Universityof Cape Town,2006. [2]Chanho Ryu,Eunmi Song et al. Hybrid-TH: a Hybrid Access Mechanism for Real-TimeMemory-Resident Database Systems[C]// Real-Time Computing System and Applications. Proceeding of the FifthInternational Conference. Hiroshima, IEEE .1998:303-310. [3]LIN X,SHROFF N B. An optimization-based approach forQoS routing in high-bandwidth networks [J]. IEEE/ACM Transactions on Networking, 2006, 14(6): 1348-1361. [4] YueMa , Dayong Zhan,Yicheng Jin. DDM intersection area fast query algorithm Based on jump table [J] The computersimulation magazine,2005 22(7):46—49. [5] J.Aspnes and G.Shah. Skip graphs[J]. ACM Trans.on Algorithms, 20073(4):37—42. [6] Aspnes, J. ,Wieder, U. The expansion and mixing time of skip graphs with applications[C]//ACM. InSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. New York, ACM,2005:126–134.[7] Jun Ying, Binmao Yang.A kind of multiple index of large-scale data rapidly search algorithm [J]. Computer Sciencemagazine, 2009 36(3):258—260. [8]John Risson ,Tim Moors. Survey of research towards robust peer-to-peernetworks: Search methods[J] Computer Networks 2006, 50(17): 3485—3521. [9] William Pugh.Skip lists: aprobabilistic alternative to balanced trees[J]. Communications of the ACM June,1990,33(6):668-676. [10] W Pugh.Skip lists: a probabilistic alternative to balanced trees [J].Communications of the ACM, 1990, 33(6): 668-676. [11]Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ (Third Edition)[M]. Boston. Published byAddison-Wesley, 2006:85-126. [12] Hammurabi Mendes, Cristina G.Fernandes. A Concurrent Implementation of SkipGraphs[J]. Electronic notes in discrete mathematics.2009, 35:263-268.
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC关键绩效财务与客户指标详解
- 绘制企业战略地图:从财务到客户价值的六步法
- BSC关键绩效指标详解:财务与运营效率评估
- 手持移动数据终端:常见问题与WIFI设置指南
- 平衡计分卡(BSC):绩效管理与战略实施工具
- ESP8266智能家居控制系统设计与实现
- ESP8266在智能家居中的应用——网络家电控制系统
- BSC:平衡计分卡在绩效管理与信息技术中的应用
- 手持移动数据终端:常见问题与解决办法
- BSC模板:四大领域关键绩效指标详解(财务、客户、运营与成长)
- BSC:从绩效考核到计算机网络的关键概念
- BSC模板:四大维度关键绩效指标详解与预算达成分析
- 平衡计分卡(BSC):绩效考核与战略实施工具
- K-means聚类算法详解及其优缺点
- 平衡计分卡(BSC):从绩效考核到战略实施
- BSC:平衡计分卡与计算机网络中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)