共计 2990 个字符,预计需要花费 8 分钟才能阅读完成。
前言需要
咱们上一篇文章中介绍了均衡二叉树,以及为什么会有均衡二叉树?
但其实二叉树的操作效率较高,其实也是存在一些问题的
咱们个别二叉树加载寄存到内存中构建成,如果节点比拟多(亿:单位)
1. 构建二叉树时,须要 屡次进行 I /O 操作
(海量数据存在 数据库 / 文件
中),速度有影响
2. 节点海量,会造成二叉树高度很大,升高操作速度
这时咱们就提出一种树想解决这个问题:多叉树
一、什么是多叉树
根本介绍
1. 在 二叉树中
,每个节点有数据项, 最多有两个子节点
。如果容许 每个节点有更多数据项和更多的子节点
,就是 多叉树(multiway Tree)
2. 多叉树 通过从新组织节点,缩小树的高度
,对二叉树进行优化
(示例图:2- 3 树、2-3- 4 树就是多叉树)
二、什么是 2 - 3 树?
2- 3 树的根本介绍
2- 3 树即是最简略的 B 树结构,具备以下特点:
1、所有叶子节点都在同一层(B 树都满足这个条件)
2、有一个元素项且有两个子节点叫二节点、二节点要么有两个子节点、要么就没子节点
3、有二个元素项且有三个子节点叫三节点、三节点要么有三个子节点、要么就没子节点
4、由二节点与三节点形成的成为 2 - 3 树
咱们发现三节点 EJ、有 AC、H、L 子节点
其中它们的关系是 AC < H < L,而 AC 的关系又是 A < C 的
三、通过示例意识 2 - 3 树
2- 3 树的利用示例
将 数列 {16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20}
构建成 2 - 3 树,并保证数据插入的大小程序。
图解演示 2 - 3 树插入思路
第一步:插入:16 放入后成为二节点(二节点有一个元素项,两个子节点)
第二步:插入:24 放入后成为三节点(三节点有二个元素项,三个子节点)
第三步:插入:12 时按理说应该是插入 16 后面,然而插入 16 前行么?
不行,因为放入后就不是三节点了,变成了三个元素项了,咱们须要拆
第四步:插入:32 比 16 节点还要大,所以咱们从右子节点开始找地位
从右子节点找地位,尝试的从 24 节点后边去放,判断是否满足三节点
第五步:插入:14 同理,比 16 节点小,所以从左子节点开始找地位
从左子节点找地位,尝试的从 12 节点后边去放,判断是否满足三节点
第六步:插入:26 比 16 节点还要大,所以咱们从右子节点开始找地位
按理说咱们应该是放入 24、32 两头的,然而能放吗?
不行,放了就变成三个元素项了,并且也不能成为 24、32 的子节点,因为放了三节点就只有一个子节点了,也不符合要求(三节点要么有三个子节点、要么就没子节点)
因而咱们只能往上拆,使插入 26 节点也满足条件要求
第七步:插入:34 比 26 大,所以咱们从右子节点开始找地位
从右子节点找地位,尝试的从 32 节点后边去放,判断是否满足三节点
第八步:插入:10 比 16 节点小,所以从左子节点开始找地位
按理说咱们应该是放入 12 前边的,然而能放吗?
不行,放了就变成三个元素项了,并且也不能成为 12、14 的子节点,因为放了三节点就只有一个子节点了,也不符合要求(三节点要么有三个子节点、要么就没子节点)
那么依照之前的插入节点 26 的思路,咱们须要拆节点不是嘛?
然而此时并不满足 B 树的特点:所有叶子节点都在同一层
,所以咱们须要调整
第九步:插入:8 比 16 节点还要小,所以咱们从左子节点开始找地位
按理说咱们应该是放入 12 前边的,然而 12 有子节点,再进行寻找
从左子节点找地位,尝试的从 10 节点前边去放,判断是否满足三节点
第十步:插入:28 比 16 节点大,所以咱们从右子节点开始找地位
按理说咱们应该是放入 26 后边的,然而 26 有子节点,再进行判断寻找
按理说咱们应该是放入 32 前边的,然而能放吗?
不行,放了就变成三个元素项了,并且也不能成为 32、34 的子节点,因为放了三节点就只有一个子节点了,也不符合要求(三节点要么有三个子节点、要么就没子节点)
那么依照之前的插入节点的思路,咱们须要拆节点不是嘛?
第十一步:插入:38 比 16 节点大,所以咱们从右子节点开始找地位
按理说咱们应该是放入 26、32 后边的,然而放入后就变成三个元素项了,不过 26、32 有子节点,再进行判断寻找。
从右子节点找地位,尝试的从 34 节点后边去放,判断是否满足三节点
第十二步:插入:20 比 16 节点大,所以咱们从右子节点开始找地位
按理说咱们应该是放入 26,32 前边的,然而放入后就变成三个元素项了,不过 26、32 有子节点,再进行判断寻找。
从左子节点找地位,尝试的从 20 节点前边去放,判断是否满足三节点
四、什么是 B 树
B 树的根本介绍
咱们能够看看 B 树的这些节点图来多多意识 通过从新组织节点,缩小树的高度
1. 如图 B 树通过 通过从新组织节点,缩小树的高度
2. 文件系统及数据库的设计者利用磁盘预读原理,将一个节点的大小设为等于一个页的大小(通常为 4k)
,这样每个节点只须要一次 I /O 即可
3. 将 树的度 M 设置为 1024,在 600 亿个元素中最多只须要 4 次 I / O 即可读取想要的元素
,宽泛用于文件存储系统以及数据库系统中
(会不会有小伙伴发问:什么是树的度 M?)
讲树的度 M 之前须要晓得什么是节点的度?
一般来说咱们都晓得二叉树最多有两个子节点
如果 A 节点有 B、C 两子节点,咱们称 A 节点的度为 2,即度为子树有几个。
那么树的度呢?指所有节点的度里的最大的值,即为树的度 M
B 树的阐明
咱们后面介绍的 2 - 3 树、甚至 2 -3- 4 树,它们也是属于 B 树,我能够先看看之前咱们学习 Mysql 时,常常听见某种类型的索引是基于 B 树或者 B + 树的原理是个什么状况呢?
咱们先阐明 B 树的几个点:
第一点:B 树有一个概念叫:阶,指的是节点的最多子节点个数,比方 2 - 3 树阶是 3,2-3- 4 树的阶是 4
第二点:B 树的搜寻:从根节点开始,对节点内的关键字(有序)序列进行二分查找,如果命中则完结,否则进入查问关键字所属范畴的儿子节点,反复操作,直到所对应的儿子节点为指针为空或者已是叶子节点
第三点:关键字汇合散布在整颗树中,即叶子节点和非叶子节点都存放数据
第四点:搜寻有可能在非叶子节点就完结
第五点:其搜寻性能等价于在关键字选集内做一次二分查找
五、什么是 B + 树
B+ 树的根本介绍
B+ 树是 B 树的变体,也是一种多路搜寻树
咱们阐明 B + 树与 B 树的一些特点
第一点:B+ 树的搜寻与 B 树也基本相同,区别是B+ 树只有达到叶子节点才会命中(B 树能够在非叶子节点命中)
,性能也等价于做一次二分查找
第二点:所有关键字都呈现在叶子节点的链表中(数据只能在叶子节点),这叫浓密索引且链表中的关键字恰好是有序的
第三点:非叶子节点相当于是叶子节点的索引(稠密索引),叶子节点是存储数据的数据层
第四点:不可能在非叶子节点命中
可能小伙伴会很奇怪,不是一上来就找到节点五?
一上来找到的其实是索引,数据它在叶子节点上
咱们能够看看应用场景来体验一下 B + 树的构造
咱们不想一个一个的检索,那么有没有方法把这些数据宰割成几局部?
咱们应用什么算法来体现出这种宰割的思维呢?
如果咱们这时应用 B + 树的构造寻找 28,咱们上来无需从一个节点一个节点开始,只须要找到范畴的索引,一下就过滤了 3 / 2 的不合乎范畴的数据,某种意义来说比二分还狠
六、B* 树
B* 树的介绍
B* 树是 B + 树的变体,在 B + 树的非根和非叶子节点上增加指向兄弟指针的操作
然而 B * 树也有它的规定阐明:
第一点:B 树定义了非叶子节点关键字个数至多为(2/3) M,即块最低使用率为 2 /3,而 B + 树的最低使用率为 B + 树的 1 /2
第二点:从第一点能够看出,B* 树调配新节点的概率比 B + 树要低,空间使用率更高