图解 B 树 B+ 树算法

JAVA日知录 一个关注| Java | Spring Boot | Spring Cloud | 干货分享的博客网站 本文由博客端 http://javadaily.cn 主动推送

1. B 树

在介绍 B+ 树之前, 先简单的介绍一下 B 树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

1.1 B 树概念

B 树也称 B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生,其实,B 树和后面讲到的 B+ 树也是从最简单的二叉树变换而来的,并没有什么神秘的地方,下面我们来看看 B 树的定义。

所以,根节点的关键字数量范围:1 <= k <= m-1,非根节点的关键字数量范围:m/2 <= k <= m-1

另外,我们需要注意一个概念,描述一颗 B 树时需要指定它的阶数,阶数表示了一个节点最多有多少个孩子节点,一般用字母 m 表示阶数。

我们再举个例子来说明一下上面的概念,比如这里有一个 5 阶的 B 树,根节点数量范围:1 <= k <= 4,非根节点数量范围:2 <= k <= 4。

下面,我们通过一个插入的例子,讲解一下 B 树的插入过程,接着,再讲解一下删除关键字的过程。

1.2 B 树插入

插入的时候,我们需要记住一个规则:判断当前结点 key 的个数是否小于等于 m-1,如果满足,直接插入即可,如果不满足,将节点的中间的 key 将这个节点分为左右两部分,中间的节点放到父节点中即可。

例子:在 5 阶 B 树中,结点最多有 4 个 key,最少有 2 个 key(注意:下面的节点统一用一个节点表示 key 和 value)。

更过的插入的过程就不多介绍了,相信有这个例子你已经知道怎么进行插入操作了。

1.3 B 树的删除操作

B 树的删除操作相对于插入操作是相对复杂一些的,但是,你知道记住几种情况,一样可以很轻松的掌握的。

删除就只有上面的几种情况,根据不同的情况进行删除即可。

上面的这些介绍,相信对于 B 树已经有一定的了解了,接下来的一部分,我们接着讲解 B+ 树,我相信加上 B+ 树的对比,就更加清晰明了了。

2 B+ 树

2.1 B+ 树概述

B+ 树其实和 B 树是非常相似的,我们首先看看相同点。

不同点。

下面我们看一个 B+ 树的例子,感受感受它吧!
image.png

2.2 插入操作

对于插入操作很简单,只需要记住一个技巧即可:当节点元素数量大于 m-1 的时候,按中间元素分裂成左右两部分,中间元素分裂到父节点当做索引存储,但是,本身中间元素还是分裂右边这一部分的。

下面以一颗 5 阶 B+ 树的插入过程为例,5 阶 B+ 树的节点最少 2 个元素,最多 4 个元素。

有了这几个例子,相信插入操作没什么问题了,下面接着看看删除操作。

2.3 删除操作

对于删除操作是比 B 树简单一些的,因为叶子节点有指针的存在,向兄弟节点借元素时,不需要通过父节点了,而是可以直接通过兄弟节移动即可(前提是兄弟节点的元素大于 m/2),然后更新父节点的索引;如果兄弟节点的元素不大于 m/2(兄弟节点也没有多余的元素),则将当前节点和兄弟节点合并,并且删除父节点中的 key,下面我们看看具体的实例。

这样,B+ 树的删除操作也就完成了,是不是看完之后,觉得非常简单!

3 B 树和 B+ 树总结

B+ 树相对于 B 树有一些自己的优势,可以归结为下面几点。

  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    281 引用 • 595 回帖
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    271 引用 • 1353 回帖 • 214 关注

赞助商 我要投放

回帖
请输入回帖内容 ...