tip:这里对多路查找树是简单介绍和讲解,因为这部分属于深入学习了
二叉树的操作效率较高,但是也存在问题,如下图所示
当二叉树的节点较少时,不会出现什么问题。但是当节点过多时(海量,如 1 亿),就会出现如下的问题:
构建二叉树时,需要进行多次 I/O 操作
节点较多时,一般会存储在文件或则数据库中,进行多次 I/O 获取到所有的节点,速度有影响
会造成二叉树的高度很大,降低操作速度
为了解决层数过多的问题,就出现了 多叉树。
在二叉树中,每个节点只有一个数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是 多叉树(multiway tree)。
多叉树也有一定的规则的,比如后面讲解的 2-3 树、2-3-4 树,就是多叉树。
多叉树通过重新组织节点,减少树的高度,对二叉树进行优化。
下图则是一颗 2-3 的多叉树:
2-3 的原因:如上图按节点数量来定义的。有的只有 2 个子节点,有的有 3 个子节点。
B 树通过重新组织节点,降低树的高度,并且减少 I/O 读写次数来提升效率。
上图说明:
那么它的优点如何理解呢?
降低树的高度:
可以看到,一个节点中有很多数据项,就能大大减少节点数量,从而降低树的高度
减少 I/O 读写次数
文件系统及数据库系统的设计者利用了 磁盘预读原理,将一个节点的大小设为等于一个页(通常大小为 4K),这样每个节点只需要一次 I/O 就可以完全载入。
这样说,你可能没有概念,举个例子:将树的度 M 设置为 1024 ,在 600 亿个元素中最多只需要 4 次 I/O 操作就可以读取到想要的元素。
B 树(B+ )广泛应用于文件存储系统以及数据库系统中。
什么是 度?
B 树其实就是前面所说的 多叉树
2-3 树是最简单的 B 树结构,具有如下特点:
所有 叶子节点 都在同一层
只要是 B 树都满足这个条件,就是满树。
有两个子节点的节点叫 二节点
二节点要么 没有子节点,要么 必须有两个子节点。
有三个子节点的节点叫 三节点
三节点要么 没有子节点,要么 必须有三个子节点。
2-3 树是由 二节点 和 三节点 构成的树
对数列 {16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20}
构建成一个 2-3 树,那么它构建的规则要满足前面说的特点。下面进行图解后,你就明白,上面的特点是如何限制的。
有几个额外的注意事项:
下面是图解步骤:
添加 16、24
添加 16 时,没有数据,直接新建一个节点,放进去。
添加 24 时,发现有一个节点了,并且比 16 大,此时该节点中只有一个数据,则将 24 放在 16 的右边。
添加 12
此时会发现,12 比 16 小,本来应该放在 16 的左边,此时发现这个节点 已经有两个数据了,那么就只能放在 左子节点 。
如果直接将 12 放到 16,24
的左节点,就会破坏 2-3 树的条件:2 节点,要么没有子节点,要么有两个。
那么此时就只能将 16,24
这个节点进行拆分。如上图:24 变成 16 的右节点,12 变成 16 的左节点。这时就满足了 2-3 的特性。
添加 32
这个就简单了,以现在的树结构,可以直接添加到 24 的 右边,变成 24,32
添加 14
这个也简单,直接添加到 12 的右边,变成 12,14
添加 26
此时应该添加到 24,32
的中间,由于一个节点只能添加两个数据,那么就需要拆分。
为了满足 B 树特点,发现上层的 16
只有一个数,那么就补足它。组成 16,26
。
因为此时 24,32
这个节点,不满足 BST 的排序了,24 是小于 26 的。只有 32 满足。
拆完上层,再拆本层:由于 24 介于 16,26
之间,则将它安排在 3 节点中的中间节点,24,32
把 24 拆分出去了,只剩下 32
,此时完全满足 B 树的特点。
添加 34
此时就简单了,添加到 32,34
中
添加 10
此时应该添加到 12,14
的左侧。但是不满足条件:一个节点最多只能装 2 个数据。
放到 12,14
的左节点,也不满足条件:所有叶子节点必须在同一层,并且也不满足 2-3 节点的数量要求。
那么此时就需要拆分,先看他的上层 16,26
是满的,如何做呢?看下图:
左侧的拆分图,上面我们分析过了,不满足 B 树要求。那么就需要拆分成右图这样:
12,14
中的 14 拆分成 右子节点,10 挂在 左节点。16,26
中的 26 拆分成 右子节点。24
这个节点由于上层被拆分了,不满足在中间节点了。调整它的位置32,34
节点调整为 16
的右节点。添加 8
此时很简单,组成 8,10
即可
添加 28
这里笔者有点小小的疑问,此时 28 不是应该加在 26,28
吗?难道说这里还有一个规则:
添加 38
此时就简单,直接组成 34,38
添加 20
这个也简单,直接组成 20,24
满足如下特点:
所有 叶子节点 都在同一层
只要是 B 树都满足这个条件,就是满树。
有两个子节点的节点叫 二节点
二节点要么 没有子节点,要么 必须有两个子节点。
有三个子节点的节点叫 三节点
三节点要么 没有子节点,要么 必须有三个子节点。
2-3 树是由 二节点 和 三节点 构成的树
构建的树,要满足二叉排序树(BST) 的顺序
一个节点中,最多只允许放 2 个数据。
只有一个数据的节点,下面只允许 最多有 2 个节点,要么没有
有 2 个数据的节点,下面只允许 最多有 3 个节点,要么没有
除了 2-3 树,还有 2-3-4 树,他的特点是在 2-3 树的基础上,还多了一个 4 节点,同样,一个节点最多可以装 3 个数据,要么有 4 个节点,要么没有。
B 树
、B+ 树
、B*树
B-tree
树即 B 树,B 是 Balanced
平衡的意思。
tip
B-
树,这个也是B 树
,只是翻译的文本容易产生误解。
上图就是一个 B 树,说明如下:
B 树的阶:节点的最多 子节点 个数
如:2-3 树的阶是 3,2-3-4 树的阶是 4
B 树的搜索
从 根节点开始,对节点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的 儿子节点。
然后重复,直到所对应的儿子节点指针为空,或则已经是叶子节点。
关键字集合分布在整棵树中
即:叶子节点和非叶子节点都存放数据
搜索有可能在非叶子节点结束
其搜索性能等价于在关键字全集内做一次二分查找
在 MySQL 中,有些索引就是用 B 树或则 B+ 树实现的。B+ 树是 B 树的变体,也是一种多路搜索树。
B + 树说明:
B+ 树的搜索与 B 树基本相同,区别是 B+ 树只有到达叶子节点才命中(B 树可以在非叶子节点命中),其性能也等价于在关键字全集做一次二分查找
所有 关键字都出现在叶子节点的链表中
即:数据只能在叶子节点,也叫 稠密索引,且链表中的关键字(数据)恰好是有序的。
不可能在非叶子节点命中
非叶子节点相当于是叶子节点的索引,也叫 稀疏索引,叶子节点相当于是存储(关键字)数据的数据层
更适合文件索引系统
B 树和 B+ 树有各自的应用场景,不能说 B+ 树完全比 B 树好。
B+ 树的这种设计,应该是类似分段思想,比如:5,28,65
,下面存放三个节点:
5-28
的段,为一个节点28-65
的段,为一个节点65
以上的段,为一个节点比如查询 30 ,直接找到在第二个节点中,然后往下一个目录索引找,就很快能定位到数据。
B*
树B*
树是 B+ 树的变体,在 B+ 树的非根和非叶子节点再增加指向兄弟的指针
说明:
B*
树定义了 非叶子节点 关键字个数至少为 (2/3)*M
,即块的最低使用率为 2/3
,而 B+ 树的块的最低使用率为 B+ 树的 1/2
M 是指树的度,也就是层。
从第 1 个特点,可以看出 B*
树分配新节点的概率比 B+ 树要低,空间使用率更高。