00:00
好,那接着的话呢,咱们一鼓作气啊,接着来看一看我们这个呃页里边的第三个部分啊,对应的叫做配置directory,还有我们这个叫配headater,好,那重点的话呢,我们来看一下这个叫配置directory,这个颜色的话呢,之所以标示出来,是因为跟我们刚才讲的记录头信息里边这个N-on呢是相关的。啊,咱们还欠一个N-O的一个详详细的一个解释是吧?诶这里边我们要看一下这个叫这个页目录,把它说清楚以后呢,刚才这个字段呢,我们就整清楚了,来这个页目录,为什么需要这个页目录呢?哎,这个咱们前面呢,已经给大家呢解释过了啊,就是呢,我们这个呃表当中啊,比如说咱们就看这儿吧,这里边呢,假设记录了1000条记录单列表嘛,列表的特点呢,就是检索不方便,我们现在要找其中的一条记录,假设已经确定好,它就是在我们这一页当中了啊你要这样顺序去找的话呢,效率很低对吧?哎,这其实就我们所谓的第一种方式呢,就顺序查找啊,性能呢就很差啊,性能很差,那怎么办呢?我们就希望呢,使用一个高效的叫二分法查找,那怎么能够实现这个二分法查找呢?
01:02
我们就通过这个页目录的方式呢去实现,注意这个页目录呢,它并没有怎么着啊,诶同学可能初始的一个想象就是说,诶,就比如说我们这里边有1000条这个记录。啊,1000条这个记录,那是不是说呢,我们把这1000条记录呢,这个主件呢全拿过来,真的有1000个,我们用二分法呢?呃,那这样的话呢,显然这个占用空间呢,有点太大了,是吧,这个成本太高,你像我们这是一个巨速索引,你要不是个居速索引的话呢,我们这里边存储的数据呢,可能量就很大了啊,因为非居速索引,咱们这块呢,是不是只存储了你这个,比如我们按照这个C2这个字段构建的一个索引,真的有C2,是不是也有C1,那它这个呢,是不是存储的这个量呢就很小,那我们这个页呢,就是16KB,那你想想我们这里边是不是存储的数据量就很大了。那很大的情况下呢,你这块又来了个页目录,这个页目录呢,这个呃,我们本身的这个位置除了C2就放了个C1,你这块又把所有的C1又放了一遍,那相当于呢,差不多快又重新建一个我们这个用户记录了啊成本太高是吧?哎,我们这个业务呢,就没有整的这么呃细致了啊,力度没有这么细,那怎么办呢?那我们这样去做。
02:09
这个思想是这样子,然后我们就看实施这个假设呢,我们这里边儿有1000条这个记录,咱们把这1000条记录啊,我就想把它分成诶这个一组一组的,比如说呢,这个四个哎到八个呢一组,那我们呢,只取出这一组当中的一个代表就行,咱们这里边取的代表是谁呢?是这一组当中这个最大的这个。那那么我们把每一个组当中最大这个呢取出来,那每取一个,比如第一个里边我取一个放这儿,然后第二里边再取一个,这个组里边最大的就放这儿,然后每一个的话呢,我们成为一个slot。这个道呢,就是一个槽位的意思,那我们这儿呢,有多少个组是不是这块,你看就有多少个这个槽位吧,那每一个槽位呢,记录出来,记录的就是每一个组中的最大值,然后呢,这块不就从小到大的来排列嘛,现在我们要找的那数据呢,假设确定在这一页了,我们就通过二分法的方式呢,看看是在这里边的哪一个位置啊,二分法来回的去,比如说比它小了我们就从前面找,比它大了我们就从后边找,不断的二分法最终确定的是在哪一个,呃,这个这个元素是不是对应的那个组里边啊,然后你再去那个组里边去找是不是就行了。
03:12
理解我刚才说的这个过程吧,哎,那之所以呢,我们这块呢,呃,这个力度呢,不像我们刚才说的,把每一个这个主键值都取出来,是因为没必要那样的成本太高啊,我们呢是从节省空间的角度啊来考虑的啊,那其实基本上我就把这个核心的思想呢,就给大家呢说清楚了。啊,具体里边呢,有几个小细节我们看一看,那刚才呢,我提到一个点,说我们要把所有的记录呢,是不是分成几个组啊,这些组里边呢,那这些记录里边呢,是包括我们的最小记录和这个最大记录的啊把他们也都算进去了,但是呢,它是不包括已删除的记录的。啊,就像我们刚才这里边讲的时候呢,我们把这个第二条记录给删掉了,那我们这个分组的时候呢,是有哪几个呢?哎,他算一个啊,这个这个这个。还有这个啊,就是没有含着我们第四条记录啊,这个这个第二条记录是吧,就是这样的一个集合。
04:03
好,那么再回过来,那分成组以后的话呢,我们接着来看啊,这个组里边有没有讲究呢?有这个第一组的话呢,就是我们最小记录啊,它自成一组啊,他自己呢就是一组,然后呢,最后一组呢,就是包括了我们这个最大记录所在的组,它呢会有一到八条记录,而我们其他组当中通常会有这个四到八条记录。哎,最后想说,怎么这个呢是四到八至一到八呢,那你可以理解成就我们在分的时候呢,也可能最后呃,这个相当于是从这里边它不断的去分出来四个四个四个这样去分啊,最后有可能分的就不够四个了,那就咱就一到八个了啊这个呃,泛泛的这样一说啊,细节呢,大家不用去纠结那么细了。好,那么主要的咱们的思想呢,就是除了这个第一组之外呢,后边这一组呢,尽量的让他平分啊,尽量的去平分。就每个组呢,尽量一样大,对吧?那么注意看这块儿,每个组中最后一条记录的头部信息中会存储该组中一共有多少条记录,那作为我们这个N-on的这个值啊,这块呢,是不是就弄清楚了,你比如我们刚才提到这个演示这个删除操作的时候,说为什么我们是五改成四呢?就是因为呢,我们在这个里边,咱们呢,这个一开始呢,它还没删的时候,呃,它自成一组,所以它的这个N-O的这个值呢,它就是一对吧,我们这儿呢,1234加上这个呢,是五个,那这五个里边最大的是不是就是我们这个最大记录啊。
05:26
啊,因为你看这个指针不断的往下指,越指越大,最后指到它了,它就是最大的,它是最大的话呢,一共有五个,那是不是这个值就是五,现在你删掉了一个,是不是就五改成四啊,哎,这就清楚了这个指了。哎,是不是现在呢,就确实把这个N呢,就弄清楚了,对吧。好,那么页目录呢,就是来存储每组中最后一个记录的地址偏移量的。按照这个先后顺序呢进行排列啊,我们就要slot了,那你看我这举的这个例子,比如说我这呢有你看是不是一共有五个组啊,没问题吧,哎,五个组好,那我们这一组呢,就一个数据,我这个一呢指的就是N-O的这个值,这呢里边注意这个组里边呢,呃,最后一个元素,它记录的这个四呢,相当于是这个N-O的值,就你这组里边有几个,有四个。
06:11
有四个,然后呢,其他的这个呢,都还是零。没问题是吧,哎,这四个这呢有五个,这都是000啊这块它是不是五个,哎,就是这样一个道理。好,然后呢,我们这个槽这块呢,这个其实是咱们这个页目录了这个槽这块呢,它记录的是你这一组当中的最大的这个元素。哎,注意记录的是这个最大的元素啊,可以了。那接着呢,回归到我们这个配置DEMO这样的例子当中,咱们呢算是有六条记录,我们自己呢,添加了四条,一个最小的,一个最大的,一共就有六条记录嘛,然后这六条记录当中,我们最小的自成为一个呃组,然后剩下这五个呢,成为一个组,然后这个99呢,相当于就是我们最小记录的它的记录的一个这个地址啊,然后这幺二呢,季度就是我们这个最大记录它的一个这个地址了。啊,就是这样的情况。行是吧,哎,能理解啊,这块呢,如果我们把这个呃数值呢换掉啊,如果用这个指针来表示的话呢,就是呃这个槽零指的呢,是我们这个最小的,这个它呢指的是我们这个最大的啊,你像这些图呢,都全是这个咱们自己画的啊,先画出来的这个还是很花这个时间的,那再换一个角度去理解的话呢,那这个呢,大家可能更容易的去这个这个理解就是最小居住自成一组,剩下这五个呢,自成一组。
07:23
诶,然后呢,它指向的是最小的,这个指向是我们这里边的最大记录啊,这你看一看图就明白了是吧,不用我多啰嗦了。好,下个问题,这个页目录中这个分组的个数呢?是如何确定的?啊,就是怎么确定说这个个数啊这块呢,呃,其实已经涉及到了这个核心的一个设计的思想了啊面试呢,也不会问到啊大家呢,其实也只是,哎或者说呢,我啊只是怀着一个好奇心,哎把这个事儿呢,呃,这个研究了一下,呃把这列出来,其实呢,意义不大是吧,诶义不大,因为咱们完全不用涉及到这个层面了,对吧,哎,OK。哎,你要想了解一下的话呢,我这也写出来了,这个为什么最小记录之一,最大记录这个是五,差别这么大呢,首先这一呢,人家确定了最小记录就自成一组,对吧?这个为啥最大是五呢?是因为呢,我们最小记录呢,把它扣掉之后呢,咱们接下来去添加啊添加的话呢,现在你看最小记录呢,它自成一组,然后呢,我们,呃,或者呢,一开始的时候没有我们添加一条记录呢,它自然就是最小的对吧?诶,它是最小记录,然后指向这个。
08:21
加一条记录啊,那这个最大记录呢,其实也是它啊,这个唯一的这条记录呢,指不指向这个最大记录了,真的算是有俩了,然后接下来你再加啊,再加再加,然后这块呢,提到了,只要呢,我们这个记录呢,别超过这个八。啊,别超过这八就行,那相当于我们这时这是一,咱们加了四条记录,那它就是一组,我们这四个呢,加上你加上这最大的,这不是有五个嘛,哎,所以他们就自成一度,然后这块加的过程当中呢,呃,达到这个上限八的时候。但这就除去我们这个最大记录这块,是不是相当于有七个呀?啊相当你加了七条记录了,加上这个最大的一共是八了,你要再加一条记录就变成九了,九的时候呢就不行了,因为咱们这个上限是八,那我们就需要呢,把它做个拆分,你现在不是九嘛,九拆分以后呢,是不是就四加五的方式啊啊,那你就可以把那四个呢先拆出去,然后呢,剩下的那呃五个呃,剩下那四个相对大的加上这个最大的这个构成这个五个。
09:14
呃,就是这样一个场景,然后接着你再去添加,再添加超过九的时候呢,就一般我们加的时候是不是就越来越大呀,那就接着往这里边去加啊,越大的时候呢,你再到九的时候呢,再分出去。哎,就是一直这样去分,所以呢,大家你有可能是不是看到我们刚才看到的这样一个场景。哎,这样一个场景,你看我们这块呢,诶是不是四个四个四个,这呢是五个呀,哎,这五个你看我们再加加加加到九的时候啊,就是要变成九的时候呢,我们是不是又把其中的四个小的再拆出去,然后呢,你剩下这五个在一组,所以呢,你就会看到都是4445是吧?哎,是不是也有可能再会看到4446啊哎这样的场景OK,行这呢就是我们如何去分的啊,那我们这个过程呢,该如何去查找呢?哎,其实刚才我那块已经说到了这样的一个大体的一个场景了。
10:03
诶这呢,就咱们这样的一个图对吧,诶超零这为了方便起见,咱们在这个配置弹幕当中,我这儿又加了一些数据,那一共呢,就是有了这个18条记录,包括咱们最小和最大的那18条记录呢,这块一共分成了就是这样的几个组啊,一个四个四个四个五个。刚才我也讲了是怎么确定的,对吧。然后的话呢,诶,然后的话呢,咱们这块呢,指向他,你看我这个指针画的都没问题啊,这个指向这一组当中的最后一个,哎,下边呢,同样的道理啊,都指向我们每个组中的最大的这个值,作为我们这个页目录当中这个槽位上的这样的一个值啊,哎,这样指过来,然后呢,由于我们这个表中的记录啊,你想想它是非啊,页中的记录啊是非常多的,所以我们这个槽呢,并不像我们现在看到的就这么几个值。啊,这个值的话呢,它呃多一些呢,其实也还好是吧,我们二分法的话,一次性是不是就砍一半了,很快的就折半过来了,OK。行,那么接下来的话呢,就是一个典型的二分法了啊,我们现在要找的记录呢,假设呢,通过这个呃B必加数的这个方式啊,我们从头往下去找,最后呢,确定在某一页了,是不是就到这一页上了,到这页页上的时候呢,我们接下来是不是就跟这个槽里边的啊,这个呢,比如说叫槽零,然后最后呢,假设100,我们是不是就100这个索引加上这个零,然后我们除一个二,是不是就50啊,咱们就跟这个槽位50呢去比看谁大谁小啊,如果说比这个质量要小,那你尽量是不是就从我们从零到诶49这个位置去找,你要比这个50大呢,你是不是就从51到我们这个100这个位置,接着去找这个二分法呢?不用我在这多啰嗦吧?
11:34
OK好,那么最终呢,我们确定,比如说我们这个值呢,就是哎,比我们这个曹三就就算到他这了啊,比例比这个值呢要小。比这要小,已经比前面的要大了,那我们要找的话,是不是就应该在你这个曹三在的这一组里边呢去找了呀。这一组去找的时候呢,注意咱们这个列表呢,是不是小的指向大的对吧,你小的指向大的,嗯,你不能是这块呢,找到它这个最大值,你往前去找,找不了怎么办呀,那我们这块呢,你别忘了咱们这个槽的上一个槽位的这个指向的是这个最大值,这个指针是不是指向我们这儿了。
12:07
哎,现在你可以找它的这个上一个槽位的这个地址的下一个元素,这不就找到我们这个槽参里边这个最小值的嘛,然后按照这个指针,你看看哪个是你想要的,因为这里边元素的个数已经很少了,所以我们此时呢,去查找的效率呢就会很高。对吧,哎就这样,所以你看设计的还是非常这个巧妙的啊,最后呢,我这块呢,把这个过程呢,也罗列在这儿,哎,大家有兴趣的你可以去看一下。好,那么关于这个页目录咱们就说完了,总结一句话,就是为了方便呢,我们在一个具体的页当中啊,去快速的找到我们想要的这条记录,我们呢想用二分法,那如何用呢?我们就使用这个页目录。那么接下来的话呢,我们还称这个呃页里边的最后一个结构啊,这个我们叫呃页面头部这个结构啊,页面头部这个结构呢,它记录了很多这个信息是吧?啊,那这个信息的话呢,咱们就来看一看啊,再来看一看。
13:01
好,比如说第一个呢,叫做配置n DR slos在页目录中槽的一个数量。啊,相当于他还记住我们这个页幕中这个槽的一个数量了,方便我们二分法的时候呢,是不是直接你呃就呃首尾加一起除以二是吧,你能看一下这个中间值是多少,哎,它这块不有记录吗?下一个是叫配置hip top说还未使用的空间的最小地址。啊,也就是说呢,从该地址之后呢,都是free space,当你再加入一个用户记录的时候呢,是不是接着这个往后加就行了,诶从他这个地址往后加啊很方便,然后下一个啊叫配置n hi。说本页当中记录的一个数量。哎,本月当中你到底记录了多少数数量啊,数量的这个记录啊,是包括了最小最大记录和标记为删除的记录了啊,它是这样子的,诶后边我记得你看这个啊,是不是还有他呀。这个呢,是该页当中记录的数量,它不包括最小最大记录和标记为删除的记录了啊,你看有两个字段来表达的。行,然后的话呢,这个叫free,说第一个啊,已经标记为删除的记录的地址,说怎么还记录这个哥们呢,那你别忘了,咱们那会儿我讲这个删除的时候呢,稍微提到过。
14:10
咱们这块呢,比如说把这个第二条删了,我把这个第四条删了,把后边可能还删了好多,然后呢,我们第二条这个删除的记录呢,他的next record就指向你下一个删除的了,下删除了再往下指,再往下指,那你这个头部这块怎么找到它呢?诶这块呢就有办法了,我们呢在这个。诶,我们呢,在这个叫,诶这个配置还在这里边,咱们有一个是不是专门记录你第一个标记为删除的这个地址了。啊,那么这已删除的这个next指向下个删除的,他们就构成一个垃圾列表,那个垃圾列表呢,都是我们可以被重用的这个空间呀,对吧?诶这时候我就知道哪些都是没有用的。啊,非常的细致是吧。下边这个配置GA壁纸啊,已删除的记录占用的字节数。啊,这个不用多说了,就啊last insert说最后插入的记录的一个位置啊,最后插入的记录位置,然后这个配置direction啊啊记录插入的方向,诶这个有点意思哈,记录插入的方向诶你看我这块还专门列出来了,说假如啊,咱们新插入一条记录的主见值比咱们上一条记录的这个主见值呢要大。
15:14
比上一条这个记录的这个主线值大,那我们说这条记录的插入方向呢,就是向右,反之呢就是向左,那我们就用这样的一个啊字段呢,来表示这个插入的方向。啊,你比如说我们现在呢,这个已经有几条记录了是吧?新插入这条记录呢,是在我们上一条记录这个右边,那我们这个表示的方向就向右啊,然后呢,你要在它这个左边,那我们这个表示方向就向左。记住,它干什么呢?啊,这个呢,其实就涉及到了一个点,就是有可能啊我们啊,比如说这个表中呢,已经有一些这个记录数了,我们现在插入这个记录呢,诶比如我们在这儿插入到它,那很有可能我们再去插入的数据呢,也是在这个方向上。啊,你比如说我们现在是这个递增的啊呃,那这块呢,方向就向右了,那下一个我们插入的数据呢,这个值呢,有可能就比它大了一点点啊,它就还是向右的一个方向。
16:02
啊,就很有可能我们接下来插入的数据的方向跟之前那个数据的方向是一样的,便于我们后期呢再快速的去插入,所以专门用这样的一个变量呢,做了一个记录。啊,更夸张的是,你看还有另外的一个下面加了一个N是吧,说它呢表示呢,就是呃,假设啊,连续N次插入同一个方向的这个数据都是一致的,我们还还专门呢用把这个数量还记录下来,专门用这样的一个字段呢,还做了一个记录。比如说我们都是向左插入了,插入了五个,哎这块呢,相当于还记住一个五,那第六个呢,发现方向不一样了,那这个在清零。啊,还挺有意思是吧,挺有意思啊,记录的还是很细致的。啊,行,然后接着我们再往下看,说配置n records2个字节,说该页当中记录的一个数量啊,刚才说过了是吧?啊max这个transaction啊,ID说修改当页中最大的事物ID啊这个咱们还没讲事物啊,先过掉,说配置level,说当前页在B加数中所出的层级啊,咱们说叶子节点呢,就是第零级啊第零层啊接着呢,你看是第几层是吧?啊这个记录的字段信息你看还是很多的啊下边这个呢,我就诶不一个的这样去说了啊就这么几个字段了,诶大家你会发现呢,我们这个设计这个页的这个人呢,也可能是一堆人是吧?哎,还是非常的细致的啊,所以说这个大叫数学家吧,我叫这个计算机科学家是吧?
17:22
哎,这个玩起浪漫来了,你发现看一点不比其他人差啊,极其的细致啊,认真对吧?好,那么至此的话,咱们就算是告一段落了,我们把这个数据页的这个内部结构啊,咱们是不是就说清楚了啊,然后在这个过程当中,咱们还涉及到了一个compare派的这种行格式里边这个记录头的信息。OK,大家呢,消化一下啊,我觉得这个讲的还是比较清楚了啊,大家这块呢,把它弄一弄。
我来说两句