一种wandering_B+tree问题解决方法_杨勇鹏.pdf

一种 wandering B+tree 问题解决方法杨勇鹏蒋德钧（中国科学院计算技术研究所北京100190）（中国科学院大学北京100049）（）A Method for Solving the wandering B+tree ProblemYangYongpengandJiangDejun（Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190）（University of Chinese Academy of Sciences,Beijing 100049）AbstractInordertonarrowthegapbetweentherandomwriteandsequentialwriteperformanceofHDDsandSSDs,filesystemsandblockstoragesystemsusuallyusethelog-structuredtechniquetoconvertrandomwritetosequentialwrite.Therefore,modificationsonlog-structuredstoragesystemdataandmetadataareperformedasout-of-placewrites.Inlog-structuredstoragesystems,B+treesareoftenusedtomanagemetadata.Thetreenodeadoptstheout-of-placeupdatemethod,whichwillcausethetreenodetobeupdatedrecursively,soitfacesthewanderingB+treeproblem.Currently,themainideasoftheexistingmethodsare:Thelogicalindexandphysicaladdressofthetreenodeareseparated,andaseparatedatastructureandphysicaldevicespaceareusedtostorethemappingofthelogicalindexandphysicaladdressofthetreenode,therebyavoidingrecursiveupdatingofthetreenode.However,theexistingschemesnotonlyintroduceadditionalspaceoverheadbutalsohavetheproblemofnon-sequentialwritingintheadditionalphysicaldevicespace.WeproposeanIBTB+tree,internalnodebasedtranslationB+tree,whichembedsthelogicalindexandphysicaladdressesintothetreenode.Basedonthedirtylinkedlistdesign,anon-recursiveupdatealgorithmforflushingtheIBTB+treeisproposed.TheIBTB+treenotonlysolvestheproblemofwanderingB+treebutalsodoesnotintroduceadditionaldatastructureandspaceoverhead.Inthispaper,theIBTB+treeandtheB+treedesignedbyNAT,proposedinF2FS,areimplementedrespectively.Onthisbasis,theMonty-DevblockstoragesystemisdesignedandimplementedtoevaluatethetwoB+trees.ExperimentsshowthatonHDDandSSD,theIBTB+treeisbetterthantheNATB+treeinbothwriteamplificationandflushingefficiency.Key words log-structured storage system；block storage system；wandering B+tree；IBT B+tree；writeamplification摘要为了应对磁盘和固态硬盘随机写和顺序写性能差异较大的问题，文件系统和块存储系统通常采用日志结构（log-structured）技术将随机写转换为顺序写.因此，对于日志结构存储系统数据和元数据的修改都以异地写的方式执行.在日志结构存储系统中，B+tree 常被用于管理元数据，这就会导致 wanderingB+tree 问题，即树结点异地更新会导致树结构递归更新.目前，现有工作主要通过分离树结点的逻辑索引和物理地址，并使用额外的数据结构和物理设备空间存放树结点逻辑索引和物理地址的映射，从而避免递归更新树结构.但现有方法既引入额外空间开销，又存在额外物理设备空间非顺序写的问题.提出 IBTB+tree，将树结点逻辑索引和物理地址均存放在树结构中.同时，基于 IBTB+tree 结构引入 dirty 链表设计，并提出了非递归更新的 IBTB+tree 下刷算法.IBTB+tree 既解决了 wanderingB+tree 问题，又不引入额外收稿日期：2022-06-16；修回日期：2023-01-12通信作者：蒋德钧（）计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202220555JournalofComputerResearchandDevelopment60（3）：539554，2023的数据结构和物理设备空间，消除了固定物理设备空间的非顺序写.分别实现 IBTB+tree 和基于 F2FS 中NAT 设计的 B+tree，在此基础上设计实现 Monty-Dev 块存储系统以评价 2 棵 B+tree.实验表明，在 HDD和 SSD 介质上，IBTB+tree 在写放大和下刷效率方面均优于 NATB+tree.关键词日志结构存储系统；块存储系统；wanderingB+tree；IBTB+tree；写放大中图法分类号TP391随着大数据时代的到来和发展，数据量呈现爆炸式增长.根据 IDC（InternationalDataCorporation）的预 测，全 球 数 据 领 域 将从 2018 年 的 33ZB 增 长 到2025 年的 175ZB1.为了满足数据存储的需求，数据存储系统的规模和存储介质的容量都在不断地增长.各大存储设备厂商纷纷推出大容量存储设备来满足大量数据存储的需求.例如，西部数据已经推出单盘容量达 18TB 的机械硬盘（harddiskdrive，HDD）2，和单盘容量达 20TB 的瓦记录磁盘（shingledwritedisk，SWD）3.存储厂商 NimbusData 推出单盘最大容量高达 100TB 的固态硬盘（solidstatedisk，SSD）4.对于 HDD，文献 5 提到，Unix 文件系统只能利用 5%10%的磁盘写带宽，其他时间都消耗在磁盘寻道上.SpriteLFS5（log-structuredfilesystem）采用日志结构（log-structured）技术，该系统假设：文件都缓存在内存中，容量逐渐增大的内存可以很有效地满足读请求的处理需求.基于该假设，SpriteLFS 着重优化写性能.SpriteLFS 的物理地址分配方式为写时分配，文件系统的元数据和数据的更新方式均为异地写（out-of-placewrite）.SpriteLFS 将所有的写请求转换为顺序写后，几乎可以消除所有的磁盘寻道开销.基于 SpriteLFS，NILFS6在 Linux 系统上实现了日志结构文件系统.对于 SSD，文献 78 的研究表明：频繁地随机写请求处理，会导致严重的内部碎片，影响 SSD 的持续性能表现.SFS9研究发现：SSD 的随机写带宽和顺序写带宽的差异超过 10 倍；随机写会增加单位写请求的闪存块平均擦除次数，从而减少 SSD 的使用寿命.为解决上述问题，SFS 以 NILFS 为基础针对闪存介质特性，实现新的文件系统，提升系统吞吐率，降低闪存块平均擦除次数，减少 SSD 元数据管理开销，从而提升 SSD 寿命.近年来，业界又先后推出了 JFFS10，F2FS11-14等日志结构文件系统.除了文件系统外，日志结构技术还被应用于块存储系统，例如 BW-RAID15存储系统的 ASD 子系统16-17，ASD 系统向上提供标准块设备接口，将上层写请求转换为本地磁盘 RAID 的顺序写，以提升 BW-RAID 系统的吞吐率.本文把这类系统统称为日志结构存储系统.虽然日志结构存储系统可以将所有的写请求转换为顺序写，但是因为日志结构存储系统要求数据和元数据的修改都采用异地更新的方式，它面临元数据异地更新带来的连锁更新问题.树状结构通常被用于保存元数据，例如 B+tree，RB-tree（red-blacktree），而一旦树状结构的某个结点执行了异地更新，就会触发递归更新树状结构，这一问题通常被称作wanderingtree 问题18.因为 B+tree 被广泛应用于存储系统中，所以本文主要关注 wanderingB+tree 问题.针对 wanderingtree 问题，现有日志结构存储系统均提出了各自的解决方法：例如，NILFS219使用B+tree 管理所有元数据，引入特殊的内部文件 DAT（dataaddresstranslationfile）管理所有 B+tree 树结点；DAT 文件的每个数据块为 B+tree 的树结点，在文件内的偏移作为 B+tree 树结点的逻辑索引（用于索引在内存中的树结点）.但是，DAT 文件的地址映射关系仍然使用 B+tree 维护，以此保存逻辑索引和物理地址的映射（元数据块和数据块在物理设备上的地址），因此当 DAT 文件更新时，DAT 文件的映射管理仍然面临 wanderingB+tree 的问题.F2FS 采用多级间接索引管理文件映射，同样面临元数据结构递归更新问题.为了缓解这一问题带来的性能影响，F2FS 使用物理设备上固定的 NAT（nodeaddresstable）11区域存放元数据块逻辑索引和物理地址的映射关系.1 个设备上共有 2 个交替使用的 NAT 区域，目的是为了确保每次下刷 NAT 块均为原子操作.此外，对于采用日志结构技术的块存储系统 ASD 而言，它采用 2 层 RB-tree 管理地址映射，通过 固 定 区 域 存 放 地 址 映 射 的 反 向 映 射 来 解决wanderingRB-tree 问题.综上，上述系统均使用额外的数据结构和物理设备空间管理树结点逻辑索引和物理地址的映射，以此解决元数据管理的 wanderingtree 问题.但引入额外的数据结构和物理设备空间，会增加系统设计的复杂度、降低写物理设备的连续度.采用日志结构设计的文件系统和块设备系统在业界均有广泛的应用，然而针对大容量块存储系统，540计算机研究与发展2023，60（3）若采用高扇出、树操作效率高的 B+tree 管理块设备逻 辑 地 址 和 物 理 地 址 的 映 射 关 系，则 需 要 解决wanderingB+tree 问题，现有的块设备解决方法及日志结构文件系统的解决方法均需要引入额外的数据结构和物理设备空间.为解决 wanderingB+tree 问题，本文提出 IBT（internalnodebasedtranslation）B+tree.本文的主要贡献有 3 个方面：1）提出 IBTB+tree 树结构.中间结点记录孩子结点的逻辑索引和物理地址，避免引入额外数据结构和物理设备空间.2）提出 IBTB+tree 下刷算法.引入每层 dirty 链表按层次管理所有 dirty 树结点，自底向上按层次下刷 IBTB+tree，避免递归更新树结构.3）设计实现 Monty-Dev 块存储系统，评价 IBTB+tree 在写放大和下刷效率方面的优化效果.1相关工作对于树状数据结构，父亲结点需要记录孩子结点的地址信息.对于需要持久化到物理设备的树结构，则需要通过在中间结点中记录的孩子结点信息，确定孩子结点的物理地址.本文将树结点在内存中的唯一标识称作树结点逻辑索引，将树结点在物理设备上的地址称作树结点物理地址.Linux 内核中的ext4，dm-btree 等模块的树状数据结构，通过中间结点记录孩子结点的物理地址访问孩子结点，因此树结点逻辑索引和物理地址相同.其中，dm-btree 使用 RB-tree 组织缓存在内存中的树结点，访问孩子结点时首先检查孩子结点是否在 RB-tree 中，如果在则直接访问树结点，否则需要从物理设备加载.日志结构存储系统要求树结点的更新方式为异地写，且为写时分配物理地址.如果树结点逻辑索引和物理地址相同，则在树结点下刷时需要递归更新祖先结点中记录的孩子结点物理地址，因此存在wanderingtree 问题.本节分别介绍 NILFS2，F2FS，ASD系统针对 wanderingtree 问题的解决方法.1.1NILFS2NILFS2 使用 B+tree 管理文件映射和 inode.对于 wanderingB+tree 问题，NILFS2 的解决方法是：普通文件映射及管理 inode 的 B+tree 树结点，由一个文件名为 DAT 的特殊文件管理；所有管理用户文件映射的 B+tree 树结点是 DAT 文件的一个数据块；DAT文件的地址映射也由 B+tree 管理，该 B+tree 的树结点逻辑索引与物理地址相同.图 1 介绍 NILFS2 的解决方法.图 1（a）为管理普通用户文件映射的 B+tree 示意图，树结点逻辑索引为 vblocknr，即树结点在 DAT 文件中的偏移；图 1（b）为管理 DAT 文件映射的 B+tree 示意图，树结点逻辑索引和物理地址为 blocknr.若要读取用户文件逻辑地址为 0 的块，则需要查找图 1（a）所示的 B+tree，访问结点 Rf确定下一个要访问的孩子结点 vblocknr=1；若 DAT 文件的第 1 号块不在内存，则通过图 1（b）中所示的 B+tree 查找映射，自上至下访问结点 Ad，确定 DAT 文件第 1 号块的物理地址为 4，即为结点 Af的物理地址；通过查找结点 Af，可确定用户文件第 0 号逻辑块的物理地址为 0.图 1（a）中树结点修改下刷只需要修改 DAT 文件，无需递归更新图 1（a）；而图 1（b）中树结点修改下刷时，仍然需要递归更新.综上，NILFS2 可以解决除管理 DAT 文件映射的B+tree 之外所有元数据面临的 wanderingB+tree 问题.因此，NILFS2 的方法可以部分解决 wanderingB+tree问题，但仍然存在递归更新 B+tree 树结点的问题.1.2F2FSF2FS 将底层设备划分为多个 segment，segment是 F2FS 管理的最小单元.除物理设备头部固定空间占用外，剩余每个 segment 用来存放数据或者元数据，F2FS 的元数据主要包括 2 类：inode 块和间接索引块.F2FS 通过 inode 块存放文件信息，使用多级间接索引管理文件的地址映射.多级间接索引有着索引管理简单的优点，但是不抗稀疏，不能支持 Extent.由于使用了多级间接索引，F2FS 也存在 wanderingtree 问题.F2FS 的解决方法是：引入 NAT 的设计，将文件系统元数据块的逻辑索引和物理地址分离；使用固 vblocknr=0vblocknr=1vblocknr=2RfAfBf0212220011key:文件逻辑块号value:孩子结点vblocknrkey:文件逻辑块号value:文件块物理地址(a)用户文件映射(b)DAT文件映射blocknr=7blocknr=6blocknr=8RdAdBd0 262514038key:vblocknrvalue:孩子结点blocknrkey:vblocknrvalue:vblocknr对应的物理地址Fig.1ThecaseofNILFS2userfileandDATfilemapping19图1NILFS2 的用户文件和 DAT 文件映射案例19杨勇鹏等：一种 wanderingB+tree 问题解决方法541定的 NAT 区域存放 NATID 和物理地址的映射关系，避免修改一个元数据块就需要递归更新上级元数据块中记录的下级元数据块物理地址；F2FS 在格式化时，按照设备大小计算出管理既定物理设备空间所需的 NAT 块个数上限，NAT 区域中块数量为上限的2 倍，2 个空间存放 NAT 块的不同版本，交替使用.NAT 块 管 理 示 意 图 如 图 2 所 示，图 中 有 4 个segment，每个 segment 包括 512 个块，每个块大小均为 4KB；每个块包括 455 个 NATentry，即 455 个 NATID 到物理地址的转换；由于使用固定物理空间存放NAT，因此可通过每个 NATentry 相对于 NAT 区域起始地址的差值计算得到 NATID；每 2 个连续的 segment存放 512 个有效 NAT块，NAT块更新时写不同的segment，由 versionbitmap 标识某一个 NAT 块的最新版本在哪个 segment 中.因此，通过 2 个 segment 和bitmap 的设计，可确保 NAT 块每次更新均为异地写.512segment 0,1512segment 2,301210241025 1026512 513 51415361537 1538nat nat nat455NAT块versionbitmapNAT entryFig.2NATblockandversionbitmap11图2NAT 块和 versionbitmap11随着设备的增大，文件系统的元数据量也在增大，因此 NAT 区域就需要管理更多的 NAT 块.但NAT 的随机修改会导致严重的写放大，为解决该问题，引入了 journal 的设计，将最近对 NAT 的修改记录在 CP 区域中，journal 无可用空间时再更新 NAT 并下刷.综上，F2FS 采用 NAT 和 journal 的设计解决了wanderingtree 问题.但 NAT 设计无法利用负载的空间局部性，随着 NAT 空间的增大，写放大问题会更严重，且物理设备的访问模式不是顺序写.1.3ASDASD 系统提供 Linux 标准块设备语义，以虚拟块设备（virtualdevice，VD）的形式提供存储服务.ASD系统在物理设备之上创建一个日志结构存储池，存储池之上有多个逻辑地址空间，每个逻辑地址空间对应一个虚拟块设备 VD，每个 VD 向上提供存储服务.对于块设备，最重要的元数据信息是逻辑地址和物理地址的映射关系.ASD 的元数据管理结构如图 3 所示.ASD 系统使用 Extent 管理一段逻辑地址连续且物理地址连续的映射关系.定长逻辑空间内的多个 Extent 组成一个 Subtree，多个 Subtree 组成一个 Group，多个 Group组成整个逻辑地址空间.Group 信息常驻内存，Subtree和 Extent 信息在内存中的缓存可在内存压力大的时候释放.由于 Group 信息与设备容量相关，因此随着设备容量的增大，内存占用也会增大；另外，由于采用 Extent 的方式管理，一个 Extent 作为一个单独的内存分配单元，大量分配 Extent 后回收、释放可能存在内部碎片问题，释放了多个 Extent 但是内存占用却没有减少，且内存占用上限越大内部碎片越严重.ExtentExtentPhy LBALBALengthExtentSubtreeGroupGroupGroupStart LBALengthSubtreesStart LBALengthFig.3ASDsystemmetadatastructure16-17图3ASD 系统元数据结构16-17上述 Extent，Subtree，Group 结构均采用 RB-tree进行组织，每个 Group 在内存中索引多个 Extent.对于 Group 信息的下刷，需要先调整树结构，使得一个Group 索引到的 Extent 信息可以记录到物理设备上一个定长的数据块中，Group 的下刷方式为异地写.因此，ASD 也存在 wanderingtree 的问题，ASD 的解决方法是：1）Group 信 息 写 到 物 理 设 备 上 之 后，将 多 个Group 的逻辑索引和物理地址的映射以异地写的方式更新到数据区域；2）将 Group 信息的物理地址及其归属信息写入物理设备头部固定的反向表区域；3）系统重启时通过扫描固定区域重构 RB-tree.综上，ASD 采用 2 级逻辑索引和物理地址的映射解决 wanderingRB-tree 问题.该方法的优点是固定位置写较少，但管理复杂度过高.2wandering B+tree 问题分析和结构设计本节首先分析 wanderingB+tree 问题，提出该问题的解决方法：IBTB+tree.分别通过 B+tree 树结点布局、链表设计和树操作设计，以及第 3 节提出的 IBT542计算机研究与发展2023，60（3）B+tree 下刷算法论述 wanderingB+tree 的解决方法.2.1wandering B+tree 问题分析首先，通过图 4 介绍 wanderingB+tree 问题，并明确解决问题的难点.图 4 展示了 1 棵树结点逻辑索引与物理地址相同的 3 阶 B+tree 树结点更新过程.图 4 左图下刷结点 A 时，需要为结点 A 分配新的物理地址生成结点 A1；图 4 中间的图，生成结点 A1后，分配结点 D1使其指向结点 A1；图 4 右图分配结点 R1同理.因此，非树根结点分配物理地址需要递归更新父亲结点至树根结点，严重影响 B+tree 下刷效率.RDEBACRDEBACRDEBACR1D1D1A1A1A1生成结点A1生成结点D1新生成的结点未修改的结点生成结点R1Fig.4ExampleofwanderingB+treeproblem图4wanderingB+tree 问题案例综上，要解决 wanderingB+tree，需要满足日志结构系统设计需求：树结点写时分配物理地址，且更新方式为异地写；同时，避免 B+tree 树结点下刷时递归更新非叶子结点.如第 1 节所述，针对 wanderingtree 问题，NILFS2,F2FS,ASD 解决方法的共同点是：树结点逻辑索引和物理地址不同，即树结点的逻辑索引和物理地址分离，额外的数据结构和物理设备空间维护树结点逻辑索引和物理地址的映射关系.因此，解决 wanderingB+tree 问题的难点是：1）支持树结点逻辑索引和物理地址分离，且不引入新的数据结构和物理设备空间，降低复杂度；2）避免 B+tree 下刷时递归更新树结构.针对这 2 个难点，2.2 节提出第 1 个难点的解决方法，2.3 节和 2.4 节支撑第 3 节提出的 IBTB+tree 下刷算法解决第 2 个难点.2.2IBT B+tree 树结点布局IBTB+tree 的中间结点和叶子结点结构图如图 5所示，图 5 中各字段的含义如表 1 所示.接下来，分别介绍表 1 中各字段的用途.中间结点叶子结点HeaderHeaderblkid0blkid0blkid1blkid2pbidstatestateindexindexpbidpbidpbidpbidblkid1Fig.5TheinternalnodeandleafnodeofIBTB+tree图5IBTB+tree 中间结点和叶子结点Table 1The Meaning of the Fields in Fig.5表 1 图 5 各字段的含义字段含义blkid块设备的逻辑地址state孩子结点状态，dirty/cleanindex树结点逻辑索引pbid物理地址Header树结点的汇总信息1）state 字段为孩子结点的状态，dirty 代表孩子结点需要持久化到物理设备，clean 代表孩子结点已经持久化且可以在内存紧张时回收.因此，state 仅描述内存中的树结点内容是否与设备上的一致.2）如图 5 所示，中间结点记录孩子结点的逻辑索引 index，随着树高的增长，所有非树根结点的index 和 pbid 都会存放在其父亲结点中，只有树根结点的 index 和 pbid 不存放在树结构中.因此，需要额外的数据结构和物理设备空间存放树根信息，记作Superblock，包括 index,pbid,height（见 2.4 节）.由于所有树结点的更新方式均为异地写，因此树根结点需要记录在物理设备的固定位置上，B+tree 初始化时才能找到树根.3）中间结点记录孩子结点的 index 和 pbid，在内存中的 B+tree 树结点，以 index 为关键字，使用红黑树进行组织.各类 B+tree 操作执行过程中，如果树结点不在红黑树中，则需要通过 pbid 从底层设备读取树结点.2.3IBT B+tree 链表设计2.2 节提出树结点逻辑索引和物理地址分离的方法，通过树结点逻辑索引管理内存中的树结点，通过物理地址加载不在内存中的树结点，从而支持写时分配物理地址.因此，需要在此基础上解决 2.1 节提出的第 2 个难点：设计非递归更新的 IBTB+tree 下刷算法.主要思路是：按照层次管理 B+treedirty 树结点，使得 IBTB+tree 能够按照层次进行下刷.本节主要论述按照层次管理 dirty 树结点的方法，IBTB+tree下刷算法在第 3 节论述.扩展并修改 B+tree 链表维护方法.传统 B+tree只维护叶子结点链表，用来管理所有叶子结点，按照关键字升序或降序排列.本文修改并扩展树结点链表：B+tree 的每一层均有一个 dirty 链表；引入全局clean 链表.2 类链表设计主要有 2 个特点：1）B+tree 各层 dirty 链表管理相应层中状态为dirty 的树结点，dirty 树结点按照 LRU 的方式管理，而杨勇鹏等：一种 wanderingB+tree 问题解决方法543非按照关键字排序；2）clean 链表管理所有状态为 clean 的树结点，clean 链表也采用 LRU 的方式管理，目的是为了在内存紧张时释放不经常访问的树结点.链表的使用，特别是 dirty 链表，将在 2.4 节介绍.第 3 节将介绍如何通过 dirty 链表更新树结点物理地址.2.4IBT B+tree 基本操作设计B+tree 在插入、查找、删除操作中对 key-value的管理，与采用 shadow-clone 设计的 B+tree20-21没有差异.为使用 lock-coupling 细粒度加锁协议支持 B+tree 并发操作22，B+tree 采用预先 rebalance、分裂的方式调整树结构，避免 B+tree 树操作执行过程中对孩子结点的修改导致父亲结点 rebalance、分裂.对于 wanderingB+tree 问题的解决方法，2.2 节已经给出支持树结点逻辑索引和物理地址分离的树结构设计.本节主要从支撑写时分配物理地址、更新物理地址的角度进行论述.支撑上述特性的主要解决方法是 dirty 和 clean 链表设计.本节从 B+tree 树操作的角度介绍 2 类链表的管理.由于 clean 链表用来管理clean 树结点、支撑内存回收，只需要维护树结点的LRU 逻辑即可.因此，本节主要介绍 dirty 链表的管理.dirty 链表的变化主要源自插入操作和删除操作.下面分别通过案例介绍这 2 个操作中 dirty 链表的管理.本节所有的案例均围绕图 4 所示的 3 阶 B+tree进行介绍，B+tree 树结点的 key-value 按照 key（逻辑地址）升序排序.2.4.1插入操作图 6 为将10,11映射插入 1 棵 3 阶 B+tree 的主要步骤.下面分步介绍插入操作：1）初始状态如图 6（a）所示，所有树结点状态均为 clean.2）图 6（b）将结点 R 标记为 dirty，并将结点 R 插入 list0；由于结点 R 的 key-value 数量达到上限，因此需要分裂结点 R，分配 D 和 E 这 2 个结点.将结点R 的 key-value 平均分配给结点 D 和 E.将结点 D 和 E中记录的最小 key 与结点 D 和 E 的逻辑索引分别作为 key 和 value 插入到结点 R 中.此时不需要为结点D 和 E 分配物理地址.树高加 1，相应地调整链表.3）图 6（c）和图 6（d），逐层向下访问到结点 A，将10,11插入到结点 A 中.如图 6（b）所示，新创建的链表为 B+tree 的第2 层.因为除树根结点外，B+tree 其他任何层都可能存在兄弟结点，为降低 B+tree 树操作复杂度，仅允许树根结点分裂出孩子结点.综上，新插入的 dirty 链表只发生在第 2 层，这一特性适用于任何高度大于 1的 B+tree.图 6 所示的每个阶段操作过程中，都将所有需要访问的树结点状态标识为 dirty，同时除树根结点外，将所有 dirty 树结点在其父亲结点中的状态标识为dirty.height2index1pbid10Superblockheight3index1pbid10SuperblockA1125Dc217c312218Rd51d621B341512C562621Ec49Rc217c4219c3128A1125B3412 15C5621 26height3index1pbid10SuperblockA1125Dd217c312218Rd51d621B341512C562621Ec491011list0list0list0list1list2list1list2height3index1pbid10SuperblockA1125Dd217c312218Rd51d621B341512C562621Ec49list0list1list2list1树结点为dirty树结点为clean未分配物理地址尚未建立与孩子结点的关系孩子结点为dirty指向孩子结点d孩子结点为cleanc新插入的key-value(a)初始状态(b)结点R分裂,树高增加(c)访问结点A(d)在结点A中插入key-value指向链表结点Fig.6Insertoperation（insert10,11）图6插入操作（插入10,11）544计算机研究与发展2023，60（3）由于 dirty 链表的引入，2 个并发的插入操作和，先执行，后执行；如果插入导致树高加 1，获得的树高信息不正确，则树结点可能插入错误的链表.因此，B+tree 无法支持插入和插入的并发.由于 clean 链表对树高不敏感，B+tree 仍可支持插入和查找操作并发执行.2.4.2删除操作以图 7（a）所示的 3 阶 B+tree 为例，介绍删除10,11映射：1）访问树根结点 R，将结点 R 标记为 dirty，并加入到 dirty 链表 list0 中.2）图 7（b），结点 R 只有 1 个孩子.因此，将结点 D中记录的 key-value 拷贝到结点 R 中，删除结点 D 和相应的链表.同时，结点 R 继承结点 D 的类型，图 7（b）中 D 为中间结点，也存在结点 R 只有 1 个孩子且为叶子结点的情况.因此，结点 R 也可能成唯一的叶子结点.3）图 7（c）和图 7（d），逐级向下访问到结点 A，将10,11从结点 A 中删除.如图 7（b）所示，被删除的 dirty 链表为 B+tree 的第 2 层.与插入操作同理，dirty 链表删除操作仅删除第 2 层链表，这一特性适用于任何高度大于 1 的 B+tree.删除操作可能引起树高的修改，因此删除操作与删除操作、删除与插入操作均不能并发执行.list0list1list2list0list1list0list0list1list1Dc217c3128A11251110B341512Rc5113Rc217c3128A11251110B341512height3index1pbid10Superblockheight2index1pbid10Superblockheight2index1pbid10Superblockheight2index1pbid10SuperblockRd217c3128A11251110B341512Rd217c3128A11251110B341512树结点为dirty孩子结点为dirtyd孩子结点为cleanc被删除的key-value(a)访问结点R(b)树高减1(c)访问结点A(d)删除key-value树结点为clean指向孩子结点指向链表结点Fig.7Removeoperation（remove10,11）图7删除操作（删除10,11）3IBT B+tree 下刷本节针对 2.1 节提到的第 2 个难点，提出非递归更新的 IBTB+tree 下刷算法，从而解决 wanderingB+tree 问题.通过第 2 节中 IBTB+tree 的相关介绍可知，IBTB+tree 除树根结点外有如下特性：所有状态为 dirty 的树结点的父亲结点状态均为 dirty；dirty 结点的状态对父亲结点不透明.利用上述 2 个特性，下面分别通过下刷算法和具体案例介绍 IBTB+tree 的下刷.B+tree 下刷存在 2 种情况：下刷所有树结点，包括 B+tree 创建完成并插入多次关键字之后的状态和B+tree 非首次下刷且所有树结点状态均为 dirty；部分下刷，包括部分 B+tree 树结点为 dirty 的情况和经过多次删除后 B+tree 为空.多次插入、删除操作后，dirty 树结点的内存占用或下刷时间间隔达到一定阈值，需要将 B+tree 所有状态为 dirty 的树结点下刷到物理设备.为避免递归更新 B+tree 树结构，IBTB+tree 下刷采用 2 阶段提交的方式.第 1 阶段，自 dirty 链表的倒数第 2 层向上下刷所有的 dirty 链表：1）根据该 dirty 链表上所有树结点，下刷该树结点所有状态为 dirty 的孩子；2）为孩子结点分配物理地址并下刷，将孩子结点的物理地址记录到父结点中，并更新父结点中记录的状态.第 2 阶段，将Superblock 写到固定的物理设备空间.B+tree 下刷算法如算法 1 所示：杨勇鹏等：一种 wanderingB+tree 问题解决方法545算法 1.IBTB+tree下刷算法.procedureflush_dirty_nodes（A）forchildAdoifis_dirty（child）thenwrite（child）；更新结点 A 中 child 的物理地址；endifendforendprocedureprocedureflush_dirty_lists（tree）idepth（tree）；whilei10doforAdirty_listi1doflush_dirty_nodes（A）；endfori；endwhileendprocedureprocedureflush_btree（tree）flush_dirty_lists（tree）；write（root）；/*第 1 阶段提交*/将树根的物理地址记录在 superbloc