B树

这B树是一个多叉平衡搜索树，这种树在大数据量的情况下他要比二叉搜索树、红黑树要好的。因为二叉搜索树和红黑树都是先把数据给加载到内存中，然后再对其进行处理的。

内存呢现在一般就是GB级别的，比如16G、32G，这种通常处理的数据量通常不会很大。如果要是处理的数据量规模非常大的话那么就需要把数据给存到容量更改的硬盘里了，当今TB级别的硬盘已经是非常常见的了。

因为无法一次性的把大规模的数据全部读取到内存中，那么当需要处理某些数据的时候，去找硬盘上到数据然后把它读取到内存中再进行处理。

问题：为什么一定要读取到内存中再处理数据呢？

解答：操作数据是需要CPU去执行相关的指令的，而CPU是不能和硬盘直接交互的。至于原因嘛就是因为CPU太快了，硬盘跟不上CPU的速度，所以得需要内存这个中间人去协调两边。所以想要处理硬盘内的数据需要先把数据给读到内存中然后再进行交互。整个过被称做一次硬盘的访问，也可以叫一次硬盘io

在上图中，假设这些内容都是存在于磁盘中，那么每一次对节点的访问就是一次磁盘的IO。

如果我需要找到13这个数，那么我会经历以下几步

• 第一次访问磁盘找到根节点11- 小
• 第二次访问磁盘找到节点17 - 大
• 第三次访问磁盘找到节点14 - 大
• 第四次访问磁盘找到节点13 - 正确

所以根据以上的流程，我找到13需要4此的磁盘IO，所以由此得出在这种数据结构中硬盘的访问次数和树的高度是正相关的。同理想要减少磁盘的io只需要减少树的高度即可！此时B树就应运而生了

B树和这种二叉树和红黑树最大的不同就是B树可以有多个分叉，每一个节点不止有一个元素。

问题：书的高度是降低了，但是元素个数增加了，这不会增加更多的耗时嘛？

解答：硬盘读取物理地址连读的多个字节和读取单个字节的耗时几乎没有区别；B树的访问节点是在硬盘上进行的，节点内的数据操作是在内存中进行的

以下就是一颗B树，可以看到以下分叉最多就是5个，所以这是一个5阶B树（这个阶数不是固定的）

特性

作为一颗B树，那必须满足三个特性：平衡、有序、多路

平衡：B树的叶子节点一定是在同一层的

有序：B树任何一个节点中的数据都是有顺序的。任一元素的左子树都小于它，右子树都大于它

多路：

1. m阶的B树也是一颗m叉树
2. 上限：他的最大的分叉一定等于m，最多有m-1个元素
3. 下线：根节点最少有2个分支1个元素、其他节点则最少需要有（m / 2 + 向上取整）个分支和（m / 2 - 1 + 向上取整）个元素

查找

以上图为例，查找45

1. 跟17比较 - 小 - 走右边
2. 跟23比较 - 小
3. 跟35比较 - 小
4. 跟47比较 - 大 - 此时走47的左子树也是35的右子树
5. 跟38比较 - 小
6. 跟45比较 - 正确

插入

插入的画也是得先进行比较，还是以上面的图为例插入39

1. 跟17比较 - 小 - 走右边
2. 跟23比较 - 小
3. 跟35比较 - 小
4. 跟47比较 - 大 - 此时走47的左子树也是35的右子树
5. 跟38比较 - 小
6. 跟45比较 - 大 - 此时判断当前节点是否为叶子节点是的话在后面插入

得到下图

并且如果数据到达了上线则会进行分裂，一直分裂到满足特性为止，就比如我需要再次添加两个数据40、41

1. 跟17比较 - 小 - 走右边
2. ……
3. 40插入完成 - 开始插入41
4. ……
5. 跟45比较 - 大 - 此时判断当前节点是否为叶子节点是的话在后面插入
6. 41插入完成 - 此时判断一下元素个数是否等于5（因为是5阶B树） - 满足条件开始分裂
7. 在 38 39 40 41 45 这五个数据中经过 5 / 2 + 向上取整 得到结果3
8. 把第三个数据给父节点，在父节点中排序插入 - 此时判断一下父元素个数是否等于5
9. …….

最后得到下图

这就是分裂完成的B树，如果达到上限他就会一直分裂，哪怕是根节点也是如此。所以他也是从下往上进行成长的树

插入的位置一定是在叶子节点上进行插入的

删除

删除操作在这里面就是替换操作，删除的内容最终都是叶子节点

在删除非叶子节点的数据的时候就需要使用该元素的直接前驱或者后继去替换

比如上图删除17那么找到17的前驱16后继19这两个任意一个进行替换然后把那个元素删除即可，这里我是用后继19去替换17，然后删除原来的19即可，最后得到下图

如果是叶子节点的画直接删除就行了

注意：在删除元素的时候需要保证B树的特定，在删除中就是多路里的下线（根节点最少有2个分支1个元素、其他节点则最少需要有 m / 2 + 向上取整 个分支和 m / 2 - 1 + 向上取整 个元素）

异常情况

比如在删除34的时候就会出现异常，5阶B树其他节点中元素个数必须有2个。这种情况就得需要向左右两边的兄弟借一个元素过来，左边兄弟20 22这个不能借，因为也会出现异常；右边的兄弟有三个数据那么就可以向右边兄弟借一个元素

但是在借的时候不能直接把38这个元素要过来，因为这样会破坏B树有序的特性，所以想要借到38那么他们的父级元素35就得跟着变一变。让35移步到34的位置，让38移步到35的位置，最后在删除38。让父变子，兄变父，这样不仅借到了元素，而且也保证的B树的有序性

删除结果如下图所示

另一种情况，如果左右兄弟都没有办法借那就只能进行合并的操作。比如删除35时就会出现这种情况。

删除35时左右兄弟都没办法借到元素那就只能向左右种地中任意一个进行合并。比如向20 22这个节点中进行合并，因为考虑到有序性所以得让27和20 22节点的父元素23移步到20 22节点中然后再合并27。如下图

上面这就是拆一下父元素然后合并完成了删除，既然父元素能够拆那么父元素就肯定会出现异常的情况。比如我需要删除6就会出现

再我删除6时找到6的后继节点中的数据8补上然后把6删除出现下图

此时11这个节点不满足下线那么进行左右兄弟找一个合并，我选择合并左边的，就会出现下图

此时父节点就会出现异常，这种情况就得找到13的兄弟节点去借一个数据，按照之前说的父变子，兄变父但是与之前不同的时因为兄弟节点还有一个子分支，我们还需要把这个子分支也给移动过来，如下图

还有一种情况，就是两个父元素也不够借的时候那就只能降低树的高度了。比如删除39所出现的情况

在删除39后只剩下45那么就会出现异常，45节点没有左兄弟那么只能合并右兄弟，最后得到的结果如下图所示

这时候异常就出现了，那么这种情况就是55往13 19这个节点合并，流程就是根节点38移步到13 19这个节点中然后55这个节点带着他的子节点合并过来，结果如下

最后树被砍掉一层

B+树

各种资料上B+树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同，还有一种定义方式是关键字个数比孩子结点个数小1。以下我采用第二种方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。

B+树是由B树演变而来的一种树，常常用来作为数据库的索引。B+树和B树非常的相像，但是B+树的所有数据都是存在与叶子节点上的，它的内部节点（非叶子节点）存放的是叶子节点的索引。什么意思呢？B+树的内部节点的作用就是为了快速找到存放数据的叶子节点的

在B树中想要找到某个节点可以使用随机查找，也就是比较查找。但是进行顺序遍历的时候就得使用中序遍历的方式，因为中序遍历的顺序是有序的。这让就会在节点上不停的跳转，效率比较低。B+树的出现就解决了这一个槽点，以下就是一颗5阶B+树

可以看到，他的所有数据都在叶子节点上，这样在随机查找的时候就可以从根节点快速的查找数据，而需要顺序遍历的时候只需要把叶子节点遍历一遍即可（叶子节点之间是存在链表关系的，比如1 2 3这个节点它链接的下一个节点是4 5 6）

特性

B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

查找

顺序查找：比如我要查找一个数字15，在顺序查找的时候从头节点（1 2 3）开始查找，因为叶子节点之间是存在链表关系的，所以从前往后开始遍历很快就可以找到

随机查找：还是查找14，从根节点（13 25）开始查找

1. 跟13比较 - 小
2. 跟25比较 - 大 - 此时走25的左子树也是13的右子树，所以走25的左子树
3. 找到16 19 22这个节点
4. 跟16比较 - 小 - 走16的左子树
5. 跟13比较 - 小
6. 跟14比较 - 相等 - 找到了

混合查找：查找5~13之间的数据

1. 先通过随机查找找到最小数5
2. ……
3. 找到之后通过链表开始往后遍历
4. ……
5. 最后遍历到14的位置发现大于13停止遍历

插入

所有插入的数据都是插入到叶子节点上的，再插入之前都会先去比较一下数据，看看当前元素需要插入到哪个位置

从0开始构建一颗5阶B+树。首先第一个节点它既是根节点也是叶子节点里面有元素1 2 3 4，然后添加5此时该节点出现了上溢出开始分裂。1 2 3是一个叶子节点，4 5是一个叶子节点，他们的父节点元素是4如下图

此时父节点也就是索引节点就创建好了，然后继续添加6、7、8三个数据发现4 5这个节点会发生上溢出此时再次进行分裂，如下图

再次添加若干个数据之后会出现下图情况

此时再次添加一个数据17就会最后一个元素就会发生分裂，但是分裂后父节点的元素也会上溢出，此时父节点也得跟着分裂，但是跟叶子节点的分裂不一样。

叶子节点分裂他不会把m / 2 + 1 + 向上取整的元素给移动到上面而是上面存在他的索引元素本身还在叶子节点中。

而内部节点它的分裂就是B树的正常分裂了，最后结果如下图