1. 前言
通过「行格式」我们知道了记录在磁盘里的存储格式,除了存储记录的真实数据外,每条记录还会有额外的头信息、变长字段长度列表、NULL 值列表等信息。为了更好的管理记录,InnoDB 以「页」为基本单位,将一条条记录存储在一个个单独的页中,页内的记录按照主键排序并形成单向链表,页与页之间通过在 File Header 里记录上一个和下一个页的页号来形成双向链表。
一张表的记录往往是很多的,可能上千万甚至上亿条记录。可即便如此,哪怕上亿条记录的表,我们通过主键或索引检索数据时,速度依然很快,InnoDB 是怎么做到的呢?这就是我们今天要介绍的 B+树索引。
2. B+树索引
现有一张仅有两个列的表 T,如下所示:
CREATE TABLE `T` (
`id` INT NOT NULL,
`c` VARCHAR(10) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB ROW_FORMAT=COMPACT;
现假设一个页仅能存下三条记录,随着用户记录不断插入,InnoDB 不断申请新的索引页,最终结构如下图所示:现在我们要查询
id=10
的记录,InnoDB 会怎么做呢?很遗憾,只能从页 1 开始一个页一个页的往后找。InnoDB 会先将页 1 从磁盘加载到内存,然后遍历用户记录,判断是否存在 id=10 的记录,没有找到则继续加载页 2,然后重复前面的过程,这就是「全表扫描」。当然,这个查找的过程也可以偷懒。首先,页内的记录无需全部遍历,通过 Page Directory 使用二分法即可快速查找。其次,找到第一条 id>10 的记录就不用再往后找了,因为记录是按照 id 排好序的,后面的记录 id 也肯定也比 10 大。尽管可以偷点懒,但可惜的是效果微乎其微,内存的读写速度和 CPU 的算力已经非常快了,整个过程最耗时的操作其实是将页从磁盘加载到内存里,这需要发起系统调用来读取磁盘数据。这些页在物理上可能还不是连续的,机械硬盘随机读的效率是非常低的,如果每次检索数据都要全表扫描一次,这是完全不能接收的。
如何提高根据主键查询记录的效率呢?还记得 Page Directory 吗?页内的记录是有序的,通过将多条记录划分成一组,将每个组里最大的那条记录的地址偏移量填充到 Page Directory 的槽里,通过二分法即可快速定位到组。
有没有发现?索引页本身其实和页内记录的分组很像,页内的记录是有序的,页与页之间也是有序的。于是,InnoDB 直接借鉴了 Page Directory 的设计,将每个索引页内最小的主键值提取出来,给所有的索引页再建立一个目录。目录项最少要记录主键值+页号,例如上图中的记录,先给页 1 创建一个目录项,存储主键值 1 和页号 1;再给页 2 创建一个目录项,存储主键值 4 和页号 2;以此类推。这些目录项存在哪里呢?有没有发现目录项和用户记录也很像?只是用户记录存储的是用户自定义的列数据,而目录项存储的是主键值+页号。所以,InnoDB 直接使用索引页来存储目录项,把目录项和用户记录同等对待,只在记录头信息里通过record_type
属性做区分,0 是用户记录,1 是目录项记录,除此之外两者结构完全一样。存放目录项记录的页类型和存放用户记录的页类型也是一样的,都是0x45BF
。目录项之间也是有序的单向链表,也可以通过 Page Directory 快速查找等等。
现在假设表的每条记录平均占用约 200 字节,那么一页 16KB 可以存储约16*1024/200
80 条记录。假设表有一亿条记录,那么约需要1250000
个页才能容纳所有记录。现在要给这些页建立目录,假设主键用 BIGINT 类型占用 8 字节,页号 INT 类型占用 4 字节,记录头信息占用 5 字节,那么一条目录项记录约占用 17 字节。光是存储目录项记录就需要约1250000*17/1024/1024
20MB 的空间,远远超过了一个页的大小,怎么办?当然是使用多个页存储了,经过计算,发现需要约1250000*17/(16*1024)
1300 个页来存储目录项记录。遍历 1300 个页开销还是太大了,怎么办?俄罗斯套娃,继续给这 1300 个页再建立一个目录,只需要1300*17/(16*1024)
2 个页就够了。最终,数据的组织形式就会变成这样:是不是很熟悉?这就是传说中的 B+树。经过我们上面的计算发现,哪怕上亿条记录的表,树的高度也就在 3 到 4 之间,很少会超过 4 的。这意味着你根据主键检索记录时,最多只需要加载 4 个索引页,相较于全表扫描,这快的可不是一星半点儿啊。
现在我们再来看一下,有索引的情况下,InnoDB 通过主键查找记录的流程。先将 B+树的根节点页面加载到内存,通过 Page Directory 使用二分法快速定位到分组,遍历组内的目录项,通过页号定位到第二层页节点,将该节点页加载到内存,重复前面的过程,直到定位到叶子节点页,最终获取到记录。加载数据页的个数,其实就是 B+树的高度,而且 InnoDB B+树有个特点,就是根节点一旦确定就不会改变,这样 InnoDB 就可以将根节点页做缓存了,进一步减少页的加载次数。
2.1 非聚簇索引
根据主键 id 将记录组织成一棵 B+树,这样就可以通过 id 快速查找记录了。那如果我要根据列 c 查找,是否也可以使用这棵 B+树呢?很抱歉并不能,B+树快速查找有个前提,那就是数据必须有序,很明显,列 c 在这棵树里并没有顺序,所以是无法使用这棵树的。那如果想通过索引使用列 c 查找呢?很简单,给列 c 单独建个索引就好了,语法如下:
ALTER TABLE T ADD INDEX `idx_c` (c) USING BTREE;
上述命令执行完毕后,InnoDB 就会给列 c 构建一棵 B+树索引,这棵树结构上和主键索引一样,内容上稍有不同。B+树的叶子节点,存储的不再是完整的用户记录,而是列 c+id。要想获取完整的用户记录,需要通过 id 再去主键索引上再查询一次,这个过程称作「回表」。
为什么不在叶子节点存储完整的用户记录,而是通过 id 再回表查询一次呢?回表固然影响了效率,但是每棵 B+树都存储一份完整的用户记录实在是太浪费空间了。所以,像主键索引这种 B+树存储了完整的用户记录的索引叫作「聚簇索引」,像列 c 这种 B+树只存储了主键,需要获取完整的用户记录需要回表查询的索引就叫作「非聚簇索引」,也叫「二级索引」或「辅助索引」。
2.2 B+树索引的特性
1、根节点固定不变 一张全新的表,它的聚簇索引 B+树默认会生成一个根节点,但是里面的记录是空的。当我们插入记录时,会先插入到根节点中,根节点“满”了就会再申请两个新的页,然后将数据拷贝到这两个新页中,根节点自动升级为目录项节点,存储的不再是用户记录,而是目录项记录。不管表里的数据怎么变,B+树的根节点始终都不会改变。InnoDB 会将索引树的根节点的页号存储在某个地方便于管理,根节点固定不变,也便于 InnoDB 将根节点缓存起来,减少一次磁盘 IO。
2、目录项记录的唯一性 InnoDB 允许创建「非唯一索引」,这意味着二级索引 B+树中可能存在大量索引值相同的目录项,如果连续的页索引值都相同,那意味着内节点中会有两条索引值相同的目录项记录。此时,如果再插入一条索引值相同的记录,那到底该插入到哪一个页里呢?这种情况下 InnoDB 也不知道该怎么办了。所以,对于非唯一索引,B+树中的目录项记录除了记录索引列+页号外,还会额外存储主键 id,确保目录项记录是唯一且有序的,索引值相同则按照 id 排序。
3、一个页面最少存储 2 条记录 B+树快速检索的本质是因为它每经过一个节点都可以快速的过滤掉大量的无效节点,大大的减少了索引页的加载次数。理论上来说,单个索引页包含的记录数越多,查询的效率就越高。我们上面计算过,一个页面可以包含约 80 条 200 字节的用户记录、约 960 条目录项记录,这样即使上亿条记录树的高度也不会超过 4。一旦页内包含的记录数少了,B+树就会变高,查询效率会指数级下降。所以,为了防止极端情况出现,InnoDB 规定,单个索引页内最少包含 2 条记录。
3. 总结
InnoDB 表数据的组织形式是一棵 B+树,完整的用户记录存储在叶子节点,按照主键值排序。为了提高数据的检索效率,InnoDB 借鉴了 Page Directory 的设计,给所有的叶子节点页建立目录,目录项记录存储的是主键值+页号,InnoDB 使用相同的索引页来存储目录项记录,只是在记录头信息里将两者做了区分。InnoDB 通过俄罗斯套娃的方式,反复给内节点建立目录,直到一个根节点即可容纳所有的目录项记录。视觉上看来,B+树就是一个矮矮的小胖子,检索数据时每经过一个节点就可以过滤掉大量的无效节点,大大的减少了数据页的加载次数,一般来说,上亿条记录的表通过主键查找数据,一般加载不会超过 4 个数据页,效率非常高。
原文始发于微信公众号(程序员小潘):InnoDB表数据的组织形式:B+树
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/28590.html