「漫步计算机系统」之数据结构与算法(21):B树

B树又叫B-树，它是一种多路平衡搜索树，它的阶数m指它最多可以有多少个子结点，当m为2时，B树就成了二叉搜索树。

一棵m阶的B树定义如下：

1. 每个结点最多可以有m-1个关键字，可以是键值对；
2. 根结点最少可以只有1个关键字；
3. 非根结点最少有m/2个关键字；
4. 每个结点的关键字按照从小到大排序，它左子树结点的关键字都小于它，右子树结点的关键字都大于它；
5. 所有叶子结点位于同一层，也就是根结点到所有叶子的路径长度相同；
6. 每个结点都存有索引key和数据value。

因此，根结点关键字数量范围是1至m-1，非根结点关键字数量范围是m/2至m-1。每个结点存储了关键字(key)和关键字对应的数据(value)，以及字结点的指针。我们将一个关键字key和其对于的数据value称为一条记录。

在数据库中，我们将B树作为索引数据结构，可以快速查找key对应的value，value存储条目在磁盘上的逻辑地址。

B树的插入操作

插入指在B树中插入一条记录，即键值对（key-value）。如果B树中存在需要插入的键值对，则用新的value替换原value即可。若是新的键值对，则一定要在叶子结点插入。

1. 根据要插入的结点key的大小，在叶子结点中插入；
2. 判断当前结点的key的个数是否小于等于m-1，若是，则结束，否则进入第3步。
3. 以中间key为界将结点分割为两部分，中间key插入父结点，这个key的左指针指向左部分结点，右指针指向右部分结点。继续进行第三步。

下面以一个5阶B树为例，介绍插入操作。

a）在空树中插入39

b）继续插入22，97和41

c）继续插入53

这时结点的key个数超过了m-1，以key41分割结点，key41插入父结点，key41左指针指向前半部分，右指针指向后半部分。

d）依次插入13，21，40

e）依次插入30，27, 33 ；36，35，34 ；24，29

f）插入26

以key27分隔根结点

此时根节点也要分割

g）最后再依次插入17,28,29,31,32

B树的插入操作

删除操作是指，根据key删除B树结点中对应的键值对（key-value）。若B树中不存在key，删除失败。

1. 如果要删除的key位于非叶子结点，则将该key的后继（后继一定要在叶子结点）key替换该key，并将该后继key从叶子结点删除；
2. 如果该叶子结点key的个数大于m/2，结束，否则进入步骤3；
3. 如果兄弟结点key的个数大于m/2，则将父结点的key下移到该结点，兄弟结点的key上移到父结点；
4. 否则，将父结点key下移与兄弟节点、该结点key合并，形成一个新结点。原父结点指向两个孩子的两个指针变成了指向该新结点的一个指针。重复步骤2。

下面以一个5阶B树为例，介绍删除操作。

a）原始状态

b）删除21

c）删除27

先将key28替换key27

将兄弟结点的key26上移一个层次，再将key28下移一层至右子结点

d）删除32

父结点key30下移，和左右子结点合并为一个新结点

d）删除40

父结点key36下移，和左右子结点合并为一个新结点

最后将根结点和左右子结点合并为一个结点，完成。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。