CN109690522B - 一种基于b+树索引的数据更新方法、装置及存储装置 - Google Patents

Abstract

本申请公开了一种基于B+树索引的数据更新方法、装置及存储装置，所述方法利用写时复制的方式对数据进行修改，所述方法包括：获取需要更新的数据的节点，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点；将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址；修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。通过上述方式，本申请能够消除CoW B+树级联CoW操作，减少开销。

Description

一种基于B+树索引的数据更新方法、装置及存储装置

技术领域

本申请涉及软件技术领域，特别是涉及一种基于B+树索引的数据更新方法、装置及存储装置。

背景技术

写时复制(Copy-on-Write，CoW)B+树(B+-tree)技术被广泛应用在计算机软件中，例如Btrfs(Butter FS)文件系统以及LMDB(Lightning Memory-Mapped Database，LMDB)数据库。CoW技术是实现多版本并发控制的一种手段，写操作会触发系统产生一个新版本的数据，而读操作仍旧在当前已完成的最新版本上进行。这使得读写操作在不同版本的数据上进行，读操作无需封锁，提高效率。请参阅图1，图1是现有技术中写时复制的读写操作示意图，如果进程P1需要对叶子节点C进行修改，它不会在该数据页C上直接修改数据，而是会复制出新的数据页C’，然后进程P1在C’上修改数据。这种情况下，读写操作互不冲突，无需加锁。本申请的发明人在长期的研究中，发现这种方法存在一定的弊端：第一、这种修改的代价比较大，叶子节点的修改会一直向上扩散到树的根节点。如图1所示，叶子节点C的修改会导致CoW动作沿着通往根节点A的路径进行下去(C--->B--->A)。第二、CoW B+树在事务提交时刻，指针修改完成以后，会执行刷盘动作，这个导致写入放大与随机IO问题严重。第三、为了尽量减少这种写时复制带来的代价，CoW B+树不会将叶子节点链接起来，对于范围查找很不友好。

发明内容

本申请主要解决的技术问题是提供一种基于B+树索引的数据更新方法、装置及存储装置，能够消除CoW B+树在更新修改时的级联操作，减少开销。

为解决上述技术问题，本申请采用的一个技术方案是：提供一种基于B+树索引的数据更新方法，其中，所述方法利用写时复制的方式对数据进行修改，所述方法包括：获取需要更新的数据的节点，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点；将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址；修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。

为解决上述技术问题，本申请采用的一个技术方案是：提供一种基于B+树索引的数据更新装置，其中，所述装置利用写时复制的方式对数据进行修改，所述装置包括：获取模块，用于获取需要更新的数据的节点，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点；更新模块，用于将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址；修改映射表模块，用于修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。

为解决上述技术问题，本申请采用的另一个技术方案是：提供一种基于B+树索引的数据更新装置，其中，所述装置利用写时复制的方式对数据进行修改，所述装置包括处理器，所述处理器用于获取需要更新的数据的节点，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点；处理器还用于将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址；处理器还用于修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。

为解决上述技术问题，本申请采用的另一个技术方案是：提供一种具有存储功能的装置，其中，所述装置存储有程序，所述程序被执行时实现上述的基于B+树索引的数据更新方法。

本申请的有益效果是：区别于现有技术的情况，本申请提供一种基于B+树索引的数据更新方法、装置及存储装置，通过在B+树索引中添加映射表，映射表将物理节点映射到虚拟节点，可以确保对页面多个引用的修改是原子性的同时，能够消除CoW B+树在更新修改时的级联操作，减少开销。

附图说明

图1是现有技术中写时复制的读写操作示意图；

图2是本申请基于B+树索引的数据更新方法第一实施方式的流程示意图；

图3是本申请基于B+树索引的数据更新方法第二实施方式的流程示意图；

图4是本申请基于B+树索引的数据更新装置第一实施方式的结构示意图；

图5是本申请基于B+树索引的数据更新装置第二实施方式的结构示意图；

图6是本申请具有存储功能的装置第一实施方式的结构示意图。

具体实施方式

为使本申请的目的、技术方案及效果更加清楚、明确，以下参照附图并举实施例对本申请进一步详细说明。

本申请提供一种基于B+树索引的数据更新方法、装置及存储装置，数据更改时使用CoW机制，达到读写不冲突的效果，构建B+树索引时引入映射表，映射表将物理节点映射到虚拟节点，可以确保对页面多个引用的修改是原子性的同时，能够消除CoW B+树在更新修改时的级联操作，减少开销。

请参阅图2，图2是本申请基于B+树索引的数据更新方法第一实施方式的流程示意图；在该实施方式中，该方法包括如下步骤：

S201：获取需要更新的数据的节点。

其中，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点。

具体地，B+树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树，在降低磁盘I/O操作数方面比较好，一棵B+树包含根节点、内部节点和叶子节点，根节点可能是一个叶子节点，也可能是一个包含两个或两个以上叶子节点的节点，B+树通常用于数据库和操作系统的文件系统中。

S202：将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址。

其中，该方法采用写时复制技术对数据进行修改更新，通过写时复制技术，能够达到读写不冲突的效果。具体地，写时复制的基础观念是，如果有多个呼叫者(callers)同时要求相同资源，他们会共同取得相同的指标指向相同的资源，直到某个呼叫者(caller)尝试修改资源时，系统才会真正复制一个副本(private copy)给该呼叫者，以避免被修改的资源被直接察觉到，这过程对其他的呼叫者都是通透的(transparently)。

也或者说，虚拟空间(虚拟节点)不同的进程会指向相同的物理空间(物理节点、内存区)，当进程中有更改相应段的行为发生时，才会为进程相应的段分配物理空间，然后在新的物理空间内对数据进行修改。

S203：修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。

其中，B+树的内部结点并没有指向关键字具体信息的指针，因此其内部结点较小，如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存中的需要查找的关键字也就越多，相对来说IO读写次数也就降低了，所以B+树的磁盘读写代价更低。同时，由于B+树的非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引，所以任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率相当，所以B+树的查询效率更加稳定。

但是，写时复制的B+树索引对更新操作不友好，因为CoW动作会从叶子节点向上蔓延至根节点，此外，在这过程中带来的随机IO代价比较大。为克服现有CoW B+树的不足，本申请在B+树索引中增添了一个映射表(Mapping Table)，映射表包括虚拟节点到物理节点的映射，这样，当一个数据页的物理地址发生改变以后，只需要在mapping table中将对应的条目进行更改即可，只需要修改映射表中虚拟节点与物理节点的映射关系即可。利用Mapping table可以将数据页更改的影响限制在特定的页面上，避免级联CoW现象的发生，加速更新操作，降低随机IO。

其中，在一实施方式中，该方法需要先建立树索引，树索引包括映射表和B+树；映射表包括虚拟节点到物理节点的映射；物理节点代表一个物理内存地址，虚拟节点构建形成B+树。因为映射表的存在，mapping table隔离了物理地址和B+树节点，使物理节点的更改并不会影响虚拟节点，这样子，CoW导致的物理页面的更改并不会对其他页面造成影响，都是原子性的，也不需要把叶子的修改传播到树的根部。但是，Mapping table中页面ID对应的物理地址Ptr会随着页面的更改而发生改变。

其中，在一实施方式中，该方法的B+树索引中，虚拟节点之间是通过逻辑链接关联起来。这是因为mapping table的引入消除了CoW动作沿着通往根节点路径蔓延，对整个索引造成影响的缺陷。因此，可以将叶子节点链接起来，进而更好地支持范围查找与合并、分裂操作。

其中，在一实施方式中，该方法可用于对索引页面数据的修改，也可以用于对树的数据结构的修改，例如分裂一个节点或者合并节点。这些修改操作均采用CoW技术。

其中，在一实施方式中，修改完成后，对旧的物理节点进行回收。具体地，等待事件(Latch-free，闩锁释放)环境不允许排它的访问一个共享数据结构，也就是说即使页面在被修改，也可以被访问。我们并不想释放一个仍然被访问的内存。比如在固化的时候，线程交换老的页面和新的页面状态，并回收新状态，但是不能再有线程访问老的页面的时候释放。回收机制就是为了保护之前有访问的又要释放的对象。

请参阅图3，图3是本申请基于B+树索引的数据更新方法第二实施方式的流程示意图；在一个应用场景中，该方法包括如下步骤：

建立树索引，其中，树索引包括映射表和B+树，映射表包括虚拟节点(ID)到物理节点(Ptr)的映射(图中实线指针)，物理节点(Ptr)代表一个物理内存地址，虚拟节点(ID)构建形成B+树。一棵B+树包含根节点、内部节点和叶子节点，每个节点是由指针(Pointer，P)数据对(图中虚线指针)、关键字(Key，K)以及关键字所代表的文件地址组合构成的，一个节点存储在一个磁盘块上。

在需要对页面数据修改或树的结构修改时，会先将原来的页面拷贝一份出来，然后在新的页面上进行修改，修改之后将新的地址放到mapping table的页面物理地址栏中，形成新的物理地址。

CoW事务需要对某个记录进行修改时，先查找定位到灰色方框的叶子(Leaf)节点。具体地，从根节点开始，读取根节点信息，在根结点所包含的关键字K1,……,Kn中查找给定的关键字，若找到等于给定值的关键字，则查找成功；否则，可以确定要查找的关键字在Ki与Kj之间，此时取指针Pi所指的结点继续查找(Pi为指向子树根节点的指针)，直至找到。

然后事务会将对应地叶子节点拷贝一份出来，进行相应的修改；修改完成以后，将物理地址Ptr指向修改完成的页面际的内存地址；这样，以后操作访问的都是修改完成以后的页面。而灰色页面在所有访问操作完成以后等待回收。在该实施方式中，通过一层间接层Mapping table装置，可以消除原生的Copy-on-Write B+树的级联CoW问题，减少写入放大与随机IO问题。

基于上述方法，本申请还提供一种基于B+树索引的数据更新装置，请参阅图4，图4是本申请基于B+树索引的数据更新装置第一实施方式的结构示意图，在该实施方式中，所述装置利用写时复制的方式对数据进行修改，装置40包括处理器401，处理器401用于获取需要更新的数据的节点，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点。处理器401还用于将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址。处理器401还用于修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。

其中，在一实施方式中，处理器401还用于建立树索引，树索引包括映射表和B+树；映射表包括虚拟节点到物理节点的映射；物理节点代表一个物理内存地址，虚拟节点构建形成所述B+树。

其中，在一实施方式中，处理器401还用于将虚拟节点之间通过逻辑链接进行关联。

其中，在一实施方式中，处理器401还用于对索引页面数据的更改、或对索引树结构的更改。

其中，在一实施方式中，处理器401还用于对树结构进行节点分裂、或节点合并。

其中，在一实施方式中，处理器401还用于对旧的物理节点进行回收。

以上，该基于B+树索引的数据更新装置可用于执行上述基于B+树索引的数据更新方法，对数据进行修改更新，且具有相应的有益效果，具体过程请参阅上述实施方式的描述，在此不再赘述。其中该装置可以是独立于后台服务器的独立装置，也可以是服务器中的某一模块，或某一处理单元。

请参阅图5，图5是本申请基于B+树索引的数据更新装置第二实施方式的结构示意图，在该实施方式中，该装置利用写时复制的方式对数据进行修改，装置50为处理器中的某一模块，具体包括获取模块501、更新模块502和修改映射表模块503。

其中，获取模块501用于获取需要更新的数据的节点，节点包括物理节点和虚拟节点，物理节点代表一个物理内存地址，虚拟节点代表一个B+树节点。

更新模块502用于将需要更新的数据复制到一个新的物理内存中，在新的物理内存中对数据进行修改，形成新的物理内存地址。

修改映射表模块503用于修改映射表，使虚拟节点指向新的物理内存地址，形成新的物理节点；其中，映射表包括虚拟节点到物理节点的映射。

其中，在一实施方式中，该装置还包括创建模块，用于建立树索引，树索引包括映射表和B+树；映射表包括虚拟节点到物理节点的映射；物理节点代表一个物理内存地址，虚拟节点构建形成所述B+树。

其中，在一实施方式中，更新模块502还用于对索引页面数据的更改、或对索引树结构的更改。该装置可用于执行上述基于B+树索引的数据更新方法，具体过程请参阅上述实施方式的描述，在此不再赘述。

本申请还提供一种具有存储功能的装置，请参阅图6，图6是本申请具有存储功能的装置第一实施方式的结构示意图。在该实施方式中，存储装置60存储有程序601，程序601被执行时实现上述基于B+树索引的数据更新方法。具体工作过程与上述方法实施例中一致，故在此不再赘述，详细请参阅以上对应方法步骤的说明。其中具有存储功能的装置可以是便携式存储介质如U盘、光盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟等各种可以存储程序代码的介质，也可以是终端、服务器等。

以上方案，本申请提供一种基于B+树索引的数据更新方法，通过在构建B+树索引时引入映射表，映射表将物理节点映射到虚拟节点，可以确保对页面多个引用的修改是原子性的同时，能够消除CoW B+树级联CoW操作，减少开销。

在本申请所提供的几个实施方式中，应该理解到，所揭露的系统，装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施方式仅仅是示意性的，例如，所述模块或单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施方式方案的目的。

另外，在本申请各个实施方式中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)或处理器(processor)执行本申请各个实施方式所述方法的全部或部分步骤。

以上所述仅为本申请的实施方式，并非因此限制本申请的专利范围，凡是利用本申请说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。

Claims (11)

1.一种基于B+树索引的数据更新方法，其中，所述方法利用写时复制的方式对所述数据进行修改，所述方法包括：

获取需要更新的数据的节点，所述节点包括物理节点和虚拟节点，所述物理节点代表一个物理内存地址，所述虚拟节点代表一个B+树节点，所述B+树包含根节点和叶子节点，所述虚拟节点之间通过逻辑链接将所述叶子节点进行关联；

将所述需要更新的数据复制到一个新的物理内存中，在所述新的物理内存中对所述数据进行修改，形成新的物理内存地址；

修改映射表，使所述虚拟节点指向所述新的物理内存地址，形成新的物理节点；其中，所述映射表包括虚拟节点到物理节点的映射；

其中，所述将所述需要更新的数据复制到一个新的物理内存中，在所述新的物理内存中对所述数据进行修改，形成新的物理内存地址包括：

将需要更新的索引页面数据或索引树结构拷贝一份出来，在新的页面或树结构上进行修改，将修改之后新的物理地址指向修改完成的页面或树结构的物理地址。

2.根据权利要求1所述的基于B+树索引的数据更新方法，其中，所述获取需要更新的数据的节点之前包括：

建立树索引，所述树索引包括映射表和B+树；所述映射表包括虚拟节点到物理节点的映射；所述物理节点代表一个物理内存地址，所述虚拟节点构建形成所述B+树。

3.根据权利要求1所述的基于B+树索引的数据更新方法，其中，所述对索引树结构的更改包括：

对所述树结构进行节点分裂、或节点合并。

4.根据权利要求1所述的基于B+树索引的数据更新方法，其中，所述修改映射表，使所述虚拟节点指向所述新的物理内存地址，形成新的物理节点之后包括：

对所述旧的物理节点进行回收。

5.一种基于B+树索引的数据更新装置，其中，所述装置利用写时复制的方式对所述数据进行修改，所述装置包括处理器，所述处理器用于获取需要更新的数据的节点，所述节点包括物理节点和虚拟节点，所述物理节点代表一个物理内存地址，所述虚拟节点代表一个B+树节点，所述B+树包含根节点和叶子节点，所述虚拟节点之间通过逻辑链接将所述叶子节点进行关联；

所述处理器还用于将所述需要更新的数据复制到一个新的物理内存中，在所述新的物理内存中对所述数据进行修改，形成新的物理内存地址；

所述处理器还用于修改映射表，使所述虚拟节点指向所述新的物理内存地址，形成新的物理节点；其中，所述映射表包括虚拟节点到物理节点的映射；

其中，所述处理器还用于将需要更新的索引页面数据或索引树结构拷贝一份出来，在新的页面或树结构上进行修改，将修改之后新的物理地址指向修改完成的页面或树结构的物理地址。

6.根据权利要求5所述的基于B+树索引的数据更新装置，其中，所述处理器还用于建立树索引，所述树索引包括映射表和B+树；所述映射表包括虚拟节点到物理节点的映射；所述物理节点代表一个物理内存地址，所述虚拟节点构建形成所述B+树。

7.根据权利要求5所述的基于B+树索引的数据更新装置，其中，所述处理器还用于对所述树结构进行节点分裂、或节点合并。

8.根据权利要求5所述的基于B+树索引的数据更新装置，其中，所述处理器还用于对所述旧的物理节点进行回收。

9.一种基于B+树索引的数据更新装置，其中，所述装置利用写时复制的方式对所述数据进行修改，所述装置包括：

获取模块，用于获取需要更新的数据的节点，所述节点包括物理节点和虚拟节点，所述物理节点代表一个物理内存地址，所述虚拟节点代表一个B+树节点，所述B+树包含根节点和叶子节点，所述虚拟节点之间通过逻辑链接将所述叶子节点进行关联；

更新模块，用于将所述需要更新的数据复制到一个新的物理内存中，在所述新的物理内存中对所述数据进行修改，形成新的物理内存地址；

修改映射表模块，用于修改映射表，使所述虚拟节点指向所述新的物理内存地址，形成新的物理节点；其中，所述映射表包括虚拟节点到物理节点的映射；

其中所述更新模块还用于将需要更新的索引页面数据或索引树结构拷贝一份出来，在新的页面或树结构上进行修改，将修改之后新的物理地址指向修改完成的页面或树结构的物理地址。

10.根据权利要求9所述的基于B+树索引的数据更新装置，其中，所述装置还包括：

创建模块，用于建立树索引，所述树索引包括映射表和B+树；所述映射表包括虚拟节点到物理节点的映射；所述物理节点代表一个物理内存地址，所述虚拟节点构建形成所述B+树。

11.一种具有存储功能的装置，其中，所述装置存储有程序，所述程序被执行时实现权利要求1至4任一项所述的基于B+树索引的数据更新方法。