B+树-分分钟钟被安排地明明白白

B+树特性

B+树是为磁盘或其他直接存取辅助设备而设计的一种M叉平衡查询树，其特性如下：

1. 每个节点M个关键字和M棵子树，每个关键字对应一个子树。
2. 除根节点外，其余所有节点的关键字数在M/2（小数位进1）和M之间；根节点的关键字数在[1,M]之间。
3. 所有的数据项，都是按照大小顺序存放在同一层的叶子节点中，各叶子节点间用指针连接。
4. 所有非叶子节点，起到索引作用，可以看成是索引。非叶子节点中的每个索引项只含有对应子树的最大关键字和指向子树的指针，不含有该关键字对应记录的存储地址。

以3叉B+树为例，如图：

1. root节点[3,5,8]，包含了3个关键字和3个子树，每个关键字对应一个子树。
2. 见图即可知root[3,5,8]节点个数为3，叶子节点[1,2,3],[4,5],[6,7,8]关键字个数分别为3，2，3。
3. 叶子节点中，三个节点[1,2,3],[4,5],[6,7,8]有指针关联，数据按照从小到大的顺序排列，1，2，3，4，5，6，7，8。
4. 如果该节点存储是以数字id标识的用户对象，在root节点中[3,5,8]数据存储的是id关键字。在叶子节点，存储的是包含数字id的用户对象。

B+树最大的好处在于，如下：

• 随机查找关键字

从root根节点开始查询，在非叶子节点找到对应的关键字时，因为非叶子节点起到索引作用，没有该关键字对应记录的存储地址，还需要到达该关键字的叶子节点才能获取对应的全部数据。

• 从小到大遍历数据

如果需要从最小关键进行从小到大的顺序查询，可以直接从最左侧的叶子节点开始，不经过根节点和其他非叶子节点，而沿着下一个叶子节点指针可便利所有的数据。

B+树节点分裂和节点领养

在执行添加或者删除操作时，有可能会破环B+树特性。通常，通过节点分裂和节点领养两种方式可以继续保证B+树特性。节点分裂会扩展节点的空间，一个饱满的节点分裂为两个节点；节点领养会节省节点空间，使被领养的节点更加饱满。具体操作可以参考b树节点分裂和节点领养。