B树和B+树比较（特征和算法）

B树和B+树的特征

b树的核心

• 树高:一般来说，树的高度要比二叉平衡树低很多
• 数组:每一个node，都是一个“数组”，数组是很关键的决定性因素，我们后面写入和读取分析的时候会讲到。

B+tree 其实就是在原有b-tree的基础上。增加两条新的规则

• Branch节点不能直接查到数据后返回，所有数据必须读穿或写穿到leaf节点后才能返回成功
• 子叶节点的最后一个元素是到下一个leaf节点的指针。

这样做的原因是，更方便做范围查询，在b+树种，如果要查询20~56.只需要找到20这个起始节点，然后顺序遍历，不再需要不断重复的访问branch和root节点了。

B树和B+树的算法实现

B树

        每个节点占用一个磁盘块的空间，一个节点上有两个生序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。

        两个关键字划分分成的三个范围域对应三个指针指向的子树的数据的范围域。

        以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

        模拟查找关键字29的过程

1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2.
5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6. 在磁盘块8中的关键字列表中找到关键字29

        分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+树

        B+树在B树中做了一个优化，因为每个磁盘块的大小都是有限的，如果在每个非叶子节点处都存放数据，那么每次获取到的磁盘块上的索引指针信息以及关键字信息将会很少，这样会增加我们的IO次数以及树结构的深度。

        B+树只在每个非叶子节点处只存放指针以及关键字信息，这样最大化的增加每个磁盘块存放的索引信息，可以更加有效的获取出相对应的地址信息，从而也降低了树结构的深度，而且叶子顶部节点允许互链减少了重新IO的次数。

        我们常用的MYSQL引擎InnoDB就是按这种方式存放数据，存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

        InnoDB存储引擎中有页（page）的概念，页是其磁盘管理的最小单位。InnoDB存储中默认每个页的大小为16KB。在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

总结

B+树的特征

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优势：

1. 单一节点存储更多的元素，使得查询的IO次数更少。
2. 所有查询都要查找到叶子节点，查询性能稳定。
3. 所有叶子节点形成有序链表，便于范围查询。