前言
本章节从数据页的具体结构,分析到如何生成索引,如何构成B+树的索引结构。
以及什么是聚簇索引,什么是联合索引
InnoDB数据结构
行数据
我看各种文档中有好多记录数据结构的,但是这些都是看完就忘的东西。在这里详细讲也没有多大用处,无非就是照本宣科而已。所以就不去一点点分析每个行数据中的详细内容,大概说一下每行的大概结构。
- 页是 MySQL 中磁盘和内存交互的基本单位,也是 MySQL 是管理存储空间的基本单位。
- 指定和修改行格式的语法如下:
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称
ALTER TABLE 表名 ROW_FORMAT=行格式名称 - InnoDB 目前定义了4种行格式
COMPACT行格式:
Redundant行格式:
Dynamic和Compressed行格式:
这两种行格式类似于 COMPACT行格式 ,只不过在处理行溢出数据时有点儿分歧,它们不会在记录的真实
数据处存储字符串的前768个字节,而是把所有的字节都存储到其他页面中,只在记录的真实数据处存
储其他页面的地址。
数据页
前面说缓存页的时候,提过数据页的概念,那么这里详细说一下什么是数据页,以及数据页的结构是什么。
数据页,代表这块16kb大小的内存空间。里面存储了每个数据页的固定信息,和行记录数据。
大概就是这些内容,下面慢慢介绍里面每个内容。
如图:
数据记录
数据页中的数据记录,也就是我们上面说的行数据,这些行数据都是存放在User Records这个区域内。
当有数据需要存放的时候,先从Free Space中申请一个对应大小的空间,划分到User Records区域中,然后放入数据。当free space空间用完了,就证明这个数据页已经满了,需要新开一个数据页来继续存储数据。
如图:
这些数据单纯存储在这里肯定不行的,我们还需要管理一下,要不然查询的时候一个个数据页一条条数据去扒拉的话,还要数据页干啥。
首先,这些数据也是由链表方式存放在数据页中,每条数据都有一个指针来指向下一条数据。形成一个单向的链表结构。 并且,这个链表的头部和尾部是两个固定的虚拟节点,虚拟节点是存储在数据页中其他地方的。不在User Records中。
如图:
页目录(Page Directory)
现在已经把数据页中的所有数据记录串联起来了,但是想要查询的时候,好像还是要从头捋一遍,当然也是很耗时的。
那现在我们有了这个链表,也标记了最大数据和最小数据记录。
就可以把这个最大数据记录和最小数据记录单独存储起来,不就有了一个目录的功能么? 既然是目录了,肯定不会单纯的记录最大值和最小值咯。我们看书的时候,不也是分为一个个章节吗,这样能帮助我们更快的检索到数据所在位置。
所以为了制作这个目录, 需要将数据记录分为多个组,第一组肯定是最小数据,并且这个最小数据是单独划分出来一组,其他组的数据最多不能超过8个。然后把每个组中的最后一条记录数据地址进行单独存储。
如图:
查询的时候,就是通过二分法确定数据在哪个槽里面,然后获取到这个分组地址中最小记录数据地址。通过链表的指针捋一遍,查询到数据。
页面头部(Page Header)
有了上面的目录依旧是不够的,还需要得到一个数据页中存储的记录的状态信息,比如本页中已经存储了多少条记录,第一条记录的地址是什么,页目录中存储了多少个槽等等,特意在页中定义了一个叫 Page Header 的部分,它是数据页结构的第二部分,这个部分占用固定的 56 个字节,专门存储各种状态信息,大概内容如下:
文件头部(File Header)
数据页有了基本内容,有了介绍,有了目录。现在要做的就是把这些数据页串联起来,也形成链表的格式。File Header 作为第一个组成部分,它描述了一些针对各种页都通用的一些信息,比方说这个页的编号是多少,它的上一个页、下一个页是谁啦吧啦吧啦~ 这个部分占用固定的 38 个字节,是由下边这些内容组成的:
数据页和B+索引
前面我们大概说了一下数据页的结构,各个数据页可以组成一个 双向链表 ,而每个数据页中的记录会按照主键值从小到大的顺序组成一个 单向链表 ,每个数据页都会为存储在它里边儿的记录生成一个页目录 ,在通过主键查找某条记录的时候可以在 页目录 中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
页和记录的关系示意图如下:
因为这些 16KB 的页在物理存储上可能并不挨着,所以如果想从这么多页中根据主键值快速定位某些记录所在的页,我们需要给它们做个目录,每个页对应一个目录项,每个目录项包括下边两个部分:
页的用户记录中最小的主键值,我们用 key 来表示。
页号,我们用 page_no 表示。
所以我们为上边几个页做好的目录就像这样子:
以 页28 为例,它对应 目录项2 ,这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。我们只需要把几个目录项在物理存储器上连续存储,比如把他们放到一个数组里,就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为 20 的记录,具体查找过程分两步:
先从目录项中根据二分法快速确定出主键值为 20 的记录在 目录项3 中(因为 12 < 20 < 209 ),它对应的页是 页9 。
再根据前边说的在页中查找记录的方式去 页9 中定位具体的记录。
至此,针对数据页做的简易目录就搞定了。不过忘了说了,这个 目录 有一个别名,称为 索引 。
这些目录数据也是同样存在一个数据页中,这时候的数据页就称为目录页。
那当数据页的数据,上了几千几万几百万千万的时候,目录页肯定也不会是单单的几个而已。那么这些目录页也是要以同样的形式,通过前后指针形成数据页一样的链表。
那目录页多了,肯定也是要有查询方法的,所以目录页也会以同样的方式再统计一层目录。
这样一层一层的统计上去,如图。是不是看着有点熟悉? 没错,这就是B+树!
最下面的存放数据的数据页就是叶子节点,其他的目录页就称为非叶子节点或者内节点,最上面的节点也称为根节点
从图中可以看出来,一个 B+ 树的节点其实可以分成好多层,设计 InnoDB 的大叔们为了讨论方便,规定最下边的那层,也就是存放我们用户记录的那层为第 0 层,之后依次往上加。
之前的讨论我们做了一个非常极端的假设:存放用户记录的页最多存放3条记录,存放目录项记录的页最多存放4条记录。其实真实环境中一个页存放的记录数量是非常大的,假设,假设,假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录,所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录,那么:
● 如果 B+ 树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放 100 条记录。
● 如果 B+ 树有2层,最多能存放 1000×100=100000 条记录。
● 如果 B+ 树有3层,最多能存放 1000×1000×100=100000000 条记录。
● 如果 B+ 树有4层,最多能存放 1000×1000×1000×100=100000000000 条记录。哇咔咔~这么多的记录!!!
你的表里能存放 100000000000 条记录么?所以一般情况下,我们用到的 B+ 树都不会超过4层,那我们通过主键值去查找某条记录最多只需要做4个页面内的查找(查找3个目录项页和一个用户记录页),又因为在每个页面内有所谓的 Page Directory (页目录),所以在页面内也可以通过二分法实现快速定位记录,这不是很牛么,哈哈!
聚簇索引
上面说了B+树的构成,而这个B+树本身就是一个索引,有两个特点:
- 所有的记录也都是按照链表的方式排列的,排列方式是按照主键大小的顺序
- 叶子节点存储的就是完整的数据记录
而同时具有这两种特点的B+树就是聚簇索引,也就是说,每个表都会默认创建这个聚簇索引,不需要我们通过语句显式创建。需要注意的是,这个聚簇索引的叶子节点就是所有的数据记录,也就是说数据即索引,索引即数据。
二级索引
上面的聚簇索引只有在通过主键查询的时候才会发挥作用,但是在我们真正使用的时候,并不会全都按照主键来查询。那我们想要通过其他字段中的数据查询的时候该怎么处理?
这时候就可以用其他字段来建立一个新的B+树,不同的B+树使用不同的排序规则。比如我们上面是按照主键id建了一颗树,那这次按照另一个字段再建一颗,如图:
这个图中,黄色依旧是主键,蓝色是我们指定的索引字段。
● 首先是第一层的建立,这里就没有全量的数据了。为了和原本的记录关联,只用了索引字段和数据的主键id。把指定的索引字段按大小排列,如果相同的话再按主键排列。
● 第二层及以上就是通用的逻辑了,记录每页的最小索引值+页号。
当我们按照索引字段查询的时候,依旧是二分法查询。根据索引值的大小一层层的确定数据的页号所在。
最后找到索引+主键id的数据,但是这时候找到的并不是全量的数据记录。如果我们需要获取其他字段的数据,就需要拿着这些主键id,到聚簇索引中再次查询数据的全量字段,而这个动作就叫做回表查询。
为什么需要再次进行回表操作,直接吧数据存在这个索引中不好吗? 那样的话,就要把我们所有的数据存储两边了。而且,如果每新建一个索引,就把数据再复制一遍吗?那多大的内存也不够用啊。所以当通过这种其他字段建立的索引树进行查询的时候,还需要再次到聚簇索引进行一次回表操作才可以获取全量的数据记录。所以这种索引记录就称为二级索引,也可以称为辅助索引。
也就是说,只要是非主键建立的索引,全都是二级索引。
注意的一点,如果我们这个二级索引查询的时候,如果因为相同的数据太多,获取太多的记录页的话,就会导致获取到大量的主键id。然后拿着一批主键id再进行回表肯定会影响效率啊。
需要回表的数据越多,使用二级索引的性能就越低。本来我们建立一个二级索引,就是为了能提前筛选出更加精确的数据。如果二级索引查询一大堆数据的话,那这个索引还有使用的必要吗?
所以,在我们尽量要用数据更加散列的字段来建立索引
联合索引
既然可以使用其他字段建立索引了,那肯定也可以通过多个字段建立索引咯。可以如图:
这个与上面说的唯一不同区别就是,所有的记录页都增加了一个字段。优先按照第一个索引字段排序,相同的话再按照第二索引字段,依旧相同的话再按照第三索引字段。。。。最后是主键id排列。
主键依旧是只存在叶子节点中,每次查询,都要到最底层的叶子节点才可以获取主键id。
那这种通过多个字段建立的索引树就是联合索引。
既然我们建立索引的时候有排序的优先顺序,当然查询的时候,条件语句也是有优先顺序的。不过这个问题不用担心,mysql的查询优化器会优化我们传入的条件字段。按照最符合索引的方式进行排列。
明白了这个联合索引的排列顺序,那清楚为什么查询的时候要按照左侧优先了吗?
- 无论是索引条件还是字符串like查询的时候,都是按照左侧优先排序的。比如字符串“bai%”,在索引中肯定是先梳理到“b”开头的字符。如果直接“%du”,这种形式查询,就没有办法使用索引了。
- 多个字段查询也是这种顺序,比如我们现在的联合索引是idx_name_phone_address
那查询的时候,使用name+phone,就可以使用索引,但是直接用phone+address就无法用到这个二级索引了 - 还有排序,如果我们定义的排序规则同索引顺序相同的话,就可以直接使用索引排序。比如:order by name, phone; 但是如果反过来order by phone , name; 就无法直接使用索引进行排序了。
预告
下一章节单独列一下执行计划的各个参数定义