00:00
各位我们继续往下讲解,那刚才呢,给大家介绍了一下二三数对不对?二三数它的一个构建过程,除了二三数呢,还有一种数,我们称之为234数,二三数的概念呢,对,它和二三,二三数的是类似的,也是一种B数。只是呢,大家看到它有个新的特点什么呀,它它还有一种叫做四节点的这么一种节点,什么叫四节点呢?就说它可以有四个子节点。那其他的整个构建过程跟二三,二三数是一样,我这里呢就不去举例了,接着我们继续来看下一个叫B数,B加数和B心数的概念。那么首先要给B数做一个系统或者说完整一点的介绍,那么B数呢,有人也这样去写,就B一个杠杠。所以说这个你们以后看到B一个杠tree呢,它就是B数,这个B不是binary的意思,同学们不要。
01:04
跟以前那个。那个B混在一起了,这个B是balance,代表平衡的意思,那通过这个大家应该就知道了,我们所说的B数,B加数,B心数,它首恒首先是一棵平衡树,明白我的意思吧,当然平衡树的前提呢,它也必须是一棵搜索树,或者叫做排序树,明白那么有些地方呢,有些书,他把有些书把这个B杠脆翻译成B减数,这个其实是很不好的,为什么呢?因为你这样翻译很容易让人产生这样一个误解,他认为是B。杠树是另外一种数,而B数呢,又是另外一种数,这就混在一起了。因此以后同学们再看到人写B杠,B杠脆就是指的B速,有有些人如果这样写,他说B杠翠树也是指的B数,同学们明白意思吧,也就说没有一个叫B减数的东西,明白吗?这点大家一定要清楚啊,别搞懵了,下面呢,我们来看看B数的一个。
02:05
他的一个示意图,底层的一个示意图。那前面呢,我们已然给大家介绍了2323数和234数,他们其实本身就是B速,因为它是一种平衡术嘛。大家有没有发现他一直在平衡,在做的过程中。那么这里我们再做一个说明,我们在学习MYSQL,经常会听到某种索引,某种类型的索引是基于B数和B加速的,我们来看B数。这种基于数据数据库的这种索引的B数和比价数,它的底层是怎样形成的呢?好,我们先来看这么一个图。OK,那么在讲这个图的时候呢,我们先对B数做几点说明,第1.b数呢?有一个概念叫接。什么叫做B数的阶呢?就是节点的最多指节点的个数,就是B数的阶,你比如说二三数的阶就是三,234数的数,234数的阶呢,就是四,这个大家理解。
03:06
那么B数的搜索,它是从根节点开始走的。那么对节点内的关键字进行一个二分查找,首先它是个有序的啊,如果命中则结束,否则进入查询关键字所属的二次节点。比如说大家看。我还以刚我以这个,我以这个B数为例,比如说我们要查找的是三。这个节点,那么三跟它当前这个根节点一比较,发现3:17还小,于是到它指向的着字节点走,因为这个P1,同学们看到这个P代表指向这个二节点的着字节点。然后这个三呢,再跟它这个八比较,发现3:8还小,再继续指向这个左子节点的。这个着子节点。那么这个左止节点是由P指向的,在这这个地方再一找,发现三就在这个地方找到了。
04:05
也就是说其实它这个地方是,呃,先进行二分,如果找不到呢,我再在它的二次节点去找二次节点继续进行二分查找,那么同学们可以看到这种B数。B数呢,如什么时候找不到呢?就说如果指针为空了,在下面没指针了,没有指针,或者说已经是一个什么呢,已经是一个叶子节点了,那么诶,它就是找不到了。明白我的意思吧,就是说有也有可能你不停往下走,发现这个指针已经为空了。那也找不到,或者说已经是叶子节点在液体节点里面还找不到,那就没有了。那么第三点要注意,注意关键字集合分布整棵树中这句话怎么理解B树的说说法呢?他说关键字集合分布在整棵树中,这句话的意思就是指我们这个关键字可能是在叶子节点,也可能是在非叶子节点。比如说我找26。
05:05
26这个数据项其实就在这个地方。发现没有,那么这个时候它并不是一个叶子节点,而是一个非叶子节点,所以说在B数里面,关键字集合分布在整棵树中。也就是说在叶子节点或者非叶节点都存放数据,明白。第四点,搜索可能在非叶子节点就结束了,比如说刚才我讲的,比如说我们要找26,其实在这个地方就结束,那就没有必要再到非,呃,在这个非E节点就结束,没有必要继续往下走,明白。那么它的搜索性能等价于在关键字全集类做一个二分查找,因为它本身是二分,按照二分这个形式来做的嘛,所以它这个它的性能等价于一个在整个集合做一个二分查找的这种性能,其实也就是我们所说的这个叫做什么呢?叫做线性对数件。好,那关于这个这个做完了以后,我们接着往下走。
06:03
那么现在呢?我们给大家来看一下B加速的概念。B加速的概念B加速它是一个什么概念呢?OKB加速是B数的一种变体。它也是一种多路查找数,它的区别是在于同学们注意看。它的区别是在于什么呢?它的区别是在于它所有的数据都会放在叶叶子节点,而不会放在非叶节点,你看这个这个这个这个都是非叶子节点,这里面不再存放具体的数据了,它所有真实的数据全部都在叶子节点。这是第一点大家注意的。那么呃,第二点呢?呃,所有的看这已经说清楚了,所有的关键字都出现在叶子节点的链表中。那么,即数据只在叶子节点出现,那么这个也叫稠密索引。且链表中的关键字刚好也是有序的,大家发现没有,它的关键字的确是有序,看587这个地方是代表它有指向下一个叶子节点。
07:12
那下一个介质点的呢,又是从十开始,十,十五十八也是有序的。好,这是第二句话,第三句不可能在非yes节点命中,那有些同学可能会说了,说老师你你这个图画的有点不对吧,比如说有些有些同学,老师你比如说找一个五,他上来给我不一下就直接找到这个五了吗?注意这个舞代表的是缩影。并不是真实的数据,那个节点了,他会继续往这边找,找到这个五再往下面找,这个五才是真实的数据,才会停止明白。好的,那么再看非叶子节点,相当于是叶子节点的索引,就说你们看到的这一大块。才是真正的索引,也叫什么呢?稀疏索引,而这个里面的数据呢,才是真正的数据,它也叫稠密索引。
08:01
明白,所以说这种结构呢,它更加适合文件索引系统。那当然有些同学就说了,说老师B数和B加数哪个更好呢?其实理论上来说没有谁更好更坏的问题,主要是看它的一个应用场景。主要是看它应用场景,那比如说在文件系统里面,我们这个B加速,它的性能就很优秀。那有些同学老师,那你这个讲了过后,我完全不太清楚,这个必加速它有什么用啊,好同学们,我这样讲可能大家就明白了,因为你拿到一个B加速这个结构,其实如果你是第一次接触,你很难理解。他的这种设计理念,我们站在设计理念再给大家讲两句好不好,大家注意听啊,这是老师对他的一个理解,大家也可以看看,比如说大家看。我们假如不用这个B加速,注意听,假如我们不用这个B加速做这种做这不用做,不用B加速这种结构。
09:00
我们来去管理数据,我们会怎么做呢?大家看我现在一共有几个数据,这有三个数据,是不是这也有三个数据,我一共有几个,一个两个三个,四个,五个,六个,七个,八个九个,OK,那也就是说一共有27个数据。是不是这是第一个五,如果我们链表存放的话,下一个就是八,再下一个就是九,我们按序列除往下走好,走走走走走走走走走好,最后这个节点是假如这也这不停往下走啊,假如这个地方有个节点是28。最后这个节点呢,是99,大家发现没有是这样子的,OK,同学们,这个是一个什么,这是一个单链表。这是不是一个单链表,同学们。是吧,各位同学大家想,如果现在我给大家一个要求,请大家检索到第28这个数据,是不是你只能从这地方一个一个一个的比较,才能找到28。
10:00
是这样子吧,那大家想,如果,如果是我是一个设计者,如果韩老师是个设计者,是不是?我希望咱们不要从头开始找,太累了。太累了,因为从头开始到太累了,我们能不能有一种办法把这个表分割成几个部分呢?我们能不能把它分割成几个部分呢?比如说我三个,我把这三个分成一个一个部分。或者说再三个再分成一个部分,再三个分成一个部分,分成几段,明白我的意思吧,分成几段,比如说现在我们就按照他的设计分成九段。分成了九段,每一段有三个数据,明白我的意思了吧?可是你把它分成九段,你怎么用一一个算法来体现出这种分割的思想了?OK,他的他的想法就很简单,大家看他,首先大家看这里。他说你要分割是吧,好,这边第一个是五开始的,往这边走,那么中间是28。
11:00
再下面是65,我先把它分割成三段。好,下面每每每每一个范围就是五到28这个范围再分割成三段。八就是我们所说的这个28,下面呢,再分割成三段。在这个65下面指向的再割分割成三段,好,你看这样这样子就比较有意思了,看这是五,这是十,假设是十啊,假设是20,这是20是吧,20好,这边我就不画那么多了,好让五开始指向这里,这是第一段,让十指向我们的第二段,让20指向我们第三段,好假设这次我们的28 28指向我们这个链表的第四段,完事后面我就不讲了,大家明白我我想做什么事了吧。哎,你看这样的思想就相是不是有点类似于把我们这个链表割成了九段。甲割成了九段,割成了九段,我再去找28,哎,你们发现没有就很快了,我上来过后,我先不从这个地方找了,我怎么找呢?我先从我这个这个部分我们就称之为索引。
12:13
也就是说这一块就是我们真正意义上的索引,就是刚才大家听到的稀疏索引的概念,他把因为他分了,那我怎么找呢?如果我要找28,我上来过后先到这个地方去找,因为这个很快嘛,它这三个一找,啪哦,28,从这28的指向的那一个块是哪个块呢?指向这个块。好一一下就定位了,这相当于一下就砍掉了几个,你们知道吗?一下就把这三三个块砍掉了。也就是说,你原先九段,现在一下就砍砍掉了三段。砍掉三段过后,再往这边一中间一走,发现28其实这一块的相因为是28,那你只能是28~65之六,65之间了,相当于又把这一块又砍掉了,大大想他这个可可相当于不是砍了二一半了,相当于砍掉了2/3了,大家明白我的意思吧。
13:05
说他比这个二分砍的更厉害,因为相当于为我,我知道我一比较这个数,我就知道他在哪一段了,是不是在哪一段了,因为你原先如果是二分二叉树的话,你只能一半一半砍,现在我一砍,我知道28 28是介于这个28~65之间的,因此呢,我敢肯定他只能是在这个块里面。那相当于说你已经把前面这三段和后面这三段干什么扔掉了,是不是相当于相当于三段里面砍到了两段,那你只能在这找,诶再往下面一一看,在。往下面看,28跟这个匹配,直接取出来就可以了,如果28不是呢,再比较这个不就完了吗?明白意思吧,这里面它还可以继续下下索引啊,还可以继续下索引,你看这么281:2找到了是不是。是不是这样子就可以完成了?性能当然是很卓越的,而且关键是它能够降低我们这个树的高度。
14:03
所以说它这个性能是非常OK的,非常OK的,因此呢,大家看说在很多文件索引系统里面呢,我们这个B加速用的非常多的。好的同学们,那么这里呢,关于我们B数和B加数,先给同学们聊到这里,一会呢,我们再给大家讲。心。
我来说两句