账本索引跳表的构建方法及使用其的区块链账本处理方法

摘要

本发明提供一种账本索引跳表的构建方法，包括如下步骤：（1）构建账本索引跳表数组：账本索引跳表的内容由区块的哈希值组成，按区块链高度从小到大顺序排列；（2）构建账本索引跳表集合：每个区块中账本索引跳表集合由0个或多个账本索引跳表数组组成，每个数组最大存储28=256个元素，由区块高度决定，应当包含所有小于当前区块高度的跳表数组。本发明在区块链账本的区块中构建一种索引跳表，构建一种新的区块链账本数据结构，提升区块链账本的查询、校验、加载的效率，改进账本处理的并行度，降低等待时间，提高节点资源利用率。

说明书

技术领域

本发明涉及区块链技术领域，具体涉及一种账本索引跳表的构建方法及使用其的区块链账本处理方法。

背景技术

区块链账本中的区块按照发生的时间顺序，通过区块的哈希值串联而成，是链上交易记录和状态变化的日志记录。区块的数据结构中包括当前区块的高度、当前区块打包的时间戳、前一区块的高度、前一区块打包的时间戳、前一区块的哈希值、交易记录集、状态变化集合以及当前区块的哈希值。一般情况下，用正整数对区块进行编号，称之为区块高度。创世区块的高度默认为1，后续区块的高度按照步进1递增。区块哈希值根据构成区块数据结构中除当前区块哈希值之外的数据元素经过指定哈希算法得到。后一个区块内会记录前一个区块链的哈希值，形成单向链式结构。

在根据区块哈希值在区块链账本中查找区块时，其时间复杂度为O(n)，n为区块链账本的当前高度。随着区块链运行时间的增长，区块链的高度也日积月累，根据区块链哈希值查找区块的时间复杂度也在逐渐变长。

传统的区块的数据结构由以下要素组成：{版本号，前一区块高度，前一区块时间戳，前一区块哈希值，当前区块链交易集默克尔根，当前区块链账户状态集默克尔根，当前区块链高度，当前区块链时间戳，当前区块链哈希值}。

区块链的哈希值H = Hash（{版本号，前一区块高度，前一区块时间戳，前一区块哈希值，当前区块链交易集默克尔根，当前区块链账户状态集默克尔根，账本索引跳表集合，当前区块链高度，当前区块链时间戳}）。

总的说来，采用传统区块链数据结构存储账本的区块链存在如下问题：

a、查询效率低：查询过程必须从最新的区块开始，每次步进1，向前递推，区块高度越大，查询所需经过的区块越多，浪费的时间越多，因此导致随区块高度升高，查询效率逐渐线性降低。查询时间复杂度为O(n)。

b、校验效率低：当从最新的区块向前校验账本的有效性时，根据当前区块链中包含的前一区块的哈希值来校验前一区块的有效性，只能一个一个线性排队处理，处理完当前的账本，再去处理下一个账本。因此导致校验账本的效率低。

c、账本不支持并行处理：由于每个账本中只包含前一个账本的哈希值，导致账本的处理，如加载、校验、查询等没法并行处理，浪费节点的资源和增加账本的处理时间。

发明内容

本发明要解决的技术问题是提供一种账本索引跳表的构建方法及使用其的区块链账本处理方法，提升区块链账本的查询、校验、加载的效率，改进账本处理的并行度，降低等待时间，提高节点资源利用率。

为解决上述技术问题，本发明的实施例提供一种账本索引跳表的构建方法，包括如下步骤：

（1）构建账本索引跳表数组：账本索引跳表数组的内容由区块的哈希值组成，按区块链高度从小到大顺序排列；

（1-1）第一层账本索引跳表的步进幅度为2

（1-2）第二层账本索引跳表的步进幅度为2

（1-3）第三层账本索引跳表的步进幅度为2

（1-4）……，依次类推；

（2）构建账本索引跳表集合：每个区块中账本索引跳表集合由0个或多个账本索引跳表数组组成，每个数组最大存储2

（2-1）当区块高度等于1时，即创世区块，不包含任何账本索引跳表数组，账本索引集合为空；

（2-2）当区块高度大余1时，区块链由一个第一层账本索引跳表和0个或多个第二层及第N层账本索引跳表组成。

本发明还提供一种区块链账本处理方法，包括如下步骤：

步骤一、建立区块链账本的数据结构，包括采用上述的构建方法构建的账本索引跳表集合；

增加账本索引跳表后的区块链账本的数据结构包括：

版本号、前一区块高度、前一区块时间戳、前一区块哈希值、当前区块链交易集默克尔根、当前区块链账户状态集默克尔根、账本索引跳表集合、当前区块链高度、当前区块链时间戳和当前区块链哈希值；

步骤二、计算区块链的哈希值

区块链的哈希值H′= Hash（{版本号、前一区块高度、前一区块时间戳、前一区块哈希值、当前区块链交易集默克尔根、当前区块链账户状态集默克尔根、账本索引跳表集合、当前区块链高度、当前区块链时间戳}）；

步骤三、区块链账本的并行处理

账本加载、校验、查询过程从当前最新区块高度对应的区块中找到账本索引跳表集合，根据集合中的数组包含的区块哈希值数量，通过多线程账本处理函数，对每个Hash值对应的区块及其前置区块展开并行处理。

其中，步骤三中区块链账本查询的时间复杂度为O(log(n))。

本发明的上述技术方案的有益效果如下：本发明在区块链账本的区块中构建一种索引跳表，构建一种新的区块链账本数据结构，提升区块链账本的查询、校验、加载的效率，改进账本处理的并行度，降低等待时间，提高节点资源利用率。

附图说明

图1为本发明中账本索引跳表结构示意图；

图2为本发明中账本索引跳表数据构建方法示意图。

具体实施方式

为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附图及具体实施例进行详细描述。

一种账本索引跳表的构建方法，包括如下步骤：

（1）构建账本索引跳表数组：账本索引跳表数组的内容由区块的哈希值组成，按区块链高度从小到大顺序排列；

（1-1）第一层账本索引跳表的步进幅度为2

（1-2）第二层账本索引跳表的步进幅度为2

（1-3）第三层账本索引跳表的步进幅度为2

（1-4）……，依次类推；

（2）构建账本索引跳表集合：每个区块中账本索引跳表集合由0个或多个账本索引跳表数组组成，每个数组最大存储2

（2-1）当区块高度等于1时，即创世区块，不包含任何账本索引跳表数组，账本索引集合为空；

（2-2）当区块高度大余1时，区块链由一个第一层账本索引跳表和0个或多个第二层及第N层账本索引跳表组成。

其中，区块链账本跳表示意图见图2。

本发明还提供一种区块链账本处理方法，包括如下步骤：

步骤一、建立区块链账本的数据结构，包括采用上述的构建方法构建的账本索引跳表集合；

增加账本索引跳表后的区块链账本的数据结构包括：

版本号、前一区块高度、前一区块时间戳、前一区块哈希值、当前区块链交易集默克尔根、当前区块链账户状态集默克尔根、账本索引跳表集合、当前区块链高度、当前区块链时间戳和当前区块链哈希值；

步骤二、计算区块链的哈希值

区块链的哈希值H′= Hash（{版本号、前一区块高度、前一区块时间戳、前一区块哈希值、当前区块链交易集默克尔根、当前区块链账户状态集默克尔根、账本索引跳表集合、当前区块链高度、当前区块链时间戳}）；

其中，账本索引跳表结构见图1。

步骤三、区块链账本的并行处理

账本加载、校验、查询过程从当前最新区块高度对应的区块中找到账本索引跳表集合，根据集合中的数组包含的区块哈希值数量，通过多线程账本处理函数，对每个Hash值对应的区块及其前置区块展开并行处理。本步骤中，区块链账本查询的时间复杂度为O(log(n))。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。