00:00
各位同学,我们继续来讲解数据结构和算法的下一个章节,叫做多路查找数,那同学们可以看这个名字。那通过这个名字呢,我们可以。推断出来这种数呢,它的子节点就不仅仅只有左子节点和右子节点可能有更多,那么我们来看一下何为多路查找树,那在讲这个多路查找树之前呢,我们先来给大家说一下二叉树和B数的一个关系,或者说我们说二叉树存在怎样的一个问题。我们先来看对二叉树它的一个问题的分析,二叉树的操作效率比较高,但是也存在一些问题,请各位同学看下面这棵树。同学们看这一棵树是一棵二叉树,它是一棵什么二叉树,大家大家能看出来吗?它是一棵满二叉树。对不对?那么满二叉数我们在前面讲过,它的这个节点有二的N次方减去一还记得吧,这个N代表它总共它的高度,或者或者说它的乘数,那么对于这棵满二叉数,它的个数应该是二的五次方减去一个一等于多少呢?
01:12
各位同学,等于31是不是?这我算了一下。那大家可以看到。二叉树的。这样一个构建形式,构建形式那么我们可以分析出来,可以分析出来二叉数它是需要加载到内存的。也就是说,我们要去使用一棵二叉树呢?需要把数据加载到内存,构建成这棵二叉树。那大家看我们这个节点很多,很多的情况下就存在问题,如果说二叉树的节点比较少,那没有什么问题,但是如果二叉树的节点比较多,比如说假如我们节点有1亿个,你还是。一个节点,一个节点的存放,那么就存在如下的问题,什么问题呢?第一个问题大家看,在构建二叉树的时候,需要多次进行IO操作,为什么呢?因为你这个节点的数据很有可能是来自于文件,也有可能是从数据库读取,读取到内存然后构建的,因此你的节点的个数很多,你的节点个数很多,那么就意味着我们要进行多次的IO操作。
02:25
那么才能构建这个二叉树,所以说在构建二叉树的时候呢,会有影响。对不对。好,这是第一个问题,第二个问题,如果我们这个节节点海量,假如你把这棵二叉树构建起来了,它的节点很多。节点很多,那么也会造成二叉树的高度太高了,因为什么呢?因为你看你一层,你的每一层是不是哦,或者这么说,你的一个节点只有左子节点和右子节点,但是你的节点又很多,那必然造成我们这颗二叉树的高度很很高,那如果二叉树的高度很很大的话呢,也会降低,我们的操作是这样是吧,比如说我们这个这个二叉树这么高。
03:08
三层还没问题,但是你假设有。三千三千层呢。对不对,那这个量就很大了,同样也会存在。这个速度和效率的问题。大家想是不是这个问题,但是我我说的是一个极端的情况啊,我说的是一个极端的情况,但是不管你说的情况极不极端,这种可能性是存在的,你可能性存在的根本原因是为什么呢?其实就是因为你这个二叉树,它只有左侧节点和右侧节点,也就是说它的一个节点。他最多只有只有一个左一个右。一个左一个右,而且你这一个节点呢,大家看到没有一个节点就放就放一个数据项。是不是这样的一个问题,从而当我们节点海量的时候,就可能造成这棵二叉树的高度太大?从而降低我们的这个操作的速度,这是它这个问题,那么解决这个问题怎么解决呢?OK,同学们看,我们就提出了一种数叫做多差数。
04:07
听这个名字呢,就是这棵树呢,分的这个差很多,原先是二叉,现在是多差了,可能是你分三个叉,分四个叉都有可能。好,我们接着来看看多差数。各位同学,我们看在二叉数中呢,每个节点是有数据项的,一般只是一个对吧,一般就是一个,那么最多我们有两个节点,是这样子吧,如果允许每个节点注意听,如果允许每个节点可以有更多的数据项和更多的子节点,那么这个就称之为多差数,叫做。Mot motiv motiv。后面我们会马上讲解到,一种数叫二三数,还有一种数叫234数,这些都属于多差数。那么多差数,它的好处是通过重新组织节点,减少树的高度。大家看到。多叉树,它可以降降低我们这个树的高度,也就是说减少我们树的层数,从而可以对原有的二叉树进行优化。
05:09
事实上呢,在我们数据库里面做索引的时候,往往我们就使用的B速必加速明白。好,那么我们现在举例说明一下,何为二三、二三数呢?我们先把二三数讲了二三数,讲完了234数,自然大家也就明白了这个概念,并不难,同学们,并不难啊,我们先看一棵二三树,大家看这里。这有个节点13,它有左子节点和右子节点,看到没有,好它的左子节点呢?大家看到没有,这个左子节点里面有两个数据项,八和12,我们所说的数据项是指的关键数据项,明白,而且大家有没有发现这一个我标我圈起来的这个呢,是一个节点。是一个节点,这个节点里面有两个数据项,同时呢,它有三个分支,大家有没有发现OK,向左边的。
06:06
是指向一个七的节点中间的这个分支指向十这个节点右边的。这个子节点指向它的另外一个节点,看到没有,同学们有没有发现?相当于这个节点,这个节点它。他的这一个子节点已经超过了两个。那么这个时候呢,我们就把它称之为多差数。大家看这个就叫三节点,就说我们如果把这个82这个节点,用我们的术语来讲呢,这个就叫三节点,那么在多差数中,假如我们有个节点,它只有左侧节点和右侧节点,我们就把它叫做二节点。大家明白什么叫三节点,什么叫二节点没有,也就是说,如果你这个节点有三个分叉,三个分叉或者是三个子节点,那么就叫三节点,如果有一个节点,它只有两个子节点,我们就叫二节点。这个概念要清晰,OK,好,现在呢,这样大家可能还是不太明确,对吧,说老师这个地方我我还是不太明白你在说什么,那这样子我们我们接着往下看,我们接着往下看,那么这里呢,我们来看一棵B树的基本介绍,后面最近我们后面还要讲B树。
07:20
我们还要讲B速,这里呢,我们先给大家看一个简单的B速,同学们,B速呢,它通过重新组织节点,降低数的高度,大家看。我们有没有发现这这张图,这张图的节点其实就按照以前那个小圈的话呢,就是一个一个小圈代表一个数据项,那么这个代表一个什么呢?各位同学,这个代表一个节点。这个呢也代表一个节点,这个代表又一个节点明白,只是这个节点里面代这一个节点里面的数据项呢,有多个明白。OK,这个就是一棵B树,这个就是,那么如图B树通过重新组织节点可以降低树的高度,如果按照我们以前的二叉树在有这么多的这个小圆圈。
08:07
或这个小圆圈,这个小圆圈就你可以理解成代表代表一个数据项。数项啊,数据项,而整个这个呢,代表一个节点。这个整个代表一个节点,明白好,那这样子呢,我们相当于把一个一个节点里面可以存放多个数据项,OK,那么这样子我们就在相同的情况下,这个树的高度就降低了。那么降低了带来的好处是什么?大家是是不是我们检索的速度就会更快,还有一点,大家看文件系统,还有数据库系统的设计者呢,一般他会利用一个叫做磁盘预读的原理,什么叫磁盘预读呢?就是预先我们从磁盘里面读取一些数据。读取这个数据,将一个节点大小,如果我们啊,注意听,如果我们将一个节点大小设置设置等于一个页,一个页呢,一般是4K。
09:01
4K,那么每一个节点只需一次IO就可以完全载入,因为我一次读取一个,那数据量就很大了嘛。那么假如我们这个数的度M设置为1024,我先说一下什么叫做数的度啊,大家了解一下,因为这这块呢,我们只只需要做一个了解就可以了,所谓数的度呢,它是指的这个意思。呃,它是指的这个意思,我们先讲数的度之前要提,要提一个叫做节点的度。节点的度。我先说一下节点的度,再说数的度,节点的度指的是什么呢?就是你一个节点,你一个节点下面的这个指数的个数有几个,比如说你这有个节点A节点,它有两颗指数,那么这个节点的度,这个A节点的度呢?就是二理解了吧。那么数的度指的是什么呢?数的度是指的所有的节点里面那个节点,所有的节点里面那个度最大的,最大的那个值就是。
10:06
就是这个数的度,明白了吧?啊,就是这个意思啊,那么呃,这有一个简单的公式和一个结论,大家知道就可以了,不需要去刻意的记,就说假如我们有一棵树,它的度我们是1024,那么假如我们现在有6亿个元素,6亿个元素。那么在六一个元素中,最多我们只需要四次IO操作就可以读取到想要的元素,OK,那这个特点,这个这个速度非常快的了。也就是说我们其实是很快就可以把一个。在一个文件或者在一个文档里面的数据,快速的怎么样找到,明白这意思吧。明白的意思,OK,那么我们在这说一下B速,它利用这个特性,利用这个特性广泛的应用于文件存储系统和数据库系统,也就是说你们是不是经常在你们在学这个MYSQL或者学Oracle的时候,往往往往这个书上会有一句话说它的索引是基于B速或者是必加速的,有没有这有没有这种说法呀?
11:17
他就是利用这个特性来快速定位我们的元素啊,这个地方应该B速用了,B加速也用啊,B加速也用,大家不要着急,这么我还没有把这个B数和B加数,呃,详详细的给他介绍,你们先有个概念。好,这是B数,那么B数其实就是,其实就是我们前面说到的多差数啊,它就是一种多差数,明白。
我来说两句