快速查询的秘密武器B+树索引-Part1(无索引如何搜寻、基本索引概念)

进入到这篇之前要先确保大家有一些概念。

大家要知道Innodb各个资料页物理上并没有连在一起,而是透过FIL_PAGE_PREV和FIL_PAGE_NEXT属性串连起来,形成一个双向链结串列。而每个资料页内的纪录会按照主键值从小到大的顺序形成一个单向链结串列,每个资料页都会为储存在它里面的纪录生成一个页目录,在透过主键搜寻某笔纪录的时候可以在页目录中使用二分法快速定位到对应的槽,然後在历遍该槽对应分组中的纪录即可快速找到指定的纪录。

额外补充说明:有些蛙友可能对二分法有点疑惑?就是我们在前文有举一个例子搜寻主键值为6的纪录,我们会拿6去跟中间槽对应的主键值比对大小,找到high为2,low为1,这就是二分法

如果对於我前面内容有一丁点不清楚的,请先去前面复习再来唷

那就进入今日的正题 -- 索引 --
我们先了解没有索引的时候,会是怎麽搜寻资料的。

单一页面搜寻

如果以主键为搜寻条件,我们知道可以透过二分法比对主键值找寻对应的槽,大大的提升搜寻的速度。
但如为非主键的搜寻条件,就只能照最原先做法一笔一笔比对,效率低落。

多页面搜寻

大多数产品表的资料量都非常大,需要相当多资料页来储存。
在没有索引的情况下,我们无法快速的定位到查询纪录所在的页,因此只能从第一页沿着双向链结串列往下找,并在每页一笔一笔去比对资料,执行效率真的非常差呀...

该如何改善呢???
有两个具体步骤:

  1. 我们之所以这样没有效率的一页页搜寻,主因是每个页面并没有按照规律排序。
    对此Innodb工程师制定了一个排序方式。其为让下一个资料页中的所有纪录主键值都大於上一个资料页中的所有纪录主键值(按大小排序)。

所以实际上新增一笔纪录X到资料页B的时候,如果发现此纪录X比上一资料页A的纪录Y还小,则会将资料页A较大的那笔纪录Y移动到资料页B(腾出空间),而较小的纪录X则是新增到资料页A里面去,确保资料页B的所有纪录主键值都大於资料页A。这个动作也叫做页分裂。

透过这样的方式确保符合规律。

  1. 既然我们可以为储存在页内的纪录生成目录快速查询,我们当然也可以为所有的资料页生成目录快速查询呀,而目录内容包含两个部分[资料页所有纪录中最小的主键值(key)及页号(page_no)],我们只要将这些目录项储存在连续物理记忆体上,就可以根据二分法快速找到对应的目录项,再根据目录项找到对应的页面。
    至此,针对资料页编制的简易目录就完成了,这些目录项的别名也就是 索引

之所以称其为简易目录,是因为并不完善,有些问题待解决。
1.Innodb使用页作为管理储存空间的基本单位,因为页与页间并不会都是连在一起的(只是透过next_record的方式串连在一起),所以在一页内最多就是16kb的连续储存空间,当目录项非常多的时候就就容纳不下。

2.再来我们常常需要对资料做新增、删除、修改的动作,如果有个目录A内容只包含一个页面B的索引(只有一笔key跟page_no),当页面B纪录全部删除之後,那这目录A也没有存在的必要了(都没纪录了干嘛浪费时间去页面B)。这时我们删除了目录A,由於目录在物理记忆体上是连续储存的,所以其後的所有目录都要往前挪。可想而知这样牵一发而动全身的方式实在是很没有效率啊。

有监於此,Innodb的工程师思考有没有更好可以灵活管理目录项的方式?
仔细观察可以发现目录项其实跟使用者纪录蛮相似的,只是里面存放的资料不一样,目录项是储存该资料页最小的主键值(key)及页号(page_no),而使用者纪录是储存真实资料。

前面的问题是受限於目录项要储存在连续物理记忆体上,最多就只能16kb。

但如果我们把目录项跟使用者纪录一样存在资料页呢?
当然一页还是最多只能容纳16kb,但我们可以一样画葫芦为其再制作更进阶的目录项[往上再多一阶(层)],并随着资料变多,这个目录的层级可以不断地往上长。

整个资料结构会变成像一个B+树
所有的使用者纪录都是存放在最底层的节点上(称为叶子节点或叶节点)
底层以上都是用来存放目录项纪录的节点(称为非叶子节点或内节点)
其中最上面的那个节点称为根节点。

这样子就不会有目录项过多容纳不下的问题,且也不太会有删除某个目录就一定要将其後所有的目录都挪动的情况(应还是有部分的资料需要调动,但减少了挪动的情况,提升了效能)。

是不是很不错!!!因此就采用了这样的做法。

整个搜寻的流程变成先透过最上层的进阶目录项找到对应的低阶目录项,再透过低阶的目录项找到对应的资料页,最後再去资料页历遍找到指定的纪录。

最後补充说明一下实际上使用者纪录跟目录项纪录的属性差异在那?

  1. 存放的资料不一样
  2. 标头内的record_type属性(目录项纪录为1,普通使用者纪录为0。大家还记得吧?之前有说稍後会再回来看,比较清楚,传送门)
  3. 标头内的min_rec_flag属性也不一样(存放目录项的纪录有可能为1,普通使用者纪录为0)。

目录项纪录跟普通使用者纪录,除了以上三个地方不一样之外就没有差别了。

今日难度开始提高,但还是希望大家耐着性子把它一个个熟悉看懂了,加油!

有任何不清楚的地方随时欢迎提问唷~我会尽我所能回答。
而有任何错误的地方也欢迎提醒我改正唷!


<<:  新新新手阅读 Angular 文件 - Add Services - Day08

>>:  Day 08 CSS <文本属性>

Html表单元素(DAY6)

我们在上一篇文章中介绍了input的text,Password,button,radio,check...

[Day 17]独自一人的全端攻略(前端篇)

挑战目标: MockNative Camp 最近这两年在工作上一直想要有同事可以交流进步,或者是遇到...

DAY 11 『 UIAlertController 』Part2

昨天分享如何从中间弹出、由下而上弹出 UIAlertController 今天会介绍: 显示多个按钮...

Day 02 - 行前说明 — 网页微切版架构 和 UI 元件

作为正式开始的第一篇要来讲的是很基础的网页切版和怎麽去看网页中有哪些元件,会分两部分: 网页微切版...

用 watch 搭配服用 immutable

在 《Clean Architecture》里第 6 章介绍 functional programm...