00:00
好,那么关于这个B加数这个结构啊,咱们讲的呢,就算是比较清晰了啊,那么具体呢,在我们存储引擎像MYS和诺DB当中啊,那体现为呢,就是索引和二级索引,那如果给到大家一个啊,说是叫B加啊,让你判断一下它是不是一个合格的加,以及呢,诶我们这个B加数呢,是一个居束索引呢,还是一个二级索引呢?哎,大家要能有能力呢,给它判别出来。好,那这个呢,我们就先说到这儿,然后接下来的话呢,我们再看一看呢,除了这个B加数之外呢,其他的一些数据结构啊,以及呢,为什么我们的MYS和诺DB呢,没有选择其他的这些数据结构,那我们做个对比,通过这个对比的话呢,让大家呢,对这个加数呢,有一个更深刻的一个认识。好,这呢就提到了我们MYSQL呢,数据结构选择的一个合理性,呃,首先的话呢,我们选择的一个标准是什么呢?诶这块呢,明确提出来就是磁盘IO的一个操作次数。啊,就是一个操作次数啊,这里边儿呢,我们就提到一个点,凡是呢,我们讲到这个算法的时候啊,通常我们都会提到一个算法的一个复杂度,对吧?比如说呢,我们这个呢,复杂度呢叫N方,然后这个复杂度呢,叫LOG2N,那很显然的话呢,我们这个复杂度呢,叫低一些啊随着这个N的增加呢,它这个时间呢,呃,增长的比较慢,诶我们说呢,这个算法呢,是不是要好于我们这种算法对吧。
01:23
但是这时候呢,你大家要注意,我们此时讨论的这个所谓的算法优劣呢,还都是在内存层面,看看谁的这个复杂度高,谁的复杂度比较低,诶他们两个的差别呢,有可能本身呢,就是几毫秒的事儿。啊,就是几毫秒的事儿,或者十几毫秒的事儿,甚至说几十毫秒的事儿啊,也就这样,但是呢,有一个比他这个更耗时的一个操作呢,就是咱们呢,把这个索引啊,以及呢,这个索引最后呢,我们对应的那个数据页是吧,加载到咱们内存中的时候啊,就是从磁盘到内存中这个加载过程花费的时间呢,是非常多的啊达到呢,比如说几百毫秒这样的一个程度,那你想想我们要多加载一个呃这个页结构,那你相应相对应的是不是要多呃执行一次几百毫秒,那相较于我们这里边呢,只差几毫秒甚至十几毫秒来讲,这个呢,是不是简直呢都可以忽略不计了,那我们重点要关注呢,就是咱们把这个呃页从这个磁盘加载到这个内存中的时候呢,这个加载的这个次数啊,那我们也就成为了这个IO操作的一个次数。
02:24
这个呢,才是咱们关注的一个重心。啊,这个要说明一下。啊,那既然是这样了,那有同学可能会想说,我们为什么不把这个呃数据页或者索引的这个结构呢,完整的都加载到内存中,一次性都加载了以后呢,我们只需要呢,从缓存当中啊进行这个呃取出数据呃进行这个查找就可以了,是吧,这样行不行呢?呃这样的不现实,因为呢,当我们的数据量比较大的时候呢,咱们这个索引呢,也会比较大啊,甚至呢达到几个G。那么这个索引这么大的话呢,你想我们就不可能把这个索引的数据呢,全部加载到内存当中,那这个占据量呢,也就太多了啊,正常来讲,我们说这个索引都是放在这个磁盘上的,对吧?诶不可能把它一次性都加载到内存中,那我们只能是在你需要的时候呢,就做这个加载,那既然如此,你需要时候呢去加载,那我们是不是就希望呢,尽可能的需要的次数就少一点,进而的话呢,这个IO的次数呢,就少一些,来提升我们查找的一个效率,对吧。
03:20
啊,这是这样子的,先明确我们的标准,然后呢,我们再来看一看这些数据结构,哪些靠谱,哪些呢就不太靠谱,哪些呢有使用上的一个局限性。首先的话呢,提到一个全表的便利啊,这个呢,我说这我写的啊,都懒得说了,为什么呢,就相当于呢,我们把这个索引,呃,就是相当于一个顺序的一个查找了,咱们呢,呃,就先把这个,所以呢对应的一些数据加载进来,然后没有,然后我们再找下一个,再没有再找下一个顺序的方式去查找,那假设我们要找这个数据呢,恰好比较特别,就在我们最后一条上,那是不是就意味着我们把几个G的这个索引数据啊,或者数据的数据全都加载了,那显然的话呢,这个磁盘IO次数呢就太多了,性能极差,所以这个呢,都懒得说了。
04:01
那么第二种结构的话呢,我们称为它叫哈希结构啊,叫做哈希结构这里边也提到了啊,放眼我们不同的编程语言,或者我们放眼叫数据结构啊当中,要想加速查找的速度的话呢,实际上呢,是有两类啊,典型的这种算法的一类呢,就称为呢叫哈希算法啊,对应呢,其实就叫哈希结构,另外呢,就是一种树形结构啊,其实就我们后边呢,要展开的这个树形结构这个讲解,那树形结构这块呢,我们一会儿呢再说啊,咱来先说一下这个叫哈希这个结构啊,当然你会看到这个复杂度呢很低是吧,能达到一个常量级别的。啊,那么这个哈希呢,是一个什么特点呢?它其实对应的是一种算法叫哈希算法,比如MD5这种算法等等,啊把这个输入呢,转换成输出,它能够保证的就是呢,相同这个输入呢,永远可以得到相同的输入输出,比如说我们通过这个哈,这是一个字符串,诶咱们拿这个哈希的这个函数呢,这样一包,咱们算出来的具体的这个哈希值啊,你拿。这个hello啊,这会儿算是这个值,那过了一会儿呢,再算还是这个值啊,相同的输入呢,永远会得到相同的输出,那我们来一个HELLO1啊,跟刚才那个hello呢,你看就有一个微小的区别,哎,只要这个区别是有的,不是完全相同的,我们算出来这个哈希值呢,它就是不一样的。
05:15
啊,这是我们这个哈希算法它的一个特征。那具体应用的话呢,呃,这块我还举了一个例子,比如说呢,我们想比较两个文件呢,是否相同啊,那你可以拿两个文件呢,一点点从头去比啊,实际上实际上呢,这个效率呢就比较低,有点类似于像我们这样的一个方式一样,对吧,那怎么能快一些呢,我们把这两个文件呢,咱们诶通过这个哈希函数的方式呢,计算出来一个值,直接呢比较这两个值是不是相等就可以了。啊,那显然这个效率呢要更快一些,那对于两个变量来讲呢,也可以采用这样一种方式。啊,正运呢,可以采用这种方式呢,所以说呢,我们在查找方面呢,它的效率就非常的高,那比如说呢,大家啊,像有的同学呢,应该接触过这个Java,在Java里边呢,我们容器当中有一个非常重要的结构呢,叫哈希map,在哈希map里边呢,它存储的是不是就都是这个key value啊这样的建值对特点的数据,对吧?那这里边呢,我们要保证呢,就是所有的K呢,它都是不相同的,那现在的话呢,比如我们想通过诶这个K啊找一下我们这个哈奇map,我叫K1吧。
06:15
说那哈map当中有没有K1这样的一个键,如果有的话呢,你把对应的那个Y6呢,哎,你给我返回一下,那那怎么办呢?那有同学会想,那我是不是就顺序的去查找一个一个的这个K,然后看看有没有这个K1啊,那就类似于我们刚才上边说的那个顺序的一个事儿啊,显然效率比较低啊,那怎么办呢?诶咱们呢,就把这个你要找的这个K1啊,咱们用这个哈希的这个函数呢,这样包一下得到一个值是吧,这个值的话呢,我们就去这个数组当中去找了。啊,去这个数组中找,其实这里边还得需要压缩到相应的这个数组中的一个位置上啊呃,这个呢,咱们就忽略掉这个细节的讲解了,那么呃,那么在你对应的那一支上呢,能够找到了,诶那其实这块呢,就是我们想要的那个数据,诶没找到没有没有呢,我们就就是没有了。哎,就是这样啊,所以它这时候呢,相当于退化成就是OE级别,是一个常量级别的一个查找的效率。
07:05
啊,当然这个我们找它的一个前提是什么,是咱们当初往里边放这个数据的时候呢,是不是也是以这个相应的K的含义值来决定在这个数组中存放在哪个位置上,对吧?诶是这样的一个特征。所以说呢,从这个检索效率上来讲的话呢,实际上我们这个哈希算法呢,比我们这个B加速呢还要快。啊,那为什么没有选择这个哈希算法,这个哈希索引呢?哎,这个咱们一会儿再说啊,哎,一会儿有这样的一个说明。啊,接着再看这个事儿啊,我们关于这个哈希呢,咱们再讲解一下,呃,我们呢,通过不同的K啊,咱们经过一个哈希呢,让它存放在这个数组中的不同的位置,呃,那万一要是两个不同的K,哎,算完哈西以后呢,有没有可能得到同一个值呢?呃,这个尽量的我们保证它是不同的啊,尽量保证不同的,但是的话呢,有可能会出现的点就是即使这两个啊,比如我们这里边这个K2跟这个K5算出来含义是不一样,但是呢,它要压缩到这个数组中的时候呢,比如我们采用这种取模的方式是吧?诶,压缩到这个数组中的时候呢,有可能它就是在同一个位置上。
08:04
啊举个例子,你比如说我们17跟这个,诶37吧,诶这两个呢,你看明明假设我们是两个变量啊,算这个哈希值呢,一个是算出哈希值17,一个是37,看似呢,这两个值是不一样的,但是呢,如果我们曲摸16的话呢,假如这个速度的长度是16,那曲模16呢,它的结果是一。呃,啊,我这个举个33吧,写错了是吧?哎,它的这个余数是一,然后我们这个33呢,取目16呢,这个余数呢,是不是也是一样,哎,相当于它俩呢,就要放在这个数组中的同个位置了啊,那么这种场景怎么处理啊,诶这个呢,我们在像这个哈希map中啊,把它称为呢叫做碰撞,就是明明呢这俩的哈一值不一样,但是他们要放在数组中的同的位置,怎么办呢?我们采用这个叫链接法。啊,这样的方式呢,哎,让他俩呢,都能够存储起来。呃,如果大家呢,你学过Java中的哈奇map呢,我这个讲解呢,大家会非常的清晰啊。嗯,下边呢,我这也举了一个例子啊,这个例子呢,对比的是谁呢?对比的是我们这个哈希结构和我们这个全表变力的这种方式的一个性能的差别。
09:04
诶,那我们创建了一个数组,长度呢是10万啊,这个也是一样啊,是一个10万,那这呢,我是放在哈希set里边了,它底层也是用的哈希的一个算法,对吧?那么我们去呃这个取个time,这个time呢就从零一直到我们,呃呃在这儿是吧?诶从一呢一直到这个范围,我们取这个数度里边呢,一个一个去找,在这样的一个算法当中呢,我们一共花了是823毫秒啊这个代码比较简单,我就不详细的去讲了,那如果说呢,我们同样的这样的一个呃结构是吧,然后也同样的存储了这个10万条数据,我们呢,使用的是哈希set这样的结构,底层呢用的就是哈希算法。他在进行这个从一到10万这个数据一个个去查找的时候呢,只用了五毫秒,大家你会发现呢,它两个相差的一个数量级呢,你看还是很夸张的,这两个呃,时间为代表的呢,实际上呢,是我们的这种算法结构和这种算法结构的一个比较。啊,显然呢,是不是很靠谱啊啊没有问题啊行,那我们就诶说到这儿,呃,然后回到我们上面来讲解啊说既然呢,我们这个哈希结构呢,效率非常高,那为什么索引结构呢,却设置成是一个树形结构呢?啊也是我们所说的B加数呢,为什么你没有用这个哈希结构为代表的这个哈希索引呢?啊这呢,我写了四个原因啊,大家看一看是不是有道理。
10:18
第一个这个哈希,所以呢,它仅能够去判断这种等于不等于和in的这样的场景啊,In呢,其实就等于多个值嘛。诶,就相当于我们这个哈希呢,它主要擅长的是这种等值的一个判断,如果呢,要进行这种范围这个查找呢,他就无能为力了,那你还得实打实的一个个去计算,那就是on级别的一个复杂度了,就没啥优势,诶你要是我们,而我们这个竖形呢,它是一个有序的特点,咱们前面讲这个句促,那你按照这个主见是不是从小到大来排列的呀,而他呢,每次能够砍一半,相当于就是一个呃log个2N这样的一个呃复杂度,那显然呢,这个数呢就更靠谱一些。啊,也就是说那这个还是很重要的啊,也就是说呢,这个哈希这种索引和我们这个树形的这种索引的主要区别就是在这个范围查找上呢,我们的这个数据结构呢,是极具优势的,但是你要在这种等值的这种判断上呢,你的哈希索引呢,诶是有优势的。
11:12
啊,这个我就说清楚了啊,他们的一个使用场景。那么第二点呢,这个哈希所以呢,它有一个缺陷,就是它存储是没有顺序的,那如果说我们想进行这个order的这种这个排序的话呢,那你只能是一个一个的再进行重新排序,那就比如说我们这里边像存储在这个哈信map中,这个数据它是无序的呀,那这个K是无序的,对吧,那你要想按按照K呢来进行排序,那就得一个一个取出来,然后一个个去比较来排序了。啊,就用不上我们这个哈希的优良特性,OK。然后第三点呢,说对于这个联合索引来讲呢,哈希值是将联合索引键合并以后呢,计算出来的,无法对单独的一个键呢或几个索引键呢进行查找,诶能理解吗?你比如说我们前面提到这个联合索引的时候呢,拿着这个C2和C3这两个字段呢,我们建立了一个联合的索引,对吧?诶我们比如说查询这个C24的,这个C3呢,是A的这样的数据,呃,我们用前面这个,呃输赢结构呢,咱们也讲过了,但是你要用这个哈希去计算的时候,它是把这个四跟三呢,呃,合并在一起,算出来一个值。
12:10
啊,这一个值,这一个值呢,你就分辨出来是这样的特征的,对吧,你比如说我们其实得到这个值,底层找到了,呃,一个数哈基值跟它一样,那你能确定它就是四和A吗?它有可能是,呃这个什么呀,可能是这个三和B呢。对吧,那那比如说我们这个呢,小A是代表是97的话呢,就是阿次玛值是吧,这个呢,就是98,那你这俩加一起跟我们这俩加一起呢,是不是这个值是一样的,你就没有办法来判断呢,说这俩还一值一样,比如说还一值一样是吧?哎,它是不是说,呃,原本的你这两个呢,就都是跟原来那个相同的,这个不能确定的,哎,所以这个事儿呢,就不靠谱啊。那第四个点的话呢,说对,即使啊咱们说对于这种等值判断来讲的话呢,它也是有缺陷的,就是我们这个索引力的这个重复值啊,是比较多的啊,这就恶心了,你比如说呢,我们呃有一个列上呢,是叫性别,那性别的话呢,呃无外乎就是男的女的啊这个行,再给你加一个不确定的是吧?呃就这么几个值啊,那导致呢,我们去呃查找的时候呢,你看诶我们大量的男的或者大量的那女的,呃导致的话呢,我们没法法去区分出来这么多重复这个值啊,那这时候呢,是不是呃又出现了,呃以我们上面那个哈西map的特点来讲,是不是又在一个列表当中了。
13:23
那这时候呢,在这个列表中,这个存储的数据也太多了,哎,是不是又类似于像那个on级别的了。所以说呢,我们这个哈希索引呢,它在使用的时候,一定不能够用在这个重复值比较多的这个列上。啊,这个大家要小心一点。好。嗯,OK,然后呢,关于我们这个呢,提到这个哈希索引啊,对应的就是这个哈希算法啊,在哪些引擎当中去支持呢?诶我们看到就是这个memory,在内存级别的这个memory上呢,是支持的啊,印度DB和MY呢都不支持啊。啊,那么具体来讲,这个哈伊索引的一个适用性呢,主要呢,就是看重它对这个,呃,在等值判断这个场景下呢,它的效率是比较高的啊,那么在内存级别呢,我们有一个数据库呢,叫做red啊,是建制类型的,那么red的一个核心呢,就是哈希表。
14:09
啊,对应的就是我们这样的一个呃算法啊,那那另外的话呢,我们提到了咱们memory啊,上一章呢,呃,前面我们提到了这个memory这样的一个存储引擎,它是内存级别的存储引擎,那内存级别可能效率比较高了,那既然呢,你主要呢想体验效率比较高了,那我们呢,在进行等值判断的时候呢,咱们也选择哈希索引啊,就是好加上好是吧,诶好好哈,诶这样的一个情况锦上添花啊,像我们查询这个临时表,我们选择memory,然后呢,我们进行这种等值判断的时候呢,咱们就可以用这个哈希索引啊,那效率呢是杠杠的是吧。OK,这呢就说到这儿,然后的话呢,再提到一个点,这个因诺DB呢,虽然说它不支持哈希索引,但是它呢,提供了一个呢,叫做自适应的哈希索引。哎,这个也算是我们印州DB的一个核心的一个诶功能了啊,叫自适应的哈希索引什么意思啊啊这个大家对这个自适应哈希索引呢,还不太了解,那我们看一看什么情况下呢,会使用自适自适性还是索引呢,说如果某一个数据啊经常的被访问。
15:10
啊,那当满足一定条件的时候呢,比如说你这个次数达到一定情况下是吧,我们就会将这个数据页的地址存放在我们的焊气表当中,当你下次呢,再次查询的时候呢,就可以直接找到这个页面所在这个位置啊让我们这个B加数呢,也具备了哈希索引的优点。能看懂吗?啊,举个例子啊,你比如说呢,我们现在通过这样的一个字段呢,去查找X这样一个数据,我们经常性的拿这个去操作,你要用我们B加数的话呢,怎么办呢?我们就需要呢,先找到这个字段,有可能是一个二级索引,对吧?呃,先找到你对应的这个呃叶子节点,这个叶子节点呢,我们再通过回表的方式呢,是不是找到你这个呃这个居束索引,然后对应的找到我们这个主键的这个值,然后呢,最终呢,翻到你这个数据页上,然后把这个数据呢,加载到我们这个内存当中,对吧?呃,你要经常性的这样去操作的话呢,而且呢,我们可能这个鼻加数呢还挺深,一旦比较深,咱们加载的这个页呢也比较多,Lo次数呢就会比较多。
16:06
啊,那中间这个过程呢,还省不掉啊,当然你又经常用,那怎么办呢?我们就把这个数据页的这个地址啊,咱就保存在这个诶自适应哈希的这个表当中,当你下次呢,只要是查这个X的时候呢,我们就算下哈希值,那在这里边发现找到了,找到以后呢,我们直接呢,就定位它这个数据就过来了,相当于原来这块呢,我们要经过好几步,现在的话呢,是不是只需要呢这样的一步就过来了。啊,就可以是吧,哎,那这个性能呢,显然是达到一个很高很好的一个提升啊这样的一个效果。行,那我们这里边儿呢,提到了这个自适应哈希索引啊,它呢对应的一个变量啊,那默认情况下呢,其实也是一个开启状态的啊,你比如我们在这个诶8.0这个环境当中,我们粘过来啊一回车哎,大家会看到它是一个on的状态是吧。啊,这个呢,属于我们DB中的一个优化啊,一个优化。行,那么这样的话呢,我们就把这个哈希这个结构的特点呢,咱们就说清楚了,需要大家最终记住的就是这个哈希索引呢,它对于等值判断的效果是比较好的,是memory的一个默认的一个引擎。
17:09
好,那我们在说完这个哈希结构之后呢,我们再来看一看这个二叉树为代表的这个树形结构,我们在谈到这个哈希结构的时候呢,这块提到说如何呢去加速查找的一个速度,那对应的数据结构呢,主要有两类,一类呢就是数形结构,一类呢就属于我们讲的这个哈希结构,呃,哈希结构呢,我们提到它的复杂度呢,是OE啊,对于等值的查找呢,效率确实比较高,但是对于范围查轴呢,它就不理想了,那这块我们来看一看这个树形结构,那树形结构当中呢,我们,呃,这个典型的讲到的这个结构呢,就属于一个二叉树的结构,那二叉树里边呢,我们首先引入的叫二叉搜索树啊,就是相当于我们这个树呢,它是具备一定的特征的。啊,那就是我们这个节点的这个子节点呢,这个左子节点呢,是比我们本节点呢要小的,那么右子节点呢,是比我们这个本节点呢要大的,哎,是这样的一个特征。好,那我们在查找的时候呢,诶就可以根据我们这样的一个二叉搜索数呢进行查找,比如说呢,我们要找到这个数据呢,是91啊,那我们要是一个线性查找呢,显然这个效率呢就比较低了,那如果我们要是一个这种二叉树的一个呃方式查找,我们先跟34去比,比它大,我们就从右质上去找比九,呃89还大,我们就诶再往下去找,就找到91了,你要是92的话呢,诶找到这块呢,下边没有子节点了,相当就没有找到,总共的话呢,我们相当于就比了三次对吧?那这三次的话呢,我们可以理解成就是把这三个数据呢,从磁盘当中加载到内存当中,就进行了三次这个IOOK啊,那么我们这个复杂度的话呢,就是诶称作呢叫这个a log以二为底呢,还N的这个对数,OK,这是我们这样的一个情况,这呢叫二叉搜索数,那么这个二叉搜索数呢,它可能有一种比较极端的场景,那就是我们在一开始呢,有这个五的数据的情况下呢,呃,接着这个值呢,依次都比前一个这个值呢要大,所以呢,我们这时候呢,相当于就退化成了是一个是不是线性的一个情况呀,啊相当于。
18:58
就是一个链表了,对吧,那么此时的话呢,如果我们再去找,再去找这个91的,相当于每个元素呢,都需要呢,变一变,最后的复杂度呢,我们就退化成了这个on级别的,那这个就不太理想了啊,那相当于每一个元素呢,我们都需要呢,加载到内存当中进行的这个IO次数呢就比较多。
19:16
那怎么办呢?我们就希望呢,能够在这个二叉搜索的基础上呢,来控制它的一个深度,对吧,那我们就引入了一个叫AV书称为呢叫平衡二叉搜索数,也可以叫做呢二叉平衡搜索数啊,OK都可以啊,那么你要叫AV l的话呢,就更简单一些啊,就比较短是吧。好,那么它是什么样的特征呢?说要么呢,它是是一棵空树,诶或者呢,就是它的这个左右两个子数的这个高度差呢,绝对值不能超过一,并且呢,左右两个指数呢,也是一颗平衡的二叉树。啊,那这里边儿呢,我们就会出现这样的一个特征,就像咱们这儿呢,是不是就绝对的这个偏了啊,只在这个右子节点上呢,是有元素的,左边呢是没有,那这个高度差的话呢,你看是很夸张的,对吧,那我们要求这个是一个平衡的特征,就是左右呢最多只差一层。
20:03
啊,那这里边呢,我们就列举出来一个,诶平衡二叉树啊,平衡叉树这呢,它的左右两边,左右两端这个诶相当于深度呢,都是一样子的。那么在我们这张图当中呢,一共是有多少个元素呢?哎,大家可以数一下啊,这样加一下,一加二加四加八加16,哎,加一起的话呢,我们是一共有31个元素。对吧,诶31个元素好,那么我们要是在这种场景下呢,去找某个元素的话呢,最多咱们是不是需要一层两层三层四层五层就可以了啊,那就意味着我们最多呢,是不是需要进行五次IO操作呢,就OK了啊那显然的话呢,就还还不错是吧,比上面这个呢要靠谱一些。啊,那么我们接下来就想说,我能不能呢,再去降低咱们这个呃,IO的一个次数啊,同样呢,还是31个节点,那怎么能就能够减少我们这个次数呢?实际上呢,就尽量的让我们这个数呢,是不是就胖一些啊,扁平一些就可以了,怎么办呀,我们这叫二叉树,咱们可以考虑呢,是不是把它变成叫M叉树啊。
21:02
对吧,那就可以了,比如说呢,我们同样的还是31个节点,咱们呢,诶把它变成一个三叉数以后呢,我们就变成了几层啊四层结构,那既然是四层结构呢,咱们最多呢,是不是就只需要呢,进行四次IO操作就可以了,减少了一次。啊,相较于我们这个二叉树来讲,咱们这个三叉树呢,就比二叉树呢要更靠谱一些,那进而的话呢,我们就要考虑说尽量呢,我们这个叉呢,是不是就越多就越好一些呀,那么这个结论呢,大家记住它。啊说M叉树的这个高度呢,会远小于二叉数这个数据的这个高度,这个M呢是大于二的,我们呃再说一遍啊,让这个数呢,它越矮胖啊越好啊,因为越矮胖呢,就意味我们这个层数呢就越少是吧,每增加每每多一层,相当于我们就多一层IO,那这个层数越少呢,我们IO的次数呢也就越小。好,那么在这个基础之上呢,我们就引入了一个叫诶B数B数,这个B数里边呢,它涉及到这个叉呢,就会更多一些,好这块来看的话呢,呃,咱们看这张图啊,这张图里边呢,你看这个差最多呢,其实是三个对吧,那我们可以把这个呢,就理解成是一个三叉数了。
22:10
三叉树啊,多路平衡查找树,这个简称的话呢,叫balance tree,那我们简称叫btra,注意这个betra呢,跟咱们前面讲的这个B加树啊,还是不一样的啊,还是不一样的啊,怎么叫不一样呢?大家来看我们呢,现在呢,其实是有这个三叉对吧?哎。注意看哈,我们这个磁盘块一当中啊,我这放的这个数据呢,叫十七三十五,大家可以理解成就是我们比如说主键啊C1这个字段的这个值啊,十七三十五,然后我们这个诶左子数这里边呢,你发现这个值呢,都是比这个17要小的,那比如说82啊没问题,然后呢,这个诶中间这块呢,对应的就是17和35之间的这样的这个数据啊,26和30,然最右边这块呢,就是比35大的这个情况呢,我们就摆放在这个边了啊这边了,然后下边呢,也同样的道理啊,82呢,我们就利于这两个值是不是分成三部分啊,那比八小的,八和12之间的和比12呢要大的,那这里边的P1P2P3呢,就是记住我们下边这样的一个节点的一个地址,诶这样的一个场景。
23:11
诶这就OK了是吧?哎,那这呢就是我们可以称为呢,呃,这个如果说我们一个节点呢,最多呢可以有M和节点,我们就称呢是M这个B数的一个阶,那咱们这呢,相当于是不是就是阶数呢,是三呀,哎是没有问题的行,那这里边我们看到一个情况呢,就是这个位置呢,其实存放呢,我们这呢叫个主键了,实际上呢,你看我们下边这块,相较于咱们前面这个B加数呢,大家能够明显看到一个区别,就是我们这个八的话呢,在咱们这个叶子节点中,它是不存在的。对吧,呃,它就是存在我们这个节点当中的啊,所以说呢,如果我们用整个这个结构来存储一个表的话呢,是不是就意味着我们,呃,这个主键值是八的这个位置呢,需要把这一条记录的完整的,呃数据信息是不是都得放在这儿了,哎,这个呢,是跟我们这个B加数呢是不一样的。啊是不一样的,那么在这个数形结构当中,比如说呢,我们要是找这个嗯九吧,是吧,找九的这样的一个值啊,那首先的话呢,我们会先到这个根节点这块九呢,发现比17要小,是不是我们就诶推入到这儿了,然后呢,这个九呢,是在八和12之间呢,我们是就找到这儿了,然后接下来呢,我们就找到九了,那这时候我们就一层两层是不是三层就找到了,诶那就相当于我们只需要呢加载是不是一个两个三个,哎这个相应的这个结构就行,三次L啊还可以。
24:27
啊,这呢,就是我们所说的这叫哎B,哎B数啊叫这个B竖。好,那这块呢,关于这个B数的一个小结,说B数呢,在插入和删除节点的时候呢,如果导致这个数呢不平衡了,它会自动的做一个调整,诶达到一个自平衡的效果啊,B呢就是balance,所以呢,它也是一个平衡的一个啊二尔塔树啊,那这是一个,第二呢,说这个关键字集合分布在整棵树当中,即叶子节点和非叶节点当中,都来存放数据啊,这个我刚才说的就是这样个特点啊,八呢不在这里边,跟咱们B加数不一样,所以这个位置呢,它是要放数据的啊,再换一个层面来讲的话呢,大家你看过这个图。
25:04
这呢,也是一个别墅。啊,跟咱们上面其实是一样的道理哈,这个26和35就分成了比26小的,26和三五之间的和这个,呃,35比它大的啊,这个等于26的话呢,也是在这个位置,然后下边也同样道理啊,再去做区分就可以了,呃,那么我们想说的事儿是什么呢?就是咱们这个。说这吧,哎,咱们这个八呢,呃,在下边这块呢,是比八小的啊三跟五,哎这个比八大的比12小的是在这个位置,那八呢,本身也是一条记录,那这个比如说这个C1就是八,那么你C1这条记录呢,放在哪儿呢?这个数据就放在我们这个位置上。所以这个图呢,相较于咱们B加数呢,一个典型的区别呢,就是在这种非叶子节点上,它本身也是要存放我们表中的一行一行的记录的啊,这个大家要注意一下。啊,这是我们说的这样一个特点啊,这呢就是我们区分这个B数和B加数的一个主要的一个区别,好,下边我们来再来看一下这个B加数啊,前面虽然我们已经讲了啊,咱们再来说一下这个B加数呢,也是一个叫多路的搜索数,是基于我们这个B数呢做了一个改进,所以我们加了一个这个加号啊,叫做plus啊,就跟那个苹果发布手机一样啊六啊6PLUS啊,Plus就是一个改进版本啊,高级版本。
26:19
那么我们说这个B加速的话呢,更适合文件索引的系统,这个呢,是MY官网的一个描述啊,我就把这个呢加到这儿了,你看最后呢,这一块提到了说呢,诶我们这个不把它称为这个叫B竖了,它这是一个传统的B竖,诶我们呢,在银州DB当中,通常呢把它也称为呢叫B加竖,诶注意这里边这个短横线呢它呃这个短横线呢,它不是一个减号的意思啊,就是一个呃符号是吧,呃杠这样的一个特征,然后呢,B加数的话呢,我们就诶表示呢是它的一个迭代。呃,在这个官网当中呢,其实提到这种B加树的地方啊,一般呢,咱们指的其实就是呃,提到这个B树的地方啊,其实咱们指的一般都是这个B加树啊,这个大家注意一下。好,那下面呢,提到这个B数和B加数的一个差异啊,你比如说我们对于这个B加数来讲啊,这块一说的话呢,大家可能有点懵哎,为了方便起先生,咱们把前面这个呢图呢可以截一个,哎,我们说了这呢,可以作为咱们理解这个呃,B加数的一个典型的结构啊,就是它好这个呢是我们说的一个句数,所以对吧。
27:18
啊,那么接着呢,咱们再回到这块啊,这个B树啊,B数的话呢,咱们就拿这个呢,作为一个典型的代表。我把这呢也截一下。来放大这个,哎,这边。好,一个呢是B数,一个呢是这个B加数啊,我们左边这B加数,然后大家呢,来看一看他们二者的一个区别,这个B加数的话呢,我们说要有K和孩子,有K个孩子的节点呢,就是K个关键字啊,你就比如说我们这个,咱们这块呢,是不是有四个关键字,那我们这块呢,是不是就四个孩子啊,而我们这个里边呢,你要是呃有三个孩子的话呢,实际上呢,他这个关键字呢,是不是只有两个呀?哎,就我们这里边八和12,哎,所以呢,他存在的关系呢,就是孩子的数量等于关键字的数量加一,而我们这个呢,就是正好是一个等的一个关系,四呢等于这个四,对吧。
28:07
接着说,这个非叶子节点的这个关键字也会同时存在我们的叶子节点当中。啊,就是这个意思,呃,我们这个呢,是不是叫叶子节点啊,然后这个叶子节点中,我们这个呢,是不是叫一这样的一个关键字,你看它是不是还存在着,我们这个非叶子节点中,就这个一呢,就在这儿,然后这个五呢,哎,是叶子节点中呢,它也在我们这儿,而咱们这呢,就不是这样子的,这个呢是我们的非叶子节点啊,然后这个呢,叶子节点中你看是不包含的啊,有同学可能会说,老师你这块呢有26,你这怎么还有16呢?这是两个不同的26的数据啊,就是相当于我们这恰好是有这个,呃,值呢,都是26啊,这样两条数据而已。啊,那我们这个数据呢,在B数当中,一旦出现在这儿了,那它就不会再出现在我们这个子节点当中啊,这是它的一个特征。好,那就意味着我们这个,呃,B加数的话呢,它只有这个叶子节点我们才存储数据,其他的位置呢,是不存数据的,而我们这个B数的话呢,不是这样子的,它除了叶子节点存数据之外呢,非叶子节点是不是也存储数据啊,哎,这就是一个典型的区别。
29:07
好,那么所有的这个关键字呢,都在这个叶子节点中出现,然后叶子节点构成一个有序的链表啊,而且呢,叶子节点中按照本身关键字呢,从小到大这种顺序呢,我们进行的排列,哎,就是直接呢,我们要想看数据的话呢,直接呢我们看最下边这块从小到大这个顺序呢,就是排列的,而我们要看这的话呢,不行,为什么呢?哎,你要光看这块数据的话呢,虽然也是从小到大,但是呢,我们是不是丢了一些数据啊,诶,因为在三跟五之间呢,是不是还有八这条数据啊。诶,然后呢,还有12这条数据呢,诶,但是12之间呢,是不是还有这个九跟十这条数据啊,也就是呢,如果我们诶在这个B加数当中,你想把这个表中的数据呢,进行一个排序呢,直接是不是找最后这块直接找就行,因为数据全在子节点上对吧,叶子节点上啊,而我们要是通过我们这个B数呢,去便利一下这里边从小到大的顺序呢,是不是你要进行这种中序的遍历是吧,才能够找到这样所有的这个数据才行。啊,就要更麻烦一些啊。
30:02
好,这呢,就是我们说到他们二者的一个区别啊,下边又举了一个,这还是个必加数的例子啊,就不多说了。哎,那么下边说。说这个B加数呢,跟我们这个B数相比啊,呃,说这个B加数的这个中间节点呢,是不直接来存储数据的,呃,我们说这种结构设计呢,它有什么好处呢?为什么说我们这个B加数是对于B数的一个改进呢?啊,这里边我们罗列出来的这样的几个特征啊,大家看呢,是不是有道理?首先的话呢,我们说这个B加数啊,它的查询效率呢,是更稳定的,更稳定是什么意思呢?诶你比如说我们这个图当中,诶,我们不管是查询,比如说12这条记录。还是查询这个209这条记录,咱们是不是一定要经过这三次查找才可以。因为呢,我们的数据呢,是不是都只在这个叶子节点上,对吧,所以我们一定是需要三次的,当然比如我们要查询26这条记录呢,你会发现呢,我们,诶找到这儿就找到了,哎,当然呢,有相同的我们还要找到这儿,当然你要找这28呢,我们是不是就需要呢,找到这个三层就到这儿了,我要找35呢,是不是找到这块就结束了。
31:03
呃,G呢,就是由于我们这个非叶子节点上它也存数据,所以有的时候我们这个查找的数据呢,恰好就在这个非叶子节点上,甚至夸张点说呢,就在我们这个根节点上,你都不用再去找我们这个叶子节点了啊,进而的话呢,相当于他这个查找呢,每次就不稳定,可能一次,可能两次,可能三次,而我们这儿呢,是不是一定是三次的啊,就比较稳定一些。啊,这个呢,还谈不上说是一个特别明显的好处吧,而这个呢,是一定是明显的好处,我们说下这个B加处的查询效率呢会更高,你凭啥说效率更高呢?那一定是因为我们是不是IO的次数会更少啊啊那这个怎么去理解呢?诶我们说呀,在这个磁盘空间啊,都一样的这个场景下,大家你看啊,咱们这个呃,目录页的话呢,它只存放咱们这针对这个主键索引的话呢。这个我们这儿呢,是不是只存放我们这个主键,还有你这个页的这个页号就可以了啊,它不存储我们这个表中的完整的这一条记录啊,完整这条记录呢,我们能够想象这个字段要比较多的话呢,它占据的空间是不是显然比我们这俩加起的空间要大一些啊。
32:06
好,那你看我们这个B数呢,它这个非页的节点呢,它是不是也要存放数据啊,那有可能这个字段很多,那么大家想象一下,如果我们这个页的大小呢,默认就是16KB的情况下,在总量一定的情况下呢,我说呃,存放我们用B加数的话呢,我存放这个目录项是不是就可以更多呀,因为它只存储了这两项,而你这里边呢,是不是还要存储好多这个字段的一个数据,它存储的项就少。啊,它存储的像少的话呢,你对应的这个差呢,是不是就少,我这个差呢,是不是就会多一些啊,那进而的话呢,我们这个呢,是不是就更矮胖一些啊。还记得我们刚才上面说的那个事儿吗?哎,我说大家你记一下,就是我们这个M叉,这个叉呢,是不是越多,对应的我们这个呢,是不是就越矮胖呀,那显然我们这个B加数呢,它的差就越多,所以呢它就更矮胖,那我们这儿呢,进行IO的次数呢,就会更少一些。所以它的效率呢就会更高,OK,然后还有一个呢,我们说呢,在这个范围这个查找上,我们说B数B加数的这个效率呢,也比这个B数呢要高啊,怎么讲呢,就是我刚才说到的,咱们所有的数据呢,因为都在这个叶子节点上,呃,所以呢,我们要比如说找比五这个大的,是不是直接我们就往右边这块走啊就可以了,这就都是比它大的,而我们要找这块呢,比如说比武大的,你是不是还得去上边这块去找,上面这块去找,因为呢,我们在这个非页的节点上也会存储这个数据,所以这个查找的效率呢,它就会差很多。
33:28
啊,就会差很多,它这相当于是一个呃,这个数的一个便利的方式了,跟我们这个链表的便利方式相比,这个呢,显然是要更快一些的。OK啊行,那这样的话呢,我们通过一个对比证明我们这个B加数呢,确实呢,是不是就要更靠谱一些啊啊OK啊。然后下边这块呢,我罗列出来了几个这个问题啊,有一些点呢,其实咱们前面已经讲过了啊,如果呢,面试当中问到这个点问题了啊,大家你看看自己是不是会应答啊,第一个呢,说为了减少IO,我们索引数呢,一次性会加载到内存中吧,啊首先明确的这个其实咱们前面讲过了是吧,这个索引的话呢,它可能比较大啊,数据量比较大的时候呢,这个索引也比较大,然后我们把索引呢,都存储在这个磁盘上啊,放在内存中呢,一次性都放不太靠谱是吧?所以呢,我们都不会一次性去加载的。
34:14
啊,正因为不会一次性加载,所以我们,诶这个看加载这个的时候呢,尽量呢,你看这个L呢要少一点,那最终呢,我们选择这个B加数是吧,就是很好的就引入了我们这个B加数啊下一个说毕加数的这个存储能力如何啊,为何说一般查找这个行记录的话呢,最多只需要一到三次,这个司马欧诶这个呢,其实是比较高大上的一个问题。啊,要想把这个问题说清楚呢,实际上呢,你就需要对这个B数这个结构呢,是比较清晰的,哎,我要是面试官的话呢,我就爱问这个问题啊,就看一下这个应聘者呢,是不是足够清晰啊。那前面呢,其实咱们也举过这个例子了啊,这块呢,我再说一下啊,前面在哪举还记得吗。啊,这个我把这个往这儿放一下,咱们在前边讲这个B加数的时候。嗯,在这找一下。
35:00
哎,是不是我在这块呢,就说明这个问题了啊,就在这说的来我们再看,再回到这个,咱最后这块呢,讲解一下。哎,开始画反了是吧,那这样啊好那么嗯在这儿啊说为什么说我们一般的这个查找这个行记录的时候呢,只需要一到三次这个48L就可以了呢,那这块呢,我们可以举具体例子,比如说呢,我们主键呢,对应的int呢是四个字节,B in是八个字节,指针类型呢是四个或八个,那一个页的话呢,诶我们大概存储这块呢,我们就按16KB呢来呃标准的去说啊八加八啊一除呢,就是咱就按这个1000来算了,就1000个对吧,那就相当于呢,我们这个,呃,咱就说这个目录页吧,哎说这个叫咱这说的是。存储引擎的页的大小,主键它行,那我们就以这个目录页来说,对吧,因为目录页当中呢,它存储的一个是主键值,一个呢,是不是我们这个叫这个地址值是吧?所以我们就以这个八加八来说,相当于我们这个,诶目录页这块呢,我们能够呃一个页呢,能够存储1000个,哎,我们这样的一个项,那这1000个的话呢,我们再往下分的话呢,是不是就对应到这儿了,那假设的话呢,我们是有三层,那就是这是一层,这两层,这第二层,第三层呢,就是存储我们真实的这个表中的记录了,那假设这个表中的记录呢,咱们假设啊,也存储一个月呢,有1000条记录,那是不是就十的三次方啊,乘以十的三次方,再乘以十的三次方,是不是就11条记录啊?
36:24
那么我们说11条记录呢,已经相当多了啊,基本上能够满足我们日常的需求,那这呢,是不是就深度呢,是为三是吧,诶深度为三,那么我们也有可能呢,不可能,呃也有可能就是每个节点呢,每个这个数据呢,不可能都把这个数据填满了啊,那我们这个高度呢,咱就再加一下,有可能就是二到四层。啊,有可能是二到四层,就咱们再给它加一层啊,就是二到四层,但是又由于什么呢?咱们前面呢,是不是提到了一个叫做根叶面这个位置呢,万年不动,那既然你这个根页面的位置呢,万年不动,那实际上一开始我们就会把这个根页面呢,就直接呢,就加载到这个内存当中了,或者呢,它就是常驻内存的,那我们在这个二到四层的基础上呢,是不是再减个一,那是不是就是一到三次磁盘的一个IO操作就可以了。
37:09
哎,就是这样的一个道理,诶我们解释的话呢,大家不能解释到这儿啊,你说这个11条就够了,所以是一到三层,这个呢,还差点意思啊,你应该呢,再说一下这个可能填不满,所以呢是二到四层啊,然后呢,我们再减去一个这个根节点长度的这个啊,又回归到一到三层,诶这个才是比较完美的一个,呃,解决方案啊,OK。好,下一个说为什么说这个B加数呢,比B数更适合我们这个文件系统的这个检索啊,其实我已经讲过了,一个是稳定性,一个呢是我们这个读写的效率呢会更高一些,因为它更矮胖对吧,那就过了,下面呢,说这个哈希索引和这个B加数这个索引它的一个区别啊,咱们前面已经讲过这个问题了,他呢不适合这种范围查找是吧?然后呢,诶不支持这个联合索引中的最左侧的原则啊,这个呢,咱们在讲到后边优化的时候呢,会提。啊,说白了,我们上面也提到了,就这个哈希呢,我们在计算的时候呢,假设你是一个联合索引啊,就像我们前面说的这个C2和C3这两个字段呢,合在一起构成了一个呃联合索引,那我们哈希呢,就把这俩给合成一起去做计算了,而我们呢,呃这个这个时候呢,你实际上是不靠谱的啊,而我们要是把这个呢,呃利用这个呃这个所以呢方式呢,我们进行一个就是B加速的这种方式呢,去使用的话呢,实际上我们就可以先找这个C2,然后再去找那个C3,看有没有对应的,如果有呢,就找到了,没有呢,那就没有。
38:27
诶我们呢,是可以支持这种左侧原则的啊,左最左侧原则的啊,这个呢,先泛泛这样一讲啊,诶主要原因呢,就是因为呢,我们哈希呢,不管三七二十一,把它们合在合并在一起就算了一个值,而我们这个呃,联合索引的话呢,我们是先考虑C2,再考虑C3啊是可以分开来进行考虑的。啊,递进关系啊,然后下边的话呢,关于这个奥啊,咱们前面也说到了对吧,排序呢,它不靠谱啊,同时的话呢,这个哈希索引呢,它不适合我们的模糊查找。啊,以ABC开头的啊,他搞不定啊,而我们这个B加数的话呢,是OK的。
39:00
啊,咱们的印度DB呢,也不支持这个哈希,所以啊。下面呢,说这个哈希索引与毕加索引在建表的时候呢,需要手动的去指定吗?哎,这个呢,首先要明确一下,像我们官方当中提到的DB和MY呢,它根本就不支持这个,呃,哈希索引。啊,这个memory啊,我们这个NDB,他们是支持这个哈希索引的。但是呢,还有一个点就是咱们这个诺DB的话呢,呃,它是不是还引入了一个我们称为呢,是不是是不是叫这个自适应这个诶哈西呀。哎,这个是我们这印度DB的一个特征是吧,这个自身的韩信呢,不需要我们手动的去指定了,而且呢,咱们默认情况下呢,它也是一个开开着的一个状态是吧。哎,它会自动的,诶给我们做一个这个,呃,这个操作了啊,OK,然后最后这块呢,提到一个R数啊,这呢大家做一个了解就行,咱们再讲上边的时候呢,是不是提到过我们这样的一种空间的数据类型,对吧?针对这种空间数据类型的话呢,我们就可以在它上面呢,是使用这个R处啊,建立一个R的一个索印。
40:00
啊,这个呢,呃,就涉及到比如我们在地图上呢,去找某一个坐标位置,周围的这个餐厅都有哪些,那我们要用传统的方式去做的话呢,这个性能呢,实在是太差了啊,那我们就用这个R术啊,主要来解决这种高维度空间的一个搜索检索的问题。啊,这就可以了啊,这个呢,诶在我们这个MY和这个in DB当中,哎,他还是都是支持的是吧?哎,这个memory当中是不支持的。呃,最后这个小结的话呢,呃,这个大家了解一下就行,就是我们呃使用,所以呢,主要目的呢,就是为了从海量的数据当中,是不是快速找到我们想要的这个数据啊,性能要高一些对吧?诶当然这块呢,我们主要关注的就是这个IO的这个次数啊,还有这个次数,诶最终的结论的话呢,就是这个B加数需要大家呢重点掌握啊,那除了这个B加数之外呢,在面试当中常还问到的就是这个B加数和B数的一个区别,以及呢,我们这个B加数呢和这个哈希啊索引。啊,这个呢,我们叫B加数的这个B数的一个,所以是吧?哎,它们的一个区别是什么?哎这块呢,大家要清楚啊,如果给你一个图,你能不能哎把这个图当中分辨出来,它是一个B数还是个B加数,还是说呢,都不是写错了是吧?哎这个能力呢,大家需要去用啊,那么基于我们这个B加数这样的一个结构,诶我们后面呢,就可以呢去谈哎什么呀,哎这个索引的一个优化问题。
41:16
好,那这一章呢,我们就说到这儿。
我来说两句