外包数据中基于链表的B+树数据完整性检测算法研究

Data Integrity Checking Algorithm Research in Outsource Data based on B+Tree of the Linked List

外包数据是数据拥有者将自己的数据存储在第三方服务提供商的服务器上,数据完整性检测的目标是防止存储在不可信的第三方服务器上的数据被篡改,验证数据是否可信。在基于B+树完整性检测算法的研究基础上,提出一种基于链表的B+树完整性检测算法,给出算法的数据结构定义及分析验证过程。该算法数据结构是通过单循环链表与B+树相结合,动态的获取链表中数据的验证信息,同时在B+树的叶子结点存储一个链表,增加了存储空间效率。实验表明,当数据增大时,基于链表的B+树与B+树在查询时间上相比略有优势,在插入数据时,优势明显。

Outsourcing data is what the users store their own data in a third-party service provider＇s server,and the goal of data integrity checking protection is to prevent data which is in storage in a distrusted third-party server from being tampered and verify the data whether it is credible or not.Based on B ＋tree integrity checking algorithm in this paper,a data integrity checking algorithm based on B＋tree of the linked list has been put forward and the data structure definition of algorithm and the verification of analysis have been given. The scheme obtains the authentication information dynamically in linked list by means of combining single circular linked list with B ＋tree,at the same time,it can increase the storage space and efficiency by means of storing a linked list in leaf nodes of the B＋tree.Experiment shows that when the data increases,the B＋tree based on linked list has a slight advantage in comparison to B＋ in the query time,while when inserting data,the advantage is obvious.