BTree vs B+Tree

• 无论 BTree 还是 B+Tree，每个叶子节点到根节点距离都相同
• BTree key 及 value 在每个节点上，无论叶子还是非叶子节点
  
• B+Tree 普通节点只存 key，叶子节点才存储 key 和 value，因此分叉数可以更多
  • 不过也请注意，普通节点上的 key 有的会与叶子节点的 key 重复
• B+Tree 必须到达叶子节点才能找到 value
• B+Tree 叶子节点用链表连接，可以方便范围查询及全表遍历
  

注：这两张图都是仅画了 key，未画 value

B+Tree 操作节点

B+Tree 新增 key

假设阶数（m）为5

1. 若为空树，那么直接创建一个节点，插入 key 即可，此时这个叶子结点也是根结点。例如，插入 5

   

2. 插入时，若当前结点 key 的个数小于阶数，则插入结束

3. 依次插入 8、10、15，按 key 大小升序

   

4. 插入 16，这时到达了阶数限制，所以要进行分裂

   

5. 叶子节点分裂规则：将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前 m/2 个（2个）记录，右结点包含剩下的记录，将中间的 key 进位到父结点中。注意：中间的 key 仍会保留在叶子节点一份

   

6. 插入 17

   

7. 插入 18，这时当前结点的 key 个数到达 5，进行分裂

   

8. 分裂成两个结点，左结点 2 个记录，右结点 3 个记录，key 16 进位到父结点中

   

9. 插入 19、20、21、22、6、9

   

10. 插入 7，当前结点的 key 个数到达 5，需要分裂

    

11. 分裂后 key 7 进入到父结点中，这时父节点 key 个数也到达 5

    

12. 非叶子节点分裂规则：左子结点包含前 (m-1)/2 个 key，将中间的 key 进位到父结点中（不保留），右子节点包含剩余的 key

    

B+Tree 查询 key

以查询 15 为例

• 第一次 I/O

  

• 第二次 I/O

  

• 第三次 I/O

  

B+Tree 删除叶子节点 key

1. 初始状态

   

2. 删完有富余。即删除后结点的key的个数 > m/2 – 1，删除操作结束，例如删除 22

   

3. 删完没富余，但兄弟节点有富余。即兄弟结点 key 有富余（ > m/2 – 1 ），向兄弟结点借一个记录，同时替换父节点，例如删除 15

   

4. 兄弟节点也不富余，合并兄弟叶子节点。即兄弟节点合并成一个新的叶子结点，并删除父结点中的key，将当前结点指向父结点，例如删除 7

   

5. 也需要删除非叶子节点中的 7，并替换父节点保证区间仍有效

   

6. 左右兄弟都不够借，合并

B+Tree 删除非叶子节点 key

接着上面的操作

1. 非叶子节点 key 的个数 > m/2 – 1，则删除操作结束，否则执行 2

2. 若兄弟结点有富余，父结点 key 下移，兄弟结点 key 上移，删除结束，否则执行 3

3. 若兄弟节点没富余，当前结点和兄弟结点及父结点合并成一个新的结点。重复 1