B树和B+树
大家都知道，IO操作是影响程序运行速度的一个重要因素，即使SSD固态硬盘的发展极大的提高了读写速度，但和内存相比还是有一定的差距。特别是红黑树等，因为每个结点只能存储一个数据，且每个结点最多有两个子结点，这意味着当数据量大的时候，树的高度会非常大，也就意味着要频繁地进行IO操作。B树和B+树就是这种频繁IO操作场景的解决办法之一。
首先来看概念:
多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。B树是一种平衡多路查找树，结点的最大孩子数称为B树的阶。
我们先从B树的一个特例：2-3树作为切入点，来看看一个B树是如何构建和操作的。2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）。它拥有如下属性：
- 一个2结点包含一个元素和两个孩子（或没有孩子，如叶子节点），和二叉排序树一致，左子树包含的元素小于该元素，右子树包含的元素大于该元素。但是这个2结点要么有两个孩子，要么没有孩子，不能只有一个孩子。
- 一个3结点包含两个元素和三个孩子（或没有孩子），左子树、较小元素、中间子树、较大元素和右子树也按照从小到大排序。一个3结点要么有三个孩子，要么没有孩子。
- 2-3树的所有叶子结点都在同一层次上。
例：图1
图1
下面我们通过构造一棵2-3树来演示它的增删过程，假定数据为：{1, 7, 4, 9, 15, 13, 6, 5, 8, 10, 3, 12, 14, 2, 11}。现在树为空，首先插入1，只需要构建一个2节点。
图2
然后插入7，只需将当前节点升级为三节点。
图3
接下来插入4，可以发现根结点已经是3结点了，因为必须是平衡的，所以只能把根结点拆开，变为3个2结点。
图4
插入9时，因为9比4大，所以插入到右侧，而7所在结点可以升级为3结点。
图5
接下来要插入15，因为9所在结点已经是3结点，但是它的父结点4是2结点，所以可以把4所在结点升级，因为3结点必须有三个孩子，所以7和9所在结点需要拆分。
图6
接下来插入13和6时，对应节点都可以升级。
图7
接下来插入元素5时，发现6所在结点已经是3结点，而父结点，也就是根结点也是3结点了，这时可以再次拆分。
图8
接下来插入8，10，3也是重复步骤。
图9
再插入元素12、14、2。
图10
最后插入11。
图11
接下来我们再演示下删除的过程，首先删除元素1，因为1是2结点，删除后会影响平衡，但是我们发现它的父结点是一个3结点，所以可以把父结点拆开，2和3合并成一个3结点。
图12
然后删除7，因为7是叶节点也是3结点，直接删除就可以。
图13
删除结点4，因为它的左孩子是3结点，只要把它拆开就可以了。
图14
删除9时比较复杂，因为它的左右孩子都是2结点，首先把它的两个孩子合并为3结点并代替它，结果如下：
图15
此时树是不平衡的，此时发现左侧3和6可以合并为3结点。
图16
接下来删除15，直接删除即可。
图17
以此类推......后面就不一一演示了。
- 总结：这里介绍的2-3树是B树的一个特例，B树就是把2-3树的阶扩展到了m，它的每个结点特性和2-3树一致，除叶结点外每个结点的指针域和数据域都必须填充。那么B树是如何解决IO访问问题的呢？假设我们有一棵阶为1001的B树，也就是每个结点可以存储1000个数据和1001个指针，那么在高度为2的层上，可以存储的数据是1001X1000个，而它的指针数量为1001X1001个，这些指针可以指向的数据为1001X1001X1000个，大概有10亿条数据。这意味着，只要我们把根结点保存在内存中，访问这10亿条数据最多需要两次IO操作，这是其他结构无法比拟的。
但是B树有个缺点，如果遍历数据，效率会比较低，比如采用中序遍历，会频繁的进行IO操作，所以B树对遍历是不友好的。接下来看下B+树对此问题的优化。
B+树
遍历的需求主要来源于“扫库”，比如网站大量充斥着各种列表，如果使用B树遍历，效率实在太低了。B+树在B树的基础上做了改进，在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出，且每一个叶子结点都会保存一个指向后一叶子结点的指针。如下就是一棵B+树：
图18
为了简化，结点左右两侧指针域省略。它的特点就是任何非叶子结点都会在叶结点上再次出现一次，并且所有叶子结点从左到右链接了起来。总体来说，它也具备B树的特性，只是在两个方面有所区别。第一就是查找元素时，即使在非叶子结点找到了目标值，它也只是用来索引的，还需要继续找到它在叶子结点的位置。第二就是如果要遍历，只需要遍历一次叶子结点即可。B+树的结构也十分适合范围查找，只需要找到范围的最小值所在位置，然后沿链表遍历即可。
B树和B+树的对比
B树与B+树都是对磁盘友好的数据结构，能大幅降低磁盘访问次数。B树的优点在于数据存储在每个结点中，可以更快访问到，而不必须走到叶子结点，B树更多的用在文件系统中。B+树的每个非叶子结点都只充当索引，所以内部节点可以存储更多的键值，使得树的高度更矮，访问非叶子节点的磁盘I/O次数更少。但查询必须到叶子结点结束，相对B树会慢一些，但它十分适合“扫库”和区间查找。
