00:00
好,那前面的话呢,我们就实现了一个简单的一个索引的设计方案,然后接下来的话呢,我们在这个方案的基础上呢,继续的进行迭代啊,那首先呢,迭代的我们要考虑的点呢,就是针对的这几个目录项,那我们刚才呢,提到了这几个目录项呢,我们可以假设呢,它在物理磁盘上呢,它是一个连续存放的,那连续存放的话呢,我们就可以考虑由由于呢,他们是依次递增的,我们可以考虑呢,使用二分法的方式,是不是快速定位到我们想要找到的那个目录项,然后进而呢,找到对应的这个数据页的这个位置啊,再去细节的找这个呃数据的这些项,对吧?好,那么我们在实际操作的时候呢,可能会遇到一些障碍,什么意思啊,随着我们这个数据页啊,它呢只有16KB的大小,那我们随着这个数据页呢,越来越多啊,言外之意呢,就是我们表中的记录呢越来越多,那我们呢,就可能会生成很多的这个数据项,那这个数据项越来越多的时候呢,我们在底层呢,使用连续空间要存储的话呢,这个压力呢就会越来越大。啊,这个呢是一点不方便的地方,那另外一个的话呢,就比如说呢,我们这个数据页呢,就后期就不要了啊,就这些数据呢,我们就在删除了,那就意味着我们这个数据项呢,其实就也不要了,那要是不要的话呢,由于我们是连续存储的,那是不是就使得我们后边这个数据项呢,就依次得向前移动啊,那这个呢是成本比较高的,那同时呢,还有可能呢,会出现这个数据的一个插入行为,对吧?比如说我们这个ID呢是十,这个呢是12啊,当然这个比如我们改成是22吧,中间呢就断了很多,那假设呢,我们就添加了一些数据呢,恰好就处在十和22之间啊,假设呢还恰好就是三个对吧,那相当于我们就插入了一个新的这个数据页了啊,这个指量相当就指到这儿了啊,这个指向这了,那我们就需要从这里边呢,是不是取出来最小值再生成一个目录项,而这个目录项呢,就应该是在这个和这个之间了,那我们就意味着现有的这个目录项呢,是不是都得往后移,把这个位置呢给空出来,来放我们这个新的这个数据页对应的这个结果是吧。
01:52
那就相当于呢,想表达的意思就是我们这个目录项呢,如果在底层呢,是连续内存空间存储啊,不是特别靠谱的,那怎么办呢?诶我们就想到了这其中的一项呢,跟我们这里边儿的一条记录啊,其实是类似的,当然记录的东西不太一样,当然呢,整个的原理呢是类似的,不妨呢,我们就让每一个目录项之间呢,也是使用这种单向链表的方式呢,进行连接,让他们达到一个从逻辑上是一个连续的概念就可以了。
02:20
啊,那么这样的话呢,我们实际上呢,就可以给这个目录项的这些项,那也给咱们提供一个页啊,我们可以称为呢,叫目录项这个记录构成的页。哎,目录项这些记录构成的页,那简单的我们就先起个名,比如说这个呢,我们就称为它叫目录页。啊,比如咱们就叫目录页,其实呢,这也叫数据页,只不过呢,为了方便起见啊,咱们就叫目录页了,这个呢,咱们就还叫这个数据页,这个数据页里边呢,呃,就放的是咱们这个表中的一条一条的记录啊这个意思,目录页数据页啊,就是我们呃范范来讲呢,其实都叫数据页啊,只不过这里边我们为了接下来呢描述方便啊,就是把他俩名字呢,我们区分一下。好,那么这样的话呢,咱们是不是就会生成这样的一个情况呀,这个呢就叫做诶目录页,然后这个目录页跟我们这个数据页,我们如何去区分呢?诶这里边我们就提到了这个叫record type了,这个record呢,我们说让他这个值是一的时候,那表示的就是你是目录项。
03:16
你看我们这里边儿这个这几项,其实就我们这里边这几项呗,这四项的话呢,它其实就属于目录项,所以我们这个record type这个值呢,就都是一,它们之间呢,是以这种单向列表的方式呢去连接的,然后最左边这个呢,自然而然它就是最小的,最右边这个呢,自然而而然,自然而然的它就是最大的,整体结构上来讲呢,跟我们这个数据页呢,你看还是比较相似的,对吧,比较相似的,那他们这个不同点是什么呢?就是我们这个目录页啊,和我们这个数页不同点的话呢,就一个呢,是我们说这个record这个不一样,另外的话呢,就我们这里边包含的这个具体的数据啊,啊也是不一样的,对吧?我们这里边存储的就是你这一个数据页里边最小的这个主键值啊,是个一,以及呢,你这个啊,它的页啊,我们叫页码了啊,其实啊,相当于是个低值值,OK,这个呢叫页十,它只记录了我们说这两个数据,对吧。
04:06
啊,而我们这个数据页里边呢,就是记录的是你真实的我们的一条一条的记录啊,这一点的话呢,你看他们是不一样的。好,另外的话呢,还提到一个点,就是我们在这个呃,记录头信息里边啊,一说到记录头信息,这就涉及到我们下一章要讲这个行格式里边的一个内容了,它有一个这样的属性啊,这个属性呢,在我们目录项记录里边,这个值是什么样子的,这个到我们下一章的时候呢,咱们再说这个事儿啊,暂且呢,大家就先诶忽略掉啊,先忽略掉这呢就提到了他们二者的一个不同点啊,这两个事儿,那么相同点是什么呢?就我们这个和这个的相同点是什么呢?这呢,我们还要引出一个内容,这个内容啊叫做配置director。叫做页目录,叫做这个页目录,这个页目录的话呢,咱们也是啊,提到了这个第七章的时候呢,咱们在这个位置,那会讲到我们这个叫页目录,对吧,那叫页目录,咱们现在呢,先泛泛的给大家这样一说,就是对于我们这个目录项记录的这个页跟我们这个真实的这个数据啊,像对应的这个页呢,他们其实都还维护了,维护了一个叫做页目录,这个页目录里边呢,它其实是一个一个的这个槽位啊,也会对我们现有这个呃里边的这个数据呢,它进行一个呃分组啊几个比如四个五个一组,然后呢,记录这里边儿的一个值啊,这个记录一个值啊,所以暂且呢,咱们先不说的那么细了啊呃,那么大家呢,泛泛的理解呢,就是说我们还有一个页目录这样一个概念,就是针对于我们这里边儿的一个数据啊,咱们建了一个目录,这个目录的话呢,从小到大这样去排列的,我们再接着去找数据的时候呢,直接就从页目录里边通过二分法的方式呢去找到啊,你更直接的这个,呃,这个这个下边要找的是哪一条这个子子。
05:45
子子记录是吧,这样的,包括我们这个数据页的也是一样,数据页里边的话呢,我们针对这个数据呢,也会建一个这个页目录,然后呢,我们这个通过二分法呢,去找的时候呢,可以快速的定位,所以这个页目录的这个出现呢,主要目的呢,就是为了让我们能够使用这二分法啊,去提升这个叫查询的速度,否则的话呢,啊怎么着啊,你是不是在这里边儿呢,只能是这样诶,通过前一条找后一条,前一条找后一条,那我们这里呢,假设只有三条在真实的一个数据当中,我们这里边可能存在这个上千条数据,对吧,那我们来查找的话呢,用二分法显然呢,速度会更快一些,这个主要归功于呢,就是我们的页目录。
06:21
这里边儿有,这里边儿也有啊,这块大家如果听着稍微有点迷糊呢,我们讲到下一章的时候呢,哎,再详细的去说一下这个页目录的问题。好,那么此时的话呢,如果我们还是想找这一条记录啊,相当于我们要查找的话呢,是通过C1这个字段呢,找20的这一条数据,那我们首先呢,是不是定位到我们的这个目录页是吧?这个目录页里边呢,我们通过这个页目录的话呢,我们就能够快速的通过二分法呢,找到了它应该呢,处在这个你看12和209之间,是不是就对应的我们这一项呀,然后这一项的话呢,对应的我们这个页码呢,是九,我们就找到了这个位置。然后这个位置里边呢,我们也通过它的这个页目录呢,我们就能够通过二分法快速的找到呢,诶是在这儿呢,然后这呢,我们就找到了这样一条记录啊,速度都非踌,那么此时的话呢,我们跟磁盘IO的次数是多少呢?注意只有两次,那我们把这一页呢,是不是加到这个内存当中,这是呢一次啊,就是我们加载的话,数据页是基本单位了,就是一加载的话呢,我们就整个把这个数据页呢,就完整的加载到我们的内存当中了,所以这呢是加载了一次,然后呢,我们判断完以后呢,是不是接着就把这一页呢再加载过来就可以了,所以我们只需要呢两次就OK了。
07:29
啊,两次就OK行,那这呢,就是我们说的这个迭代的第一次,然后迭代第二次呢,叫多个目录项组成,哎,目录项记录组成的页什么意思啊,随着我们这个下边的这个数据页呢,越来越多,你看我们假设。假设这个目录项列一页呢?咱们只能是放四项。那只能上负放四项,那对应的这块呢,是不是有四个数据页了,假设我们现在呢,又加记录的话呢,你就会多一个数据页了,多一个数据页的话呢,我们这里边儿是不是就要多去记录一项,但是呢,我们最多只能记录四项,那此时就意味着我们是不是要再这个这个创建一个目录页啊。
08:06
来创建目录页,那恰好我这块呢,方便起见,我举了一个数更大的,那这个页呢,正好是在这些数据页的最后边,然后这块呢,也自然而然的是在我们现有的这几个目录项的这个,诶最后边那这块呢,就新开辟了一个目录页,然后来记住我们这个320了。啊,这个应该一看都能明白对吧?好,这个呢,其实比较简单啊,就是想表达的意思就是随着我们数据页的不断增加,我们这个目录项,这个页呢,可能盛不下了,那我们就去再创建新的这个目录页就可以了,彼此之间呢,也是通过这种双向链表的方式呢,来进行一个逻辑上的连接啊呃,我逻辑上呢是一个连续的啊就可以了。好,那么这个时候呢,如果我们还是要查这个C1,这个这个是这个20的,那我们首先呢,是不是需要先判断你是在这个一二三十当中,还是在这个一二三十二当中吗。对吧,那我们这时候呢,是不是你得因为这呢涉及到是两个页了啊,我们就得看一下这个到底应该是在哪个段里边了啊,此时的话呢,这个目录,我们说那个页目录的话呢,它是针对这个和这个的,它们合在一起是没有的。
09:08
啊,那你只能是先从这里边去找,看看是不是在这个范围里啊,那在诶正好就往下走了是吧,那不在这儿,你是不是再去这里边呢,去找一下,看看是不是在这个呃范围里边啊是这样一个思路,行,就是相当于我们这两个页的话呢,你看都还得需要去过一下。当然你要在第一个页里边找到了,你就不用去第二个页里边找了,那么第一个页没找到,那么就得去第二页里边找,你比如我们现在呢想呃,查找的是这个C呢,是比如说呃325吧,那我们先找这一页的时候呢,相当于没找到,那我们再找到这一页,那此时的话呢,我们需要这是不是一四,然后这是一次,然后呢,假设呢,在这里边呢,我们这个呢,相当于是三次L对吧?好,那这呢是我们这个迭代的第二次,诶其实稍微的差一点,那在基于第二次的场景下呢,我们再去啊提到这个迭代的第三次,我们给这个目录项的这个页啊,目录页,目录页给他们俩呢,再去生成一个上层的目录。
10:01
就是对于现有的目录呢,我们再生成一个更高级的一个目录。啊,就是这个意思了。这个场景的出现呢,就可以解决,我们刚才呢,这个IO的次数呢,就可以减少了,来大家看,那针对只要是我们的这个目录项的这个页呢,它多于一个了,你看这时候呢,是不是就有俩,只要是多于这一个的话呢,我就会再生成一个上层的目录项的页。这个目录里边存放的信息的话呢,是什么呢?诶跟我们前面这个呢,其实是类似的一个思路,那我们这里边呢,就是首先呢,记录的是你这个前面这个目录下面这页里边呢,诶这个主见值呢是一,那这个就是一,这个30的话呢,是不是我们这个30啊,诶没问题,然后这个的话呢,我们主见值呢是320,那这个就是320,然后记住我们这个页呢是32啊记住就是32。好,这就可以了,那这样呢,就相当于我们生成了一个新的这样的一个层次结构,那么在这种场景下呢,我们再去查这个,比如说C1是20这样一条记录,我们是不是就从这块出发了,这个时候的话呢,我们一进来,诶此时呢,它会有一个页目录,然后里边呢,你就方便你去用这个二分法了啊,诶当然咱们这个目前呢,这个存储的数据量比较小,真实当中呢,这个可能是几百条上千条,那我们的U化分法呢,效率呢,就会更明显的加快一些,那一比较的话呢,我们发现呢,是不是应该是从这个里边去找啊,因为这个呢,最小是320了,不合适,那我们从这里去找,相当于我们这块呢加载了一次。
11:24
然后呢,再往下这块走的时候呢,我们就走到这一页里了,这一页里边呢,你再通过这个页目录呢,我们诶二分法快速的找到呢,诶说应该是在这一项里边,然后接着呢,去对应这个是不是就找到我们这里边了,然后再往下的话呢,去找这里边那个20的那套记录,这个呢,我们看似的说,诶这不是也是应该是加载了,呃,这叫14L是吧?呃,然后这是一四这个L加点一个页,这呢也是一次L说老师你这不上面那个是三次,这个还是三四吗。那注意咱们这时候举的例子,数据量比较小啊,对吧,数据量比较小,那你想想,如果我们在实际当中呢,这个目录项这页呢,它也可能很多在第二次迭代的时候呢,那你就得一个一个这样去找呢,有可能我们找到最后一个才发现是,那中间呢,你可能就要加载多次啊,就是多次IO了,而我们这个时候呢,呃,你这时候呢,就只需要呢,把我们这个顶层的这一次,然后下边呢再找一个就完事了。
12:12
啊,还是要节省这个IO的次数的。体会一下是这意思吧,好,那么这个结构出来以后呢,那基本上我们要表达的这个必加数啊,其实就是完成了。那其实就完成了,那我们就会生成是不是这样的一个结构啊。啊,这样的一个结构,然后下边这块呢,那这个其实就我们说的叫B加数了啊,那接下来我们把这个B加数呢,给大家去解释一下,这个里边呢,每一个篮框呢,其实就是我们想表达的一个叫数据页。啊,这个数据页的话呢,我们把这个目录页呢,也称为叫数据页了啊,诶每一个节点的话呢,相当于都是一个数据页,那么这个最下边这个呢,我们从数据结构的角度来讲,是不是叫叶子节点啊,那么这个叶子节点呢,就是真实里边存放的是不是都是我们的一条一条的数据啊,诶我们这块呢,是竖着这样放的,这就一条条数据,然后一条条数据之间呢,它们是一个单向链表的方式去连的,而每一个这个叶子节点之间呢,它们都是双向链表的方式去连接的。
13:09
好,那我们把这个呢称为呢,叫第零层,哎,把它们称为第零层,然后再往上的话呢,这个就是第一层,然后再往上第二层,哎,是这样的一个关系。好,这是这个,然后呢,这是叶的节点,那么非叶子节点呢,非叶的节点呢,其实就是我们说目录项构成的这个页了啊,咱们可以称为叫做目录页对吧?哎,这叫目录页,这个呢,是不是叫一个根节点,这也算是一个目录页吧,啊没有问题的,行,这个呢,就我们指明了说这个B加数啊是什么样子的。那大家拿这儿呢,就可以当成一个典型的一个例子啊,典型的一个例子好啊,这块我丢了一个这个指针啊,哎,把这个指针大家补上就可以了,像这呢,是我们说的这个事儿,然后的话呢,诶,我们看一看这个倍加数啊,说这个倍加数里边,比如说有这样的一个说法,说呢,我们这个表里边儿呢,通常大家在实际开发当中啊,会发现这个B加数的这个数啊,都不会特别的高啊,通常呢,不会超过四层,说这个事儿呢,你怎么来解释。
14:04
啊,有同学可能遇到这个问题时候就懵了,说为什么被加数通常不会超过四层呢?诶这里边我们要强调一个点啊,后续呢,结合其他的这个数据结构呢,我们会提到就是这个数的层次呢越低。我们IO的次数呢,就会越少。哎,我这块明显放慢这个速度,我再说一遍。我们这个数的层次呢,就是越低,我们这个时候IO的次数呢就会越少,你比如说我们现在只有三层对吧,那我首先加载的话呢,是不是把这个加载一下,这是一次L,然后从这里边呢选一个啊,因为你是这个二分法的方式呢,是吧?我们会选中一个,比如我们选中它了,这是不是就第二次L啊,然后再从它这里边儿呢,我们再选择一个,这是不是就三次L就可以了。而你要是这个数的话呢,要是这个层次比较深的话呢,那每经过一层是不是就需要加载一个数据页,那层次越多的话呢,那是不是我们加载的这个数据页就越多,那你IO的次数呢,是不是就越多呀?
15:00
那YG呢,就是我们这个树形结构呢,越扁是不是就越好一些。啊,这个先明确一下好,那么为什么说开发当中我们通常见到的这个B加数都不会超过四层呢?来大家你看。咱们上边举的这个例子啊,我说的是这个数据页呢,最多是放三条,而我们这个目录下的这个页呢,最多放四条,在实际开发当中,那肯定不止三条和四条,对吧,咱们默认的这个数据呢,是这个16KB。嗯,这个我写16KB了,没写是吧?啊,咱们默认的这个数据大小呢,它是16KB,那我们呢,放这个数据项,咱们假设呢,这个放数据项呢,一个数据页能放100条记录。啊,你可以拿这个16KB,那咱们假设呢,就是这个吧,除以这个100,那相当于是呢,是不是一条数据呢,我们占这个一百六的这个字节呀,那其实也还可以了,是吧?行,那么我们就是假设一个普通的场景,一个叶子节点啊的数据页呢,放100条用户记录,那么我们存放这个目录项记录的这个节点呢,就相当于是我们这些了扉页的节点,它呢,因为存放的不是真实的数据,字段多,我们这个里边放的这个字段少,所以假设呢,咱们能够放1000条目录像的记录。
16:14
啊,1000条不过分是吧?好,那如果我们这个B加数呢,只有一层,那只有一层,那就意味着我们是不是就只有一个这个呃,纯液的节点了,就是一个数据了,对吧,那你最多的话呢,那不就是我们刚才说的100条记录呗。就没问题是吧,那一次性的我们一次IO就加载它就OK了,这是只有一层,那如果我们说有两层呢,那两层呢,就意味着我们上层的是目录项的这个记录,然后下层的话呢,就是我们这个数据项的这个记录了,好那这时候我们说呢,呃,这个时候呢,它最多呢,是不是放1000条记录,然后对应的下边是不是有1000个这个数据页,一个数据页里边是不是有100条记录,那就是1000乘100,这是多少啊。我这样的打个打个逗号吧。那咱们在中国的话呢,更习惯的是四个一位,咱们打逗号对吧,那这呢,是不是就是10万啊,相当于呢,如果毕加数有两层,我们就能够放10万条数据,好,那如果有三层呢,你想想这是一层,下边这又一层,在下边又一层,好我们这个呢,是目录项的这个,呃,记录的页是不是能放1000个,就因为我们下边是不是有1000个呀,好,这就1000个了,这1000个里边每一个呢,里边是不是又能放1000个,那就相当于是1000,首先呢,乘以1000。
17:24
那那是不是就意味着每一个这里边有有有这么多个这样的小结构了,这个小结构呢,一个呢,是不是对应的一个数据,一个数据呢,是不是有100条记录,是不是我们再乘一个100啊所以呢,就是两个1000加上一个100,那这块是多少呢。我们在这逗号一下。在这等号下,这是不是就这多少一个亿吧。相当于呢,如果我们的B加数呢,有三层的话呢,大家想想此时的话呢,我们就能够存储1亿条记录,那要有四层呢,也就再加上个1000。这是多少?1000亿吧。啊,很夸张了对吧,那相当于我们如果有四层,咱就能从这个1000亿条记录,通常呢,咱们表还不至于这么夸张到这儿的话呢,其实就已经很夸张了,所以说呢,大家就能看到,你看我们这个毕加速这样的一种设计方案呢,我们最多呢,也就有四层,在实际开发场景当中,对吧,那最多有四层是不是就意味着我们最多呢,也就加载四次IO就可以了呀。
18:17
我这块指的是一个精确查找,咱不涉及到范围啊,你要范围查找,有可能说我们这个要这个要,这个也要,那有可能就要加载多次了,咱们精确查找假设找的就是具体的某一条记录了,那咱们相当于最多呢,是不是就四次lo就行,那IO的次数少了。自然而然,我们这时候呢,时间是不是就节省了很多了啊,没有问题,行,那这块呢,通过我这个讲解迭代,大家应该就非常清楚咱们的这个B加数长什么样子了。哎,就是这样的一个特征,好,我们就说到这儿。大家呢,理解一下。
我来说两句