# 前言
从算法的逻辑上来说，二叉树的查询 (log2_N) 和插入效率 (log2_N) 已经很高。但是在实际的应用当中，我们不能将索引全部加载到内存之中，只能逐一的加载每一个磁盘页。这里的磁盘页就对应索引树的结点，相比于内存的比较和读取来说，磁盘I/O存取消耗的时间要高很多，所以判断一个数据结构是否适合于索引问题的关键就是计算产生的磁盘I/O次数。
# B-树
B-树是对2-3树的一种补充，是一种多路平衡查找树。一个M阶的B树（M取决于磁盘页的大小）的特点：
- 根结点的子节点数量在 [2, M]；
- 每个中间结点包含了 k-1 个元素和 k 个子节点，其中 k∈ [M/2, M]；
- 每一个叶子节点包含了 k-1 个元素，其中 k∈ [M/2, M]；
- 所有的叶子节点都在同一层；
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
对于大量的数据来说，采用B-树的结构是非常合适的。因为B-树的一个结点可以存放更多的值，所以B-树会比二叉树更矮、更胖，到达叶子结点所需要的磁盘I/O次数也更少。
# 查找
下面3幅图描述了在一个3阶的B-树中，如何查找到5:
从比较的次数来看，B-树没有和二叉树有着太多的差异。但是因为B-树中的一个结点可以存放多个元素，所以磁盘I/O的次数可以少很多，同时内存中的比较耗时相对来说可以忽略，因此查找的性能会比二叉树好。
# 插入
B-树的插入模式和2-3树相似，都是将结点转换为临时结点，然后不断向上递归直到根结点。
以向图中的B-树插入4为例：首先自顶向下查找4的结点位置，发现4应该插入到 (3, 5) 结点中。3阶B-树的结点最多含有两个元素，所以向父结点插入4同时将剩下的 (3, 5) 结点拆分，创建一个临时4结点。然后再将4插入到根结点升级为两元素节点 (4, 9)。将剩下的 (2, 6) 结点拆分，节点6独立为根节点的第二个孩子。
# 删除
以删除11结点为例，首先自顶向下查找元素11所在的位置。删除11结点后，结点12只有一个右子结点，所以找出12，13，15三个数中的中位数13取代12，同时12结点左下移成为一个子节点（左旋操作）。
# B+树
B+树是B-树的一个变体，有着比B-树更好的查询性能。一个M阶的B+树（M同样取决于磁盘页的大小）和B-树之间的区别在于：
- 有 k 个子树的中间结点包含了 k 个元素，而在B-树中的元素该中间结点包含了 k-1 个元素；
- B+树中的中间结点仅用于索引，不保存数据，所有的数据都保存在了叶子结点中；
- 所有的中间结点元素都同时存在于子节点，在子节点中是最大（或最小）元素；
- 所有的叶子结点包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身按照元素的关键字大小升序链接构成一个有序链表；
根结点的最大元素等同于整个B+树的最大元素；由于父结点的元素都出现子节点，因此所有的叶子结点包含了全部元素的信息，每一个叶子结点还带有指向下一个结点的指针，形成了一个有序的链表。
在B-树中，无论中间节点还是叶子节点都带有卫星数据（索引元素所指向的数据记录），而Ｂ+树中间节点没有卫星数据，只有索引，这就意味着同样大小的磁盘页可以容纳更多节点元素，在相同的数据量下，B+树更加“矮胖”，IO操作更少。
VS
# 查找
以查找元素3为例，记录B+树中的磁盘I/O过程：
B+树的查询必须最终查找到叶子结点；在B-树中只要找到目标元素即可，所以最终可能查询到中间结点或者是叶子结点。对比来看，B+树的查找性能是稳定的，而B-树的查找性能不稳定（最好情况是查找根结点，最坏情况是查到叶子结点）。
在相同的数据量的情况下，由于一个结点可以存放更多的数据，B+树的深度会比B-树更低，所以查询所需要的磁盘I/O更少。同样的磁盘页大小，B+树可以存储更多的元素。
# 范围查找
由于B+树的叶子节点构成了一条有序链表，因此B+树的范围查找要比B-树简单的多，而B-树需要铜鼓中序遍历来完成范围的查找，效率会低很多。下面以查询范围为3～11的元素为例：
# 总结
为了减少磁盘的I/O次数，必须降低树的深度，将原本”瘦高”的树改造成为“矮胖”，使得相同的磁盘页可以容纳更多的结点元素，因此出现了B-树。B+树是B-树的变体，在mysql中采用的是B+树，其相比B-树的优势在于：
- 单一结点存储的元素更多，查询所需要的磁盘I/O更少；
- 所有查询都会查找到叶子节点，查询性能更稳定；
- 所有叶子节点形成了一个有序链表，便于范围查询；
除了B-树和B+树，平时还会听到有B树的概念，同样B树是B+树的一个变体，相比B+树的不同之处如下：
若有收获，就点个赞吧
0 人点赞
