B树和B+树

B-Tree定义

B-Tree的度n(Degree)=最大的子树个数， 节点元素最大个数n-1， 插入时节点元素个数大于n-1,那么节点分裂， 中间元素并入父节点。删除节点元素时，如果节点元素小于n-1/2时，那么和邻近节点合并。

B-Tree 删除演示

B+Tree 与BTree的不同：

1. 所有的叶子节点包含了全部的关键字信息，以及指向关键字对应的记录的指针
2. 所有的叶子节点相连
3. 所有的中间节点理解为叶子节点的索引，所以只包含节点的最大值或者最小值。

参考文档

B-Tree visualization
B+Tree visualization
B+Tree pdf

Posted in: 面试加油站