CN112559529A - 数据存储方法、装置、计算机设备及存储介质 - Google Patents

Abstract

本发明涉及区块链领域，公开了一种数据存储方法、装置、计算机设备及存储介质，其方法包括：新建事务，事务包括若干增加指令；在事务结束前，根据增加指令添加新增临时节点；在事务结束后，使新增临时节点分裂为若干个分裂节点，并计算分裂节点的哈希值；更新目标父节点的键值对列表，判断目标父节点的键值对列表的长度是否超出第二预设阈值；若超出第，则继续对目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。本发明通过使事务处理与节点分裂异步处理，同时耦合节点分裂和哈希计算，可以提高事务处理效率，减少事务型默克尔B+树的路径，索引值时IO次数少，缩短磁盘读写时间。

Description

数据存储方法、装置、计算机设备及存储介质

技术领域

本发明涉及区块链领域，尤其涉及一种数据存储方法、装置、计算机设备及存储介质。

背景技术

现有技术中，MPT(Merkle Patricia Tree，梅克尔帕特里夏树)是一种常见的，用于存储区块链数据的算法。MPT使用leveldb数据库(谷歌公司开发的一种数据库)存储数据，存在读放大写放大问题。另外，MPT按前缀索引，读取路径长，造成哈希计算次数多，影响访问性能。而且，数据存储过程中，频繁的编码解码，消耗了大量的计算资源，存储效率差。

发明内容

基于此，有必要针对上述技术问题，提供一种数据存储方法、装置、计算机设备及存储介质，以解决现有区块链数据存储效率低的问题。

一种数据存储方法，包括：

新建事务，所述事务包括若干增加指令；

在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

一种数据存储装置，包括：

新建模块，用于新建事务，所述事务包括若干增加指令；

节点新增模块，用于在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

第一节点分裂模块，用于在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

长度判断模块，用于更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

第二节点分裂模块，用于若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

一种计算机设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机可读指令，所述处理器执行所述计算机可读指令时实现上述数据存储方法。

一个或多个存储有计算机可读指令的可读存储介质，所述计算机可读指令被一个或多个处理器执行时，使得所述一个或多个处理器执行如上述数据存储方法。

上述数据存储方法、装置、计算机设备及存储介质中，新建事务，所述事务包括若干增加指令，以通过增加指令在事务型默克尔B+树增加数据。在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点，在此处，仅涉及增加指令的执行，不进行节点分裂，也不需要进行哈希计算，可以节省计算资源，减少事务处理时间。在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值，在此处，将节点分裂与哈希计算耦合在一起，减少了分裂后再次计算哈希的不必要索引时间，提高存储效率。更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点，以保证目标父节点目标父节点的键值对列表的长度不超出第二预设阈值。若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值，以实现所有节点的完全分裂，消除键值对列表长度超出其对应的预设阈值的节点的存在。本发明通过使事务处理与节点分裂异步处理，同时耦合节点分裂和哈希计算，可以提高事务处理效率，减少事务型默克尔B+树的路径，索引值时IO次数少，缩短磁盘读写时间。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例的描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1是本发明一实施例中数据存储方法的一应用环境示意图；

图2是本发明一实施例中数据存储方法的一流程示意图；

图3是本发明一实施例中执行新增指令前一事务型默克尔B+树的结构图；

图4是本发明一实施例中执行新增指令后一事务型默克尔B+树尚未进行节点分裂的结构图；

图5是本发明一实施例中执行新增指令后一事务型默克尔B+树进行节点分裂后的结构图；

图6是本发明一实施例中key值为20生成的默克尔证明；

图7是本发明一实施例中数据存储装置的一结构示意图；

图8是本发明一实施例中计算机设备的一示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本实施例提供的数据存储方法，可应用在如图1的应用环境中，其中，客户端与服务端进行通信。其中，客户端包括但不限于各种个人计算机、笔记本电脑、智能手机、平板电脑和便携式可穿戴设备。服务端可以用独立的服务器或者是多个服务器组成的服务器集群来实现。

在一实施例中，如图2所示，提供一种数据存储方法，以该方法应用在图1中的服务端为例进行说明，包括如下步骤。

S10、新建事务，所述事务包括若干增加指令。

在此处，一个事务包括了若干执行指令，如增加指令、删除指令、修改指令、查询指令等。由于删除指令、修改指令、查询指令均不涉及节点分裂，其具体处理步骤可参照现有的处理方式，在此不再赘述。本实施例重点介绍事务中增加指令的处理过程。需要注意的是，在此处，若某处节点数据的执行指令既涉及数据的修改，也涉及数据的增加，则将该指令视为增加指令。

S20、在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点。

可理解地，事务结束指的是事务内所有指令均执行完毕。事务结束前则指的是事务内存在至少一个指令未被执行完毕。在此处，在事务内不进行节点分裂，可以减少事务内执行指令的计算资源占用量。事务型默克尔B+树(Multi-version verifiable)为默克尔B+树的一种变体。事务型默克尔B+树以默克尔B+树的结构存储了若干节点数据。目标节点指的是增加指令指定的存储位置。在一些示例中，增加指令需要在某个叶子节点下增加数据，此时，该叶子节点即为目标节点。添加了新增数据的目标节点，即为新增临时节点。

在一示例中，如图3和图4所示，图3为执行新增指令前一事务型默克尔B+树的结构图，图4为执行新增指令后一事务型默克尔B+树尚未进行节点分裂的结构图。其中，通过新增指令在图3中的Hash3节点(即目标节点)处增加了{Key：35，Value：I}，{Key：37，Value：J}这两个键值对(即新增数据)，得到图4中的Hash3节点(即新增临时节点)。

S30、在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值。

可理解地，在事务结束后，所有的指令都已执行。分裂处理指的是按一定的分裂规则将超出第一预设阈值的新增临时节点分割为两个或两个以上节点。分割出的节点，即为分裂节点。第一预设阈值可以根据实际需要进行设置。每个分裂节点的键值对列表长度均不超出第一预设阈值。在一示例中，分裂规则可以设置为，将新增临时节点分割为N+1个分裂节点，前N个分裂节点的键值对列表长度为第一预设阈值，第N+1个分裂节点的键值对列表长度小于或等于第一预设阈值，其中，N为大于或等于1的整数。

S40、更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点。

可理解地，目标父节点为目标节点的父节点。在进行分裂后，目标父节点包括不需要进行分裂的子节点，也包括分裂出的分裂节点。由于新增了多个分裂节点，需要分裂处理后的对目标父节点的键值对列表进行更新。具体的，目标父节点的键值对列表，包含各个子节点的键值对列表的第一个Key。也就是说，更新后的目标父节点的键值对列表，增加了N个分裂节点的Key值(N为分裂节点的个数减一)。然后判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值。第二预设阈值可以根据实际需要进行设置。在一些情况下，第一阈值可以与第二预设阈值相等。

在图4和图5的示例中，Hash3节点(图4)可分裂为Hash3节点(图5)和Hash4节点(图5)，此时Hash5节点(即为目标父节点，未图示)的键值对列表为：{15,20,30,37}，该键值对列表超出了第二预设阈值(其值为3)，需要对Hash5节点进行分裂，分裂为Hash5节点(图5)和Hash6节点(图5)。

在进行分裂的同时，需要重新计算各个分裂节点的哈希值。具体的，可以分别计算目标父节点下各个子节点的哈希值，然后将这些哈希值组成数组，计算该数组的哈希值，即为目标父节点的哈希值。当子节点为叶子节点，叶子节点内存储的键值对组成数组，计算数组的哈希值，即为该叶子节点的哈希值。当子节点为非叶子节点，则计算非叶子节点下各个节点的哈希值，然后将这些哈希值组成数组，计算该数组的哈希值，即为非叶子节点的哈希值。

S50、若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

可理解地，若分裂处理后的目标父节点的键值对列表长度不超出第二预设阈值，则不需要进行分裂处理。若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对目标父节点进行分裂处理。需要注意的是，在此处，“继续”表示需要再次执行一次分裂处理，但其分裂的对象与第一次分裂处理的对象不同。第一次分裂处理的对象为新增临时节点，继续分裂处理的对象为目标父节点。目标父节点的分裂处理方式可以与新增临时节点的分裂处理方式相同，即按一定的分裂规则将超出第二预设阈值的目标父节点分割为两个或两个以上节点。同理，需要对涉及变动的节点进行判断，判断其键值对列表长度时是否超出各自对应的预设阈值，若不超出，则不需要进行分裂处理，若超出，则需要进行分裂处理。

步骤S10-S50中，新建事务，所述事务包括若干增加指令，以通过增加指令在事务型默克尔B+树上增加数据。在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点，在此处，仅涉及增加指令的执行，不进行节点分裂，也不需要进行哈希计算，可以节省计算资源，减少事务处理时间。在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值，在此处，将节点分裂与哈希计算耦合在一起，减少了分裂后再次计算哈希的不必要索引时间，提高存储效率。更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点，以保证目标父节点目标父节点的键值对列表的长度不超出第二预设阈值。若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值，以实现所有节点的完全分裂，消除键值对列表长度超出其对应的预设阈值的节点的存在。本实施例中，通过使事务处理与节点分裂异步处理，同时耦合节点分裂和哈希计算，可以提高事务处理效率，减少事务型默克尔B+树的路径，索引值时IO次数少，缩短磁盘读写时间。

可选的，步骤S50，即所述若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值，包括：

S501、在目标父父节点下新增分裂父节点，所述目标父父节点为分裂父节点的父节点；

S502、将排序在后的一个或多个分裂节点的键值对列表的第一个键添加至所述分裂父节点的键值对列表，以使所述目标父节点的键值对列表长度不超出所述第二预设阈值，并检查所述目标父父节点和所述分裂父节点的键值对列表长度，以确保所述目标父父节点和所述分裂父节点的键值对列表长度不超出各自对应的预设阈值。

可理解地，目标父父节点为目标父节点和分裂父节点的父节点。分裂父节点与目标父节点同为目标父父节点的子节点。分裂父节点为目标父父节点下新建的子节点。在一些情况下，若目标父节点为根节点，此处需要新建目标父父节点，然后将目标父父节点设置为根节点，而目标父节点设置为目标父父节点的子节点。在图5的示例中，目标父父节点为Hash7节点，目标父节点为Hash5节点，分裂父节点为Hash6节点。

在生成分裂父节点后，可以移除目标父节点的键值对列表中超出预设阈值的键(即排序在后的一个或多个分裂节点的键值对列表的第一个键)。将移除的键添加至分裂父节点的键值对列表。此时，分裂节点为分裂父节点的子节点。然后检查目标父父节点和分裂父节点的键值对列表长度，以确保目标父父节点和分裂父节点的键值对列表长度不超出各自对应的预设阈值。如，目标父父节点的键值对列表长度不超出第三预设阈值(目标父父节点对应的预设阈值，可以根据实际需要进行设置)，分裂父节点的键值对列表长度不超出第二预设阈值。若目标父父节点和分裂父节点的键值对列表长度不超出各自对应的预设阈值，则不需要继续进行分裂处理，若超出，则需要进行分裂处理。在图4中，原Hash3节点包含键37，进行节点分裂后，原Hash3节点分为Hash3节点(图5)和Hash4节点(图5)，而Hash7节点(图5)则新增了Hash6节点，此时需要将Hash4节点的键值对列表的第一个键37添加至Hash6节点的键值对列表中。同时检查各个节点的键值对列表长度。Hash7节点和Hash6节点由于其长度没有超出预设阈值，因而，不需要继续分裂处理。

可选的，步骤S50之后，即所述若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值之后，还包括：

S60、接收特定数据的证明请求；

S70、基于所述证明请求生成所述特定数据的默克尔证明，所述默克尔证明包括所述特定数据所在叶子节点到根节点的路径。

可理解地，特定数据指的是需要验证的某个数据。例如，需要证明某个数据在数据库的可用性。默克尔证明可以验证特定数据在数据库的可用性。默克尔证明包括特定数据所在叶子节点到根节点的路径。在图6的示例中，特定数据为：key＝20，特定数据所在叶子节点到根节点的路径包括：Hash7节点下的两个子节点的哈希值Hash5和Hash6，Hash5节点下的三个子节点的哈希值Hash1、Hash2和Hash3，以及Hash2节点下的所有键值对：{K：20，V：D；K：25，V：E；K：29，V：F}。也就是说，默克尔证明包括了特定数据所在叶子节点到根节点的路径下所有叶子节点的键值对以及所有非叶子节点的子节点的哈希值。

可选的，步骤S70，即所述基于所述证明请求生成所述特定数据的默克尔证明之后，还包括：

S80、根据所述默克尔证明计算所述特定数据的验证哈希值；

S90、当所述验证哈希值与所述事务型默克尔B+树更新后的根节点哈希值相等时，判定所述特定数据存储于事务型默克尔B+树中。

可理解地，由于节点分裂与哈希计算是同步进行的。因而，在节点分裂完成时，事务型默克尔B+树的根节点哈希值也更新完毕。用户拿到默克尔证明后，可以根据该节点路径计算出一个验证哈希值，并与事务型默克尔B+树更新后的根节点哈希值(即为事务生成的全局数据哈希摘要)进行比对，进而验证数据在数据库的可用性。当验证哈希值与根节点哈希值相等时，判定特定数据存储于事务型默克尔B+树中。当验证哈希值与根节点哈希值不相等时，判定特定数据不存储于事务型默克尔B+树中。

可理解地，步骤S50，即所述若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值之后，还包括：

S61、按照预设写入规则将所述事务涉及的脏节点写入磁盘中。

可理解地，预设写入规则可以根据实际需要设置。在此处，预设写入规则可以规定不同类型节点数据对应不同的存储方式。脏节点指的是从涉及修改的叶子节点数据(包括)至根节点(包括)上的任意一个节点。根据预设写入规则将修改版本的脏节点写入磁盘中时，所有脏节点都需要写入。

可选的，所述预设写入规则包括：

非叶子节点存储于单文件中，存储方式为缓存IO。

在此处，非叶子节点的占用空间往往小于叶子节点。可以将叶子节点存储在单文件中，以缓存IO(buffer IO)方式存储。在读取非叶子节点时，非叶子节点所在的文件可以直接映射到内存中。以单文件的存储方式、缓存IO的形式，使非叶子节点所在的文件缓存在内存中，提高了非叶子节点的访问性能。

可选的，所述预设写入规则包括：

叶子节点存储于多文件中，存储方式为直接IO。

在此处，叶子节点的占用空间大，无法将其全部存在内存中。因而可以采用直接IO(direct IO)的方式存储。只需要在读写时单，独读写某个磁盘页，只加载最近访问的一个或者多个叶子节点数据于内存中，减少内存占用，加快访问速度。

可选的，步骤S30中，即所述计算所述分裂节点的哈希值，包括：

S301、若所述分裂节点为叶子节点，根据该分裂节点的键值对列表计算其哈希值；

S302、若所述分裂节点为非叶子节点，根据该分裂节点的子节点的哈希值计算其哈希值。

可理解地，当分裂节点为叶子节点时，可以将该分裂节点内存储的键值对组成数组，计算该数组的哈希值，即为该分裂节点的哈希值。

当分裂节点为非叶子节点时，可以将该分裂节点的子节点的哈希值组成数据，计算该数组的哈希值，即为该分裂节点的哈希值。

应理解，上述实施例中各步骤的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本发明实施例的实施过程构成任何限定。

在一实施例中，提供一种数据存储装置，该数据存储装置与上述实施例中数据存储方法一一对应。如图7所示，该数据存储装置包括新建模块10、节点新增模块20、第一节点分裂模块30、长度判断模块40和第二节点分裂模块50。各功能模块详细说明如下：

新建模块10，用于新建事务，所述事务包括若干增加指令；

节点新增模块20，用于在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

第一节点分裂模块30，用于在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

长度判断模块40，用于更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

第二节点分裂模块50，用于若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

可选的，第二节点分裂模块50包括：

父节点分裂单元，用于在目标父父节点下新增分裂父节点，所述目标父父节点为分裂父节点的父节点；

分裂节点移动单元，用于将排序在后的一个或多个分裂节点移动至所述分裂父节点，以使所述目标父节点的键值对列表长度不超出所述第二预设阈值，并检查所述目标父父节点和所述分裂父节点的键值对列表长度，以确保所述目标父父节点和所述分裂父节点的键值对列表长度不超出各自对应的预设阈值。

可选的，数据存储装置还包括：

证明请求模块，用于接收特定数据的证明请求；

生成默克尔证明模块，用于基于所述证明请求生成所述特定数据的默克尔证明，所述默克尔证明包括所述特定数据所在叶子节点到根节点的路径。

可选的，数据存储装置还包括：

验证计算模块，用于根据所述默克尔证明计算所述特定数据的验证哈希值；

验证结果模块，用于当所述验证哈希值与所述事务型默克尔B+树更新后的根节点哈希值相等时，判定所述特定数据存储于事务型默克尔B+树中。

可选的，数据存储装置还包括：

数据写入模块，用于按照预设写入规则将所述事务涉及的脏节点写入磁盘中。

可选的，所述预设写入规则包括：

非叶子节点存储于单文件中，存储方式为缓存IO。

可选的，所述预设写入规则包括：

叶子节点存储于多文件中，存储方式为直接IO。

可选的，第一节点分裂模块30包括：

第一哈希计算单元，用于若所述分裂节点为叶子节点，根据该分裂节点的键值对列表计算其哈希值；

第二哈希计算单元，用于若所述分裂节点为非叶子节点，根据该分裂节点的子节点的哈希值计算其哈希值。

关于数据存储装置的具体限定可以参见上文中对于数据存储方法的限定，在此不再赘述。上述数据存储装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。

在一个实施例中，提供了一种计算机设备，该计算机设备可以是服务器，其内部结构图可以如图8所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口和数据库。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括可读存储介质、内存储器。该可读存储介质存储有操作系统、计算机可读指令和数据库。该内存储器为可读存储介质中的操作系统和计算机可读指令的运行提供环境。该计算机设备的数据库用于存储数据存储方法所涉及的数据。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机可读指令被处理器执行时以实现一种数据存储方法。本实施例所提供的可读存储介质包括非易失性可读存储介质和易失性可读存储介质。

在一个实施例中，提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机可读指令，处理器执行计算机可读指令时实现以下步骤：

新建事务，所述事务包括若干增加指令；

在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

在一个实施例中，提供了一个或多个存储有计算机可读指令的计算机可读存储介质，本实施例所提供的可读存储介质包括非易失性可读存储介质和易失性可读存储介质。可读存储介质上存储有计算机可读指令，计算机可读指令被一个或多个处理器执行时实现以下步骤：

新建事务，所述事务包括若干增加指令；

在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机可读指令来指令相关的硬件来完成，所述的计算机可读指令可存储于一非易失性可读取存储介质或易失性可读存储介质中，该计算机可读指令在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。

所属领域的技术人员可以清楚地了解到，为了描述的方便和简洁，仅以上述各功能单元、模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能单元、模块完成，即将所述装置的内部结构划分成不同的功能单元或模块，以完成以上描述的全部或者部分功能。

以上所述实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围，均应包含在本发明的保护范围之内。

Claims (10)

1.一种数据存储方法，其特征在于，包括：

新建事务，所述事务包括若干增加指令；

在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

2.如权利要求1所述的数据存储方法，其特征在于，所述若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值，包括：

在目标父父节点下新增分裂父节点，所述目标父父节点为分裂父节点的父节点；

将排序在后的一个或多个分裂节点的键值对列表的第一个键添加至所述分裂父节点的键值对列表，以使所述目标父节点的键值对列表长度不超出所述第二预设阈值，并检查所述目标父父节点和所述分裂父节点的键值对列表长度，以确保所述目标父父节点和所述分裂父节点的键值对列表长度不超出各自对应的预设阈值。

3.如权利要求1或2所述的数据存储方法，其特征在于，所述若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值之后，还包括：

接收特定数据的证明请求；

基于所述证明请求生成所述特定数据的默克尔证明，所述默克尔证明包括所述特定数据所在叶子节点到根节点的路径。

4.如权利要求3所述的数据存储方法，其特征在于，所述基于所述证明请求生成所述特定数据的默克尔证明之后，还包括：

根据所述默克尔证明计算所述特定数据的验证哈希值；

当所述验证哈希值与所述事务型默克尔B+树更新后的根节点哈希值相等时，判定所述特定数据存储于事务型默克尔B+树中。

5.如权利要求1或2所述的数据存储方法，其特征在于，所述若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值之后，还包括：

按照预设写入规则将所述事务涉及的脏节点写入磁盘中。

6.如权利要求5所述的数据存储方法，其特征在于，所述预设写入规则包括：

非叶子节点存储于单文件中，存储方式为缓存IO；

叶子节点存储于多文件中，存储方式为直接IO。

7.如权利要求1所述的数据存储方法，其特征在于，所述计算所述分裂节点的哈希值，包括：

若所述分裂节点为叶子节点，根据该分裂节点的键值对列表计算其哈希值；

若所述分裂节点为非叶子节点，根据该分裂节点的子节点的哈希值计算其哈希值。

8.一种数据存储装置，其特征在于，包括：

新建模块，用于新建事务，所述事务包括若干增加指令；

节点新增模块，用于在所述事务结束前，根据所述增加指令将新增数据添加在事务型默克尔B+树的目标节点上，得到新增临时节点；

第一节点分裂模块，用于在所述事务结束后，分裂处理键值对列表长度超出第一预设阈值的新增临时节点，使所述新增临时节点分裂为若干个键值对列表长度不超出所述第一预设阈值的分裂节点，并计算所述分裂节点的哈希值；

长度判断模块，用于更新分裂处理后的目标父节点的键值对列表，判断分裂处理后的目标父节点的键值对列表的长度是否超出第二预设阈值，所述目标父节点为所述目标节点的父节点；

第二节点分裂模块，用于若分裂处理后的目标父节点的键值对列表长度超出第二预设阈值，则继续对所述目标父节点进行分裂处理，直至所有节点的键值对列表长度不超出各自对应的预设阈值。

9.一种计算机设备，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机可读指令，其特征在于，所述处理器执行所述计算机可读指令时实现如权利要求1至7中任一项所述数据存储方法。

10.一个或多个存储有计算机可读指令的可读存储介质，所述计算机可读指令被一个或多个处理器执行时，使得所述一个或多个处理器执行如权利要求1至7中任一项所述数据存储方法。

Images