B树、B+树、B*树

2018-12-04 本文已影响68人灯火阑珊唯念沵_e0b8

说起数据库，避免不了的要讲索引。要真正理解索引，首先就得清楚B+树的结构等

B树

B树即B-树，而不是两种树。

概念：一棵m阶B树是一棵平衡的m路搜索树。
特点：

m即所有节点中孩子节点个数的最大值
每个非根节点所包含的关键字个数j满足：ceil(m/2) - 1 <= j <= m - 1（ceil为向上取整，即大于该数的最小整数）
节点的子节点数会比关键字个数加1
根据以上两条可以得出，每个节点最多有m个分支，非根非叶节点至少有ceil(m/2)个分支

B树的查找

B树的查找还是很简单的，不再赘述。

其最低搜索性能：

B树的插入

例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15构建5阶B树

因为构建5阶的B树，所以每个节点的关键字个数范围为[2,4]

插入11时，该节点的关键字个数超出范围，进行分裂

之后直接插入4，8，13

当插入10时，节点关键字个数再次超出范围

将子节点分裂

直接插入5，17，9，16，插入20

关键字个数超出范围，进行分裂

继续插入3

关键字个数超出范围，进行分裂

继续插入15

关键个数超出范围，进行分裂

这时候根节点关键字个数也超出范围，继续分裂

B树的删除

对于B-树关键字的删除，需要找到待删除的关键字，在结点中删除关键字的过程也有可能破坏B-树的特性，如旧关键字的删除可能使得结点中关键字的个数少于规定个数，这是可能需要向其兄弟结点借关键字或者和其孩子结点进行关键字的交换，也可能需要进行结点的合并，其中，和当前结点的孩子进行关键字交换的操作可以保证删除操作总是发生在终端结点上。

从上面已经构建好的B树中依次删除8，16，15，4

删除8：关键字8在叶子节点上，并且删除后其所在结点中关键字的个数不会少于2，因此可以直接删除。

删除16：关键字16不在终端结点上，但是可以用17来覆盖16，然后将原来的17删除掉

删除15：15虽然也在终端结点上，但是不能直接删除，因为删除后当前结点中关键字的个数小于2。这时需要向其兄弟结点借关键字，显然应该向其右兄弟来借关键字，因为左兄弟的关键字个数已经是下限2.借关键字不能直接将18移到15所在的结点上，因为这样会使得15所在的结点上出现比17大的关键字，所以正确的借法应该是先用17覆盖15，在用18覆盖原来的17，最后删除原来的18

删除4：4在叶子节点上，但是此时4所在的节点的关键字个数已经到下限，需要借关键字，不过可以看到其左右兄弟节点已经没有多余的关键字可借。所以就需要进行关键字的合并。可以先将关键字4删除，然后将关键字5、6、7、9进行合并作为一个节点链接在关键字3右边的指针上，也可以将关键字1、2、3、5合并作为一个节点链接在关键字6左边的指针上

显然上述两种情况下都不满足B-树的规定，即出现了非根的双分支节点，需要继续进行合并

B+树

一棵m阶B+树是一棵平衡的m路搜索树

有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
ceil(m/2) <= j <= m
所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接（叶子节点之间增加了横向的指针）。
所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。【在这一点上有一些不同的说法，其中一种说法为，非叶子结点的子树指针与关键字个数相同，非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）】

按不同的说法，以上两种形式的B+树应该都对

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+树的查询

B+树的好处就体现在查询性能上：

在单元素查询的时候，B+树会自顶向下逐层查找节点，最终找到匹配的叶子节点。比如拿上面的B+树来进行查询：

现在要查找3：
第一次磁盘IO：

第二次磁盘IO：

第三次磁盘IO:

看到这里，可能会觉得查询流程和B-树差不多呀。
不，有两点不同。首先，B+树的中间节点没有数据，只存储索引，所以同样大小的磁盘页可以容纳更大的节点元素。这就意味着，数据量相同的情况下，B+树比B-树更加“矮胖”，因此查询时IO次数也更少。
其次，B+树的查询必须最终查询到叶子节点，而B-树只要找到匹配元素即可，无论匹配元素在叶子节点还是在中间节点。因此，B-树的查找性能并不稳定（最好的情况只查找根节点，最坏的情况查找到叶子节点）。而B+树的每一次查找都是稳定的。

B+树查询的优势更多的体现在范围查询上。比如现在要查询3-11的元素。
B-树的查找过程：
自顶向下查找到范围的下限3：

中序遍历到元素6：

中序遍历到元素8：

中序遍历到元素9：

中序遍历到11，遍历结束：

B-树的范围查询是不是很繁琐呢？
再来看看B+树的范围查询。
自顶向下查找到范围的下限3：

通过链表指针，遍历到元素6，8：

通过链表指针，遍历到元素9，11，遍历结束：

总结一下B+树的特征和优势

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

B+树的优势：
1、单一节点存储更多的元素，使得查询的IO次数更少。
在数据库检索来说，对于磁盘IO扫描时最消耗时间的，因为磁盘扫描涉及很多物理特性，这些是相当消耗时间的。所以B+树设计的初衷就是最大限度的减少对于磁盘的扫描次数。如果一个表或索引没有使用B+树（对于没有聚集索引的表是用堆heap存储），那么查找一个数据，需要在整个表包含的数据库页中全盘扫描。这无疑会大大加重IO负担，而使用B+树进行存储，则仅仅需要将B+树的根节点存入内存中，经过几次查找后就可以找到存放需要数据的被叶子结点包含的页，进而避免了全盘扫描从而提高了性能。
2、所有查询都要查询到叶子节点，查询性能更稳定。
3、所有叶子节点形成有序链表，便于范围查询。

B+树的插入

1）若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
2）针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2+1个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
3）针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

往下图的3阶B+树中插入9