数据结构 —— B树和B+树
B树详解以及B+树与B树的不同
数据结构 —— B树和B+树
1. 背景
最近在学习数据库相关的知识，了解到数据库很多是采用B-/+树作为索引，例如Mysql的InnoDB引擎使用的B+树、MongoDB默认采用B树作为索引。
在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。–wiki
2. B树的定义
一个 m 阶的B树是一个有以下属性的树：
- 每一个节点最多有 m 个子节点
- 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
- 如果根节点不是叶子节点，那么它至少有两个子节点
- 有 k 个子节点的非叶子节点拥有 k − 1 个键
- 所有的叶子节点都在同一层
阶
B 树中一个节点的子节点数目的最大值，用 m 表示，假如最大值为 10，则为 10 阶，如图
所有节点中，节点【13,16,19】拥有的子节点数目最多，四个子节点（灰色节点），所以可以定义上面的图片为 4 阶 B 树
根节点
节点【10】即为根节点，特征：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有俩个子节点（不然就变成单支了）。在 m 阶 B 树中（根节点非树中唯一节点），那么有关系式 2<= M <=m，M 为子节点数量；包含的元素数量 1<= K <=m-1,K 为元素数量
叶子结点
节点【1,2】、节点【11,12】等最后一层都为叶子节点，叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。特征：在 m 阶 B 树中叶子节点的元素符合（m/2）-1<= K <=m-1
3. B数的相关操作
3.1 查找
B树的搜索和二叉搜索树类似。从根节点开始，从上到下递归的遍历树。在每一层上，搜索的范围被减小到包含了搜索值的子树中。子树值的范围被它的父节点的键确定。
3.2 插入
所有的插入都从根节点开始。要插入一个新的元素，首先搜索这棵树找到新元素应该被添加到的对应节点。将新元素插入到这一节点中的步骤如下：
- 如果节点拥有的元素数量小于最大值，那么有空间容纳新的元素。将新元素插入到这一节点，且保持节点中元素有序。
- 否则的话这一节点已经满了，将它平均地分裂成两个节点：
- 从该节点的原有元素和新的元素中选择出中位数
- 小于这一中位数的元素放入左边节点，大于这一中位数的元素放入右边节点，中位数作为分隔值。
- 分隔值被插入到父节点中，这可能会造成父节点分裂，分裂父节点时可能又会使它的父节点分裂，以此类推。如果没有父节点（这一节点是根节点），就创建一个新的根节点（增加了树的高度）。
如果分裂一直上升到根节点，那么一个新的根节点会被创建，它有一个分隔值和两个子节点。这就是根节点并不像内部节点一样有最少子节点数量限制的原因。
以5阶B树举例说明
其中5阶B数有一下特征
- 2<= 根节点子节点个数 <=5
- 3<= 内节点子节点个数 <=5
- 1<= 根节点元素个数 <=4
- 2<= 非根节点元素个数 <=4
初始化数据
插入元素【8】
图（1）插入元素【8】后变为图（2），此时根节点元素个数为 5，不符合 1<= 根节点元素个数 <=4，进行分裂（真实情况是先分裂，然后插入元素，这里是为了直观而先插入元素，下面的操作都一样，不再赘述），取节点中间元素【7】，加入到父节点，左右分裂为 2 个节点，如图（3）
接着插入元素【5】，【11】，【17】时，不需要任何分裂操作，如图（4）
插入元素【13】
节点元素超出最大数量，进行分裂，提取中间元素【13】，插入到父节点当中，如图（6）
接着插入元素【6】，【12】，【20】，【23】时，不需要任何分裂操作，如图（7）
插入【26】时，最右的叶子结点空间满了，需要进行分裂操作，中间元素【20】上移到父节点中，注意通过上移中间元素，树最终还是保持平衡，分裂结果的结点存在 2 个关键字元素。
插入【4】时，导致最左边的叶子结点被分裂，【4】恰好也是中间元素，上移到父节点中，然后元素【16】,【18】,【24】,【25】陆续插入不需要任何分裂操作
最后，当插入【19】时，含有【14】,【16】,【17】,【18】的结点需要分裂，把中间元素【17】上移到父节点中，但是情况来了，父节点中空间已经满了，所以也要进行分裂，将父节点中的中间元素【13】上移到新形成的根结点中，这样具体插入操作的完成。
3.3 删除
首先查找 B 树中需删除的元素, 如果该元素在 B 树中存在，则将该元素在其结点中进行删除；删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素 (“左孩子最右边的节点” 或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接删除。
- 某结点中元素数目小于（m/2）-1,(m/2) 向上取整，则需要看其某相邻兄弟结点是否丰满；
- 如果丰满（结点中元素个数大于 (m/2)-1），则向父节点借一个元素来满足条件；
- 如果其相邻兄弟都不丰满，即其结点数目等于 (m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并” 成一个结点；
以 5 阶 B 树为例，详细讲解删除的动作
关键要领，元素个数小于 2（m/2 -1）就合并，大于 4（m-1）就分裂
如图依次删除依次删除【8】,【20】,【18】,【5】
首先删除元素【8】，当然首先查找【8】，【8】在一个叶子结点中，删除后该叶子结点元素个数为 2，符合 B 树规则，操作很简单，咱们只需要移动【11】至原来【8】的位置，移动【12】至【11】的位置（也就是结点中删除元素后面的元素向前移动）
下一步，删除【20】, 因为【20】没有在叶子结点中，而是在中间结点中找到，咱们发现他的继承者【23】(字母升序的下个元素)，将【23】上移到【20】的位置，然后将孩子结点中的【23】进行删除，这里恰好删除后，该孩子结点中元素个数大于 2，无需进行合并操作。
下一步删除【18】，【18】在叶子结点中, 但是该结点中元素数目为 2，删除导致只有 1 个元素，已经小于最小元素数目 2, 而由前面我们已经知道：如果其某个相邻兄弟结点中比较丰满（元素个数大于 ceil(5/2)-1=2），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中，在这个实例中，右相邻兄弟结点中比较丰满（3 个元素大于 2），所以先向父节点借一个元素【23】下移到该叶子结点中，代替原来【19】的位置，【19】前移；然【24】在相邻右兄弟结点中上移到父结点中，最后在相邻右兄弟结点中删除【24】，后面元素前移。
最后一步删除【5】， 删除后会导致很多问题，因为【5】所在的结点数目刚好达标，刚好满足最小元素个数（ceil(5/2)-1=2）, 而相邻的兄弟结点也是同样的情况，删除一个元素都不能满足条件，所以需要该节点与某相邻兄弟结点进行合并操作；首先移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中，然后将这两个结点进行合并成一个结点。所以在该实例中，咱们首先将父节点中的元素【4】下移到已经删除【5】而只有【6】的结点中，然后将含有【4】和【6】的结点和含有【1】,【3】的相邻兄弟结点进行合并成一个结点。
也许你认为这样删除操作已经结束了，其实不然，在看看上图，对于这种特殊情况，你立即会发现父节点只包含一个元素【7】，没达标（因为非根节点包括叶子结点的元素 K 必须满足于 2=<K<=4，而此处的 K=1），这是不能够接受的。如果这个问题结点的相邻兄弟比较丰满，则可以向父结点借一个元素。而此时兄弟节点元素刚好为 2，刚刚满足，只能进行合并，而根结点中的唯一元素【13】下移到子结点，这样，树的高度减少一层。
4. B+树
4.1 B+树的特征
- 有 m 个子树的中间节点包含有 m 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引；
- 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而 B 树的叶子节点并没有包括全部需要查找的信息)；
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而 B 树的非终节点也包含需要查找的有效信息)；