B+树插入删除示例

B+树是什么？

• B+树是一种树；
• B+树（或者其子树）代表一个有序的键值对集合，通过键决定键值对顺序；
• B+树的节点有两类，一类是内部节点（interval node），不存储值，只存储键，一类是叶子节点（leaf node），既存储键，也存储值（一般存储值的指针）；
• 内部节点可以有多个儿子指针，假设最多有 个，而与之对应的，内部节点最有也有 个键；
• 内部节点的键以升序（或者降序）排列，指针也依次插入在 个键之间，因此每一个键可以对应到两个指针上（一左一右），相邻两个键共享一个指针；
• 假设内部节点有两个相邻的键 ，那么其共享的指针指向的子树代表的有序集合的键在 和 之间，确切的说在区间 内；
• 叶子节点也包括多个儿子指针（个）和多个键（个），每一个键对应一个指针，该指针存储键值对中值对应的地址，剩下的最后的指针指向下一个叶子节点，下一个叶子节点指的是其该叶子节点最后的键值对的下一个键值对所在的叶子节点；
• 因此顺着某一个叶子节点的最后的指针往后走，可以遍历所有比该叶子节点第一个键大的所有键对应的键值对；

B+树的一些限制条件

• B+树的内部节点中，至少需要有 个键（除了根节点以外）；
• B+树的叶子节点中，至少需要有 个键；

B+树的查找

• 从根节点开始顺着内部节点往下找，找到对应的叶子节点，在叶子节点上根据键找到对应的值；
• 相邻两个键（ 和 ）中间指针指向的子树代表的集合，都在区间 内，根据该性质，找到 满足 ，根据两个键中间的指针，继续往下进行类似的查找操作；
• 找到对应的叶子节点后，通过遍历叶子节点包含的键值对可以找到待查找的键对应的值；如果找不到即该树中不包含该键对应的键值对；

B+树的插入

B+树插入示例

• 因为B+树中只有叶子节点存储键值对，那么一定会在叶子节点上插入新的键值对；
• 通过类似查找的方式找新的键值对所对应的叶子节点；
• 将该键值对插入到该叶子节点上后（满足键升序或者降序的性质），如果该节点能够存储该键值对，那么就没有后续的处理了；
• 否则，需要把该节点分裂成两个叶子节点，假设插入前叶子节点有 个键值对，那么当前有 个键值对，分裂时把前 个键值对放入第一个叶子节点，把后 个键值对放入第二个叶子节点（此时满足限制条件），第一个叶子节点的最后一个指针指向第二个叶子节点，第二个叶子节点的最后一个指针指向前叶子节点最后指针指向的位置；
• 此时新增了一个叶子节点，需要在前叶子节点对应的父亲节点上，新增一个键，该键的值是分裂后第二个叶子节点的第一个键的值，该键对应的两个指针（一左一右）分别指向分裂后的第一个和第二个叶子节点；
• 如果父亲节点存不下新增的键，父亲节点也需要分裂；
• 父亲节点作为内部节点，分裂方式和叶子节点有些区别，假设当前该节点有 个键和 个指针，新建两个内部节点，将前 个键和前 个指针放入第一个内部节点，将后 个键和后 个指针放入第二个内部节点；
• 剩下的一个键按照上述类似的方式插入原内部节点的父亲节点，递归内部节点插入的过程；
• 如果父节点不存在（也就是原叶子节点是根节点），那么新建一个节点充当新的父亲节点（也作为根节点）；

B+树的删除

B+树的删除示例

• 对于一个待删除的键 ，首先顺着根节点找到其所在的叶子节点（查找），如果找不到则代表该键在树中不存在；

• 如果找到了对应的键值对，删除该键值对，如果此时节点的限制条件满足（B+树的叶子节点中，至少需要有 个键），此时已经完成了所有的删除工作；

  • 根据观察可以发现，一般来说，叶子节点的父亲节点中的某一个键值和其右边的指针指向的叶子节点的第一个键值对的键是相等的；
  • 但是，如果删除的是叶子节点的第一个键值对，与之对应的父亲节点的键不修改不会影响到B+树的性质（有序）；

• 如果叶子节点删除一个键值对后，打破了B+树叶子节点的限制条件，有如下几种情况：

  • 如果该叶子节点是B+树中唯一的叶子节点，不需要任何的修改；

  • 如果该叶子节点存在兄弟节点，且其兄弟节点的键值对足够多，那么可以从其兄弟节点的键值对中拿一个过来，具体来说，

    • 如果该叶子节点的左兄弟节点的键值对数量大于 ，那么把其左兄弟节点的最后一个键值对拿过来插入到该叶子节点的第一个键值对的位置上，并修改该叶子节点的父亲节点对应的键的大小（如果不修改，会破坏B+树有序的性质）；
    • 如果该叶子节点的右兄弟节点的键值对数量大于 ，那么把其右兄弟节点的第一个键值对插入到该叶子节点的最后一个位置上，并修改其右兄弟叶子节点的父亲节点对应的键的大小（同理）；

  • 如果不存在兄弟节点的键值对的数量符合大小要求，那么可以将该叶子节点和其兄弟节点合并；合并两个叶子节点，首线将两个叶子节点上的键值对放到一个叶子节点上，被删除的叶子节点在其父亲节点上对应有一个键（该键的大小为被删除的叶子节点的第一个键值对的键），该键和其右边的指针（指向被删除的叶子节点）也应该被删除；

    • 如果该键和其右边的指针被删除后，其所在的内部节点满足B+树对内部节点的要求，那么删除的工作就到此为止了；
    • 否则，类似叶子节点，根据不同的情况有类似的解决方案；
      • 如果该内部节点是根节点，那么也没有后序的处理了；
      • 如果其兄弟节点的键数量足够多，那么可以将其兄弟节点的键拿过来；具体来说（和叶子节点不同），假设当前内部节点为 ，目标是从其右兄弟 拿一个键过来，而且，两个节点的父亲节点中存在一个键 ，其左右指针分别指向 和 ，首先将键 插入到 上，然后把 的第一个键拿出来放入到 之前所在的位置，此时键的放置已经处理好了，但是还有一个指针没有放置（的第一个键的左指针），将它放置到现在的对应的右指针的位置上即可；从左兄弟节点拿键放置到该节点的方法同理；
      • 否则，需要合并两个兄弟内部节点；具体来说（和叶子节点不同），同理假设合并的内部节点分别为 和 ，他们的父亲节点上对应的键 ，合并时需要在父亲节点上删除键 ，在合并的叶子节点的对应位置上插入 即可；由于两个被合并的兄弟节点的父亲节点被删除了一个键，也需要对该父亲节点进行类似的对内部节点的判断及操作；