梅克尔-B+树的并行构建方法及装置

摘要

本发明提供了一种梅克尔‑B+树的并行构建方法及装置，属于区块链技术领域，可用于数据处理领域，其中所述方法包含：获取交易数据，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应的线程区间；通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序，将排序后的叶子节点按线程数写入各线程对应的线程区间；于各线程内部串行构建梅克尔‑B+树，循环生成梅克尔‑B+子树各节点获得梅克尔‑B+子树；通过收口线程对各梅克尔‑B+子树的根节点串行构建梅克尔‑B+树，获得交易数据的梅克尔‑B+树，可快速定位交易以便给出交易的梅克尔证明。

说明书

技术领域

本发明涉及区块链技术领域，可应用于数据结构领域和金融领域，尤指一种梅克尔-B+树的并行构建方法及装置。

背景技术

区块链中区块一般使用梅克尔树结构组织，梅克尔树是二叉树。如图1A所示，有9笔交易打包成一个区块，交易之间可按照某个或某几个字段排序后写入区块，也可以不排序写入区块。串行地对每个交易生成哈希，然后将生成的哈希再往上两两生成哈希，不断重复，直到最终只剩下一个哈希值，就是梅克尔树根。若某一层节点个数为奇数，则在此节点旁边拷贝一个完全一样的节点，继续往上生成哈希，如图1A的第7笔交易所示。

上述梅克尔树生成方法存在以下问题：

在梅克尔树高度为0的叶子节点生成哈希，不存在依赖关系，可以采用并行算法并行生成哈希；对非叶节点两两生成哈希，则需等待非叶节点哈希生成，但等待的节点数与高度有关，其定量关系为：

D(h)＝2

其中h为梅克尔树的高度，D(h)为等待的节点数。图1A所示的梅克尔树，h＝0时无需等待，h＝1时等待节点数为2，树根h＝3需等待所有节点完成，等待树为14。因此在高度较低时，仍然存在相互之间无依赖关系的节点，由此传统的计算方法效率较低。

在梅克尔证明定位交易时，因梅克尔树没有提供索引结构，只能通过遍历方法定位交易，性能较低。即便交易可在区块中按照某个或某几个字段排序，仍然无法满足按其他字段快速定位交易的要求。

发明内容

本发明目的在于提供一种梅克尔-B+树的并行构建方法及装置，提高梅克尔树的构建速度，且构建出的梅克尔树为二叉平衡树；同时本发明提出一种并行建立B+树索引的方法，提高梅克尔证明时交易定位的速度。

为达上述目的，本发明所提供的梅克尔-B+树的并行构建方法，具体包含：获取交易数据，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应的线程区间；通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序，将排序后的叶子节点按线程数写入各线程对应的线程区间；于各线程内部串行构建梅克尔-B+树，循环生成梅克尔-B+子树各节点获得梅克尔-B+子树；通过收口线程对各梅克尔-B+子树的根节点串行构建梅克尔-B+树，获得交易数据的梅克尔-B+树。

在上述梅克尔-B+树的并行构建方法中，优选的，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应交易数量的线程区间包含：根据所述交易数据中的交易数量和预设线程数量计算每个线程所生成的梅克尔-B+树节点数量；根据所述梅克尔-B+树节点数量为每条线程分配对应的线程区间。

在上述梅克尔-B+树的并行构建方法中，优选的，通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序包含：通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字；根据记录的交易关键字获得数据值，利用所述数据值通过排序算法对各叶子节点进行排序。

在上述梅克尔-B+树的并行构建方法中，优选的，利用所述数据值通过排序算法对各叶子节点进行排序包含：排序后的叶子节点中相邻的高位节点内存储低位节点的指针。

在上述梅克尔-B+树的并行构建方法中，优选的，将排序后的叶子节点按线程数写入各线程对应的线程区间包含：排序后的叶子节点对应线程区间的低位址。

在上述梅克尔-B+树的并行构建方法中，优选的，循环生成梅克尔-B+子树各节点获得梅克尔-B+子树包含：同位叶子节点中两两节点求哈希获得相邻高位节点的哈希，并在非叶子节点记录交易关键字。

本发明还提供一种梅克尔-B+树的并行构建装置，所述装置包含空间分配模块、排序写入模块、构建模块和合并模块；所述空间分配模块用于获取交易数据，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应的线程区间；所述排序写入模块用于通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序，将排序后的叶子节点按线程数写入各线程对应的线程区间；所述构建模块用于在各线程内部串行构建梅克尔-B+树，循环生成梅克尔-B+子树各节点获得梅克尔-B+子树；所述合并模块用于通过收口线程对各梅克尔-B+子树的根节点串行构建梅克尔-B+树，获得交易数据的梅克尔-B+树。

在上述梅克尔-B+树的并行构建装置中，优选的，所述排序写入模块包含计算单元，所述计算单元用于根据所述交易数据中的交易数量和预设线程数量计算每个线程所生成的梅克尔-B+树节点数量；根据所述梅克尔-B+树节点数量为每条线程分配对应的线程区间。

在上述梅克尔-B+树的并行构建装置中，优选的，所述排序写入模块包含排序单元，所述排序单元用于通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字；根据记录的交易关键字获得数据值，利用所述数据值通过排序算法对各叶子节点进行排序。

本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述方法。

本发明还提供一种计算机可读存储介质，所述计算机可读存储介质存储有执行上述方法的计算机程序。

本发明的有益技术效果在于：可提高梅克尔的构建速度；构建出的梅克尔树满足二叉平衡树的定义，同时，通过B+树上的索引结构，可提高梅克尔树证明的速度。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不构成对本发明的限定。在附图中：

图1A为本发明一实施例所提供的梅克尔-B+树的计算流程示意图；

图1B为本发明一实施例所提供的梅克尔-B+树的并行构建方法的流程示意图；

图2为本发明一实施例所提供的梅克尔-B+树的并行构建方法的应用示意图；

图3为本发明一实施例所提供的线程划分线程区间的原理示意图；

图4为本发明一实施例所提供的划分线程区间的流程示意图；

图5为本发明一实施例所提供的叶子节点的排序流程示意图；

图6为本发明一实施例所提供的梅克尔-B+树的并行构建方法的原理流程示意图；

图7为本发明一实施例所提供的梅克尔-B+树的并行构建装置的结构示意图；

图8为本发明一实施例所提供的电子设备的结构示意图。

具体实施方式

以下将结合附图及实施例来详细说明本发明的实施方式，借此对本发明如何应用技术手段来解决技术问题，并达成技术效果的实现过程能充分理解并据以实施。需要说明的是，只要不构成冲突，本发明中的各个实施例及各实施例中的各个特征可以相互结合，所形成的技术方案均在本发明的保护范围之内。

另外，在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。

请参考图1B所示，本发明所提供的一种梅克尔-B+树的并行构建方法，具体包含：

步骤S101：获取交易数据，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应的线程区间；

步骤S102：通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序，将排序后的叶子节点按线程数写入各线程对应的线程区间；

步骤S103：于各线程内部串行构建梅克尔-B+树，循环生成梅克尔-B+子树各节点获得梅克尔-B+子树；

步骤S104：通过收口线程对各梅克尔-B+子树的根节点串行构建梅克尔-B+树，获得交易数据的梅克尔-B+树。

在上述实施例中，

1、交易个数与梅克尔树节点个数的关系如下：

设nTransation是交易个数,通过梅克尔树的定义可得到交易个数与梅克尔树节点个数的关系MerkleNodeCount(nTransation)：

令CurrentCount＝nTransation，总节点数记为TotalCount；

例如：

如图1A所示，给定nTransation＝9，因9为奇数，故高度0包含10个哈希，其中最后两个哈希均为交易9的哈希。针对高度0的10个哈希两两求哈希，得到5个哈希。因5是奇数，故高度1会生成6个哈希，其中最后两个哈希均为高度1最右侧哈希。以此类推，可得到高度2包含4个哈希，高度3包含2个哈希，高度4包含1个哈希，总节点数为23个。

2、交易个数、并行线程数与梅克尔子树节点个数的关系如下：

设nTransation是交易个数,令并行线程数为nThread＝2

有L个线程分配到K+1个交易；有nThread-L个线程分配到K个交易。依据第1节求得的MerkleNodeCount(nTransation)，可得所有线程需使用的空间为：

T(nThread)＝L*MerkleNodeCount(K+1)+(nThread-L)*MerkleNodeCount(K)

每个线程得到一棵默克尔子树，共有nThread棵子树。每棵子树的根节点需再往上构建梅克尔树。子树根节点构建的梅克尔树节点数为nThread-1，故总的梅克尔树节点数为：

MerkleNodeTotalCount(nTransation)＝T(nThread)+nThread-1

例如：

如图2所示，给定nTransation＝9，nThread＝2，则K＝4，L＝1,。线程1可分配到5个交易，线程2可分到4个交易。按第1节的算法，线程1会生成13个梅克尔树节点，线程2会生成7个梅克尔树节点。2个线程对应2棵梅克尔子树，其根节点会再往上生成1个梅克尔树节点。故并行算法构建的梅克尔树节点数为13+7+1＝21个。

请参考图4所示，在本发明一实施例中，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应交易数量的线程区间可包含：

步骤S401：根据所述交易数据中的交易数量和预设线程数量计算每个线程所生成的梅克尔树节点数量；

步骤S402：根据所述梅克尔树节点数量为每条线程分配对应的线程区间。

具体的，在实际工作中，上述实施例即为梅克尔-B+子树并行构建线程的空间预分配过程，如图6所示，步骤S601设nTransation是交易个数，则按照第2节求得的总节点数MerkleNodeTotalCount(nTransation)，可预先一次性分配内存，然后按每个线程所生成的梅克尔树节点数，为每个线程划分单独的区间，以便并行写入。

例如：如图3所示，线程1生成13个梅克尔树节点，占用1-13的空间；线程2生成7个梅克尔树节点，占用14-20的空间。

请参考图5所示，在本发明一实施例中，通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序包含：

步骤S501：通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字；

步骤S502：根据记录的交易关键字获得数据值，利用所述数据值通过排序算法对各叶子节点进行排序。其中，利用所述数据值通过排序算法对各叶子节点进行排序包含：排序后的叶子节点中相邻的高位节点内存储低位节点的指针。进一步的，将排序后的叶子节点按线程数写入各线程对应的线程区间包含：排序后的叶子节点对应线程区间的低位址。同时，循环生成梅克尔子树各节点获得梅克尔子树包含：同位叶子节点中两两节点求哈希获得相邻高位节点的哈希，并在非叶子节点记录交易关键字。

在实际工作中，上述实施例即为开口线程对默克尔-B+树叶子节点按升/降序排序过程，如图6所示，步骤S602因B+树要求叶子节点按照升序或降序排序，故并行构建前，由开口线程在叶子节点记录交易关键字，并对叶子节点排序。可使用现有的排序算法实现。排序后的上一节点需存储下一节点的指针，以便做范围查询时快速遍历。排序后的叶子节点按线程数写入各线程的预分配空间中，对应线程空间的低地址。

例如：

如图2所示，DATA为交易关键字，叶子节点记录DATA的值，并按照DATA升序排序。排序后每个节点保存有指向下一个节点的指针。因nThread＝2，因此线程1分配到的叶子节点数为5个，写入空间1-5；线程2分配到的叶子节点数为4个，写入空间14-17。

如图6所示，步骤S603所示，并行线程内部构件梅克尔-B+子树的过程即为前述图1B中的步骤S103，在每个并行线程的内部串行构建梅克尔-B+树的方式，循环生成梅克尔-B+子树各节点。其方法为两两节点求得上一节点的哈希，并在非叶子节点记录关键字。非叶子节点的结构包括：左子树最大值(含，记为LMax)、左右子树哈希、右子树最大值(含，记为RMax)。若当前非叶子节点的子节点为叶子节点，则直接记录左叶子节点的关键字到LMax，记录右叶子节点的关键字到RMax；若当前非叶子节点的子节点为非叶节点，则记录左子树根节点的RMax到自身的LMax，记录右子树根节点的RMax到自身的RMax。

最终梅克尔-B+子树根节点写入各并行线程空间的最后一个节点。

例如：

如图2所示，线程1处理哈希1、哈希2、哈希3、哈希4、哈希5。哈希1和哈希2两两生成非叶子节点哈希12，并记录LMax＝1，RMax＝11。因哈希5为奇数，故拷贝一份哈希5，两两生成非叶子哈希55，并记录LMax＝20，RMax＝20。哈希12和哈希34两两生成非叶子节点哈希1-4，并记录LMax＝11，RMax＝12。最终各线程建立的梅克尔-B+子树如图2所示。

如图6所示，步骤S604所示，收口线程对梅克尔-B+子树根节点构建梅克尔-B+树的过程包含：

等待各并行线程完成梅克尔-B+子树构建后，需由收口线程对各梅克尔-B+子树根节点构建梅克尔-B+树。收口线程分配的空间大小为nThread-1，其中nThread为并行线程数。梅克尔-B+子树根节点在各并行线程空间的最后一个节点，按照第1和第2节可得,第iTree(iTree＝1,2,..)棵梅克尔-B+子树根节点所在的位置P(iTree)为：

当iTree<＝L时为：

P(iTree)＝iTree*iTreeMerkleNodeCount(K+1)

当L

P(iTree)＝L*MerkleNodeCount(K+1)+iTree*MerkleNodeCount(K)

收口线程划分的空间为剩余的nThread-1个节点，可从各梅克尔-B+子树根节点再串行构建梅克尔-B+树，构建方法同第5节。

最终构建出来的梅克尔-B+树满足二叉平衡树定义。

例如：

如图3所示，线程1构建的梅克尔-B+子树根节点在空间第13的位置，线程2构建的梅克尔-B+子树根节点在空间第20的位置，收口线程写入的根节点在空间第21的位置。

如图2所示，收口线程对对哈希1-5和哈希6-9两两生成哈希1-9，并记录LMax＝20，RMax＝31。

图2所示为最终构建的梅克尔-B+树，满足二叉平衡树定义。

请参考图7所示，本发明还提供一种梅克尔-B+树的并行构建装置，所述装置包含空间分配模块、排序写入模块、构建模块和合并模块；所述空间分配模块用于获取交易数据，根据所述交易数据中的交易数量和预设线程数量为每条线程分配对应的线程区间；所述排序写入模块用于通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字，根据记录的交易关键字的值对各叶子节点进行排序，将排序后的叶子节点按线程数写入各线程对应的线程区间；所述构建模块用于在各线程内部串行构建梅克尔-B+树，循环生成梅克尔-B+子树各节点获得梅克尔-B+子树；所述合并模块用于通过收口线程对各梅克尔-B+子树的根节点串行构建梅克尔-B+树，获得交易数据的梅克尔-B+树。

在上述实施例中，所述排序写入模块包含计算单元，所述计算单元用于根据所述交易数据中的交易数量和预设线程数量计算每个线程所生成的梅克尔-B+树节点数量；根据所述梅克尔-B+树节点数量为每条线程分配对应的线程区间。

在本发明另一实施例中，所述排序写入模块包含排序单元，所述排序单元用于通过开口线程在叶子节点记录所述交易数据中各交易的交易关键字；根据记录的交易关键字获得数据值，利用所述数据值通过排序算法对各叶子节点进行排序。

本发明的有益技术效果在于：可提高梅克尔-B+树的构建速度；构建出的梅克尔-B+树满足二叉平衡树的定义，同时，通过B+树上的索引结构，可提高梅克尔树证明的速度。

本发明还提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述方法。

本发明还提供一种计算机可读存储介质，所述计算机可读存储介质存储有执行上述方法的计算机程序。

如图8所示，该电子设备600还可以包括：通信模块110、输入单元120、音频处理单元130、显示器160、电源170。值得注意的是，电子设备600也并不是必须要包括图8中所示的所有部件；此外，电子设备600还可以包括图8中没有示出的部件，可以参考现有技术。

如图8所示，中央处理器100有时也称为控制器或操作控件，可以包括微处理器或其他处理器装置和/或逻辑装置，该中央处理器100接收输入并控制电子设备600的各个部件的操作。

其中，存储器140，例如可以是缓存器、闪存、硬驱、可移动介质、易失性存储器、非易失性存储器或其它合适装置中的一种或更多种。可储存上述与失败有关的信息，此外还可存储执行有关信息的程序。并且中央处理器100可执行该存储器140存储的该程序，以实现信息存储或处理等。

输入单元120向中央处理器100提供输入。该输入单元120例如为按键或触摸输入装置。电源170用于向电子设备600提供电力。显示器160用于进行图像和文字等显示对象的显示。该显示器例如可为LCD显示器，但并不限于此。

该存储器140可以是固态存储器，例如，只读存储器(ROM)、随机存取存储器(RAM)、SIM卡等。还可以是这样的存储器，其即使在断电时也保存信息，可被选择性地擦除且设有更多数据，该存储器的示例有时被称为EPROM等。存储器140还可以是某种其它类型的装置。存储器140包括缓冲存储器141(有时被称为缓冲器)。存储器140可以包括应用/功能存储部142，该应用/功能存储部142用于存储应用程序和功能程序或用于通过中央处理器100执行电子设备600的操作的流程。

存储器140还可以包括数据存储部143，该数据存储部143用于存储数据，例如联系人、数字数据、图片、声音和/或任何其他由电子设备使用的数据。存储器140的驱动程序存储部144可以包括电子设备的用于通信功能和/或用于执行电子设备的其他功能(如消息传送应用、通讯录应用等)的各种驱动程序。

通信模块110即为经由天线111发送和接收信号的发送机/接收机110。通信模块(发送机/接收机)110耦合到中央处理器100，以提供输入信号和接收输出信号，这可以和常规移动通信终端的情况相同。

基于不同的通信技术，在同一电子设备中，可以设置有多个通信模块110，如蜂窝网络模块、蓝牙模块和/或无线局域网模块等。通信模块(发送机/接收机)110还经由音频处理器130耦合到扬声器131和麦克风132，以经由扬声器131提供音频输出，并接收来自麦克风132的音频输入，从而实现通常的电信功能。音频处理器130可以包括任何合适的缓冲器、解码器、放大器等。另外，音频处理器130还耦合到中央处理器100，从而使得可以通过麦克风132能够在本机上录音，且使得可以通过扬声器131来播放本机上存储的声音。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。