B+Tree简要理解

B+Tree是一种为磁盘等存取设备设计的平衡查找树，它实现了以O(log n)复杂度执行查找、顺序读、插入和删除操作。

与B-Tree主要区别：

1. 非叶子节点不存数据，通过更低的树高度减少存取设备的IO次数

2. 叶子节点有前后指针，通过双向链表实现高效的范围查找

实现B+Tree的核心思路：

1. 根据允许的节点最大空间（如mysql innodb默认16KB），算出每个节点的上下界(Lower/Upper Bound)

• 根节点：关键字数在1至m-1个之间，子节点数在2-m个之间
• 非根非叶节点：关键字数在(m/2)-1至m-1个之间，子节点数在ceil(m/2)至个之间
• 叶节点：关键字数同非根非叶节点，无子节点

  m为非叶子节点的子节点数的最大值
  如mysql innodb每页默认16KB，假设每行记录关键字4 byte，则一个非页子节点最多容纳 16*1024/4=4096 行记录关键字

2. 插入

   找到位置插入后，若节点关键字数超上界, 则

   1. 取节点中间关键字拆成两个节点，把中间关键字插入父节点，插入位置由原父分割关键字位置决定(如原上级左则插右，反之则右左)
   2. 以父节点为中心检查是否超出上界，超出则递归执行第一、二步。

3. 删除

   删除后，若当前节点关键字数低于下界，则

   1. 向大于下界的兄弟节点借关键字(原父分割关键字下沉，左或右兄弟节点关键字上升，直到借出目标节点完成关键字上升)
   2. 无大于下界的兄弟节点，合并一个相邻兄弟节点且原父分割关键字下沉，以父节点为中心递归检查是否低于下界
   3. 节点调整后，要始终保证页子节点的双向链表连续性。