Btree/B+tree
Btree
Btree是一种多路自平衡搜索树，它类似普通的二叉树，但是Btree允许每个节点有更多的子节点。Btree示意图如下：
由上图可知 Btree 的一些特点:
- 所有键值分布在整个树中
- 任何关键字出现且只出现在一个节点中
- 搜索有可能在非叶子节点结束
- 在关键字全集内做一次查找，性能逼近二分查找算法
B+tree
B+树是B树的变体，也是一种多路平衡查找树，B+树的示意图为：
由图可看出B+tree的特点 同时也是 Btree 和 B+tree的区别
- 所有关键字存储在叶子节点，非叶子节点不存储真正的data
- 为所有叶子节点增加了一个链指针
Btree/B+tree区别
1、B+tree的所有关键字存储在叶子节点，非叶子节点不存储真正的data。
2、B+tree为所有叶子节点增加了一个链指针。
3、B+tree支持叶子节点的延展性（横向性）
4、B+tree可以向下开始分叉