这篇文章只讲一件事索引。不过内容太长一口气读完太累所以拆成了上、中、下三篇篇目主线上篇从一次 5.43 秒的慢查询出发往下钻到磁盘扇区、操作系统的 4KB 数据块、MySQL 的 16KB 页——回答这 5 秒慢在哪一步中篇从一页数据出发一步步把 B 树推导出来验证为什么偏偏是它再落到聚簇索引、回表、覆盖索引、最左匹配下篇回到键盘前五种索引怎么建、怎么查、怎么删、创建原则末尾附全篇知识速查表但我们不打算一上来就甩给你一句索引是 B 树然后开始念语法。那样你记住的只是结论换个场景就不会用了。我们换一种走法——从一个真实的性能事故出发一层一层往下挖看看数据到底存在哪儿、是怎么被读出来的、慢在哪一步然后自己把 B 树推导出来。等你走完这一趟你会发现 B 树不是天上掉下来的设计而是被硬件条件一步步逼出来的唯一合理解。目录〇、先看全景这篇文章要带你走一条什么样的路一、提出问题800 万行数据里查一个人为什么要等五秒1.1 先把海量表造出来1.2 见证一次慢查询1.3 只加一行语句1.4 天下没有免费的午餐1.5 我们真正要回答的问题二、往下钻一层数据到底存在哪里2.1 磁盘是一个机械装置2.2 盘片上的几何学磁道、扇区、柱面2.3 怎么在磁盘上报地址CHS 与 LBA2.4 同样是读磁盘为什么有的快有的慢2.5 小结我们已经解决了什么还剩什么问题三、再往上一层操作系统为什么不按 512 字节读3.1 三个理由3.2 那操作系统一次读多少3.3 局部性原理预加载为什么能生效3.4 一个关键的认知转折四、回到 MySQL16KB 的页4.1 MySQL 是一个IO 大户4.2 为什么是 16KB4.3 为什么一次拿一页比用多少拿多少划算4.4 Buffer PoolMySQL 的缓存池4.5 建立共识〇、先看全景这篇文章要带你走一条什么样的路在动身之前先给你一张地图。技术文章最容易犯的毛病是把你丢进细节的森林里却不给方向。所以我们先把整条路径画出来每一章你都知道自己在哪、要去哪。这张图从左到右是问题从上到下是答案。你会注意到一个关键点我们从磁盘硬件开始讲而不是从 SQL 语法开始讲。原因很简单索引是一个为解决磁盘 IO 太慢而生的数据结构。如果你不理解磁盘慢在哪你就无法理解 B 树为什么要设计成那个样子只能死记硬背。所以这条路径不能跳。一、提出问题800 万行数据里查一个人为什么要等五秒1.1 先把海量表造出来要观察索引的效果用几十行数据是看不出问题的——数据太少有没有索引都是瞬间返回。所以第一步我们得先造一张真正的大表。下面这段代码的作用是创建一个存储过程往EMP雇员表里批量插入800 万条随机数据。这里可以先把它当成造数据的工具复制执行不必逐行读懂我在每一段后面都写了它到底在干什么。-- ① 产生随机字符串下面造数据时用来生成随机的员工姓名 delimiter $$ create function rand_string(n INT) returns varchar(255) begin -- 从这 52 个大小写字母里随机挑这是字母表 declare chars_str varchar(100) default abcdefghijklmnopqrstuvwxyzABCDEFJHIJKLMNOPQRSTUVWXYZ; declare return_str varchar(255) default ; declare i int default 0; -- 循环 n 次每次从字母表里随机抽 1 个字符拼到结果后面 -- 抽 n 次就得到一个长度为 n 的随机字符串 while i n do set return_str concat(return_str, substring(chars_str, floor(1 rand() * 52), 1)); set i i 1; end while; return return_str; end $$ delimiter ;-- ② 产生随机数字用来给每个员工随机分配一个部门编号 delimiter $$ create function rand_num() returns int(5) begin declare i int default 0; -- 在 10 ~ 510 之间随机取一个整数 set i floor(10 rand() * 500); return i; end $$ delimiter ;-- ③ 批量插入的存储过程一次往 EMP 表塞进 max_num 条记录 delimiter $$ create procedure insert_emp(in start int(10), in max_num int(10)) begin declare i int default 0; -- 关掉自动提交800 万条如果一条一次提交会慢到天亮 -- 攒成一批一起提交速度天差地别 set autocommit 0; repeat set i i 1; -- 逐条插入编号递增姓名随机职位固定入职日期取当天 insert into EMP values ( (start i), -- empno员工编号从 start 开始递增 rand_string(6), -- ename随机 6 位姓名 SALESMAN, -- job职位固定写死 0001, -- mgr上级编号固定写死 curdate(), -- hiredate入职日期取当前日期 2000, -- sal月薪固定写死 400, -- comm奖金固定写死 rand_num() -- deptno部门编号随机 ); until i max_num end repeat; commit; end $$ delimiter ;-- ④ 真正开始造数据从编号 100001 开始一口气插 800 万条 call insert_emp(100001, 8000000);执行完这条call你的磁盘上就会多出一张 800 万行的EMP表。注意这张表的一个关键特征建表时没有指定主键。这一点在后面的故事里很重要先记着。1.2 见证一次慢查询现在我们来做一次再普通不过的查询找编号为 998877 的那位员工。select * from EMP where empno 998877;------------------------------------------------------------------------------ | empno | ename | job | mgr | hiredate | sal | comm | deptno | ------------------------------------------------------------------------------ | 998877 | AJFiaC | SALESMAN | 0001 | 2023-06-10 00:00:00 | 2000.00 | 400.00 | 367 | ------------------------------------------------------------------------------ 1 row in set (5.43 sec)5.43 秒。查一行数据等了五秒多。这个数字意味着什么这还只是你一个人在本机操作。如果放到公网环境同时有 1000 个人并发查这张表数据库很可能直接被打死。在真实项目里这已经不是慢而是事故。1.3 只加一行语句现在我们不改程序、不加内存、不优化 SQL只加一行语句-- 给 empno 这一列建一个索引 alter table EMP add index(empno);Query OK, 0 rows affected (25.29 sec) Records: 0 Duplicates: 0 Warnings: 0建索引本身花了 25.29 秒——这不奇怪800 万行数据要重新组织成一棵树是要花力气的。这也提前透露了一个信息索引不是免费的它的代价会在写入时体现。现在执行完全相同的那条查询select * from EMP where empno 998877;1 row in set (0.00 sec)0.00 秒。数据没变、SQL 没变、硬件没变仅仅是多了索引查询时间从 5.43 秒变成了 0.00 秒。补充一个数据点同一份资料在另一次机器上的实测是4.93 秒。具体数字随机器配置波动但秒级 → 毫秒级这个数量级的跨越是稳定的。1.4 天下没有免费的午餐如果你读到这儿的第一反应是索引这么强那我给每一列都建上索引那我们得先泼盆冷水。世界上没有凭空变快的魔法。索引让查询变快代价是第一空间代价。索引本身是一棵独立的数据结构要占磁盘、占内存。你建 5 个索引就多维护 5 棵树。第二写入代价。每次插入、删除、更新数据对应的索引树也要跟着调整。就像你往一本书里插一页后面所有页码和目录都得改。这解释了刚才那 25.29 秒——那是在为 800 万行历史数据补建目录。这其实是一个更普遍的规律任何数据结构都有它擅长的操作和不擅长的操作。那么问题来了既然每种结构都有短板凭什么 B 树就适合做索引这个问题现在还没法回答。但我们可以确定一件事——索引是为了解决查询慢而存在的所以我们必须先搞清楚到底慢在哪一步。1.5 我们真正要回答的问题把刚才的现象整理成两个待解的问题问题一为什么同样的数据、同样的 SQL加了索引就能快几百倍那 5.43 秒到底花在哪儿了问题二为什么 MySQL 选择 B 树而不是链表、二叉树、哈希表要回答第一个问题我们必须从数据存放的物理位置开始一层层往上查。这就是接下来三章要做的事。二、往下钻一层数据到底存在哪里前面我们看到一次查询要等五秒。现在我们要问这五秒钟究竟消耗在哪答案的第一步是搞清楚数据存在哪里。MySQL 提供的是存储服务而存储的无论是内容还是属性最终都叫数据。这些数据放在磁盘这个外设当中。2.1 磁盘是一个机械装置这句话听起来像废话但它决定了后面所有的设计。磁盘是计算机中的一个机械设备。相比之下CPU、内存都是电子元件靠电流开关完成工作而磁盘要靠盘片旋转和磁头摆动来读写数据。机械运动的速度和电子信号的速度根本不在一个量级上。所以磁盘慢是物理决定的改不了。我们唯一能做的是让它少动几次。2.2 盘片上的几何学磁道、扇区、柱面先看一个盘片。盘片表面被划分成一圈一圈的同心圆每一圈叫做一个磁道Track。磁道再沿着半径方向被切成一段一段每一段就是一个扇区Sector。这里有两个必须在脑子里建立清楚的对应关系第一磁头和盘面是一对一的。有多少个盘面就有多少个磁头。所以选中哪个磁头就等于选中哪个盘面。第二柱面和磁道是等价的。只是视角不同看单个盘片它叫磁道把整摞盘片一起看同半径的那一圈圈磁道在侧面叠成一个圆柱面于是叫柱面。两者描述的是同一个物理位置只是参照系不同。还有一个容易忽略的细节扇区是扇形的越靠近圆心越窄越靠外越宽。但每个扇区存储的数据量是固定的 512 字节——这个大小由盘片的比特位密度决定。近年来确实出现了 4096 字节扇区的新技术但我们这里仍按经典的 512 字节来理解。2.3 怎么在磁盘上报地址CHS 与 LBA现在我们知道数据存在一个个扇区里。那么如何精确地告诉磁盘我要第几个扇区顺着刚才的结构答案很自然用三个编号就能唯一定位一个扇区。这种定位方式叫做CHS 寻址。但是有个问题实际系统中操作系统使用的并不是 CHS而是 LBALogical Block Address逻辑块地址。LBA 是一种线性地址——你可以把它想象成给整个磁盘的所有扇区从零开始连续编号操作系统只说我要第 N 个块剩下的换算交给磁盘去做。你可以粗略理解为虚拟地址与物理地址的关系操作系统面向逻辑地址编程磁盘负责把逻辑地址翻译成物理的 CHS。这样做的好处是操作系统的 IO 代码不必和具体磁盘的物理结构强绑定。换算的细节我们不用关心知道逻辑地址 → 物理地址这条映射链存在逻辑上自洽就够了。2.4 同样是读磁盘为什么有的快有的慢这里要引入一组非常重要的概念。同样是两次读磁盘效率可能差别巨大取决于两次请求的扇区地址是不是连续的。连续访问本次 IO 给出的扇区地址和上一次 IO 结束时的地址是连续的。磁头不需要重新寻道盘片转过去就能接着读马上开始这次操作。随机访问两次请求的扇区地址相差很大。磁头必须做比较大的移动动作才能重新开始读写。请注意一个容易被误解的点即使相邻的两次 IO 是在同一时刻发出的只要它们请求的扇区地址相差很大依然算随机访问。连续说的是地址连续不是时间接近。再往下追问一层为什么地址连续就这么关键因为磁盘是通过机械运动进行寻址的——磁头左右摆动是在选择柱面盘片旋转是在选择扇区。机械动作越少越快。所以连续访问之所以快本质上是它省掉了机械定位的开销。一个重要的设计原则浮出水面在组织数据时要尽量制造连续访问规避随机访问。这条原则会一直贯穿到后面 B 树的设计中。2.5 小结我们已经解决了什么还剩什么问题到这里我们已经能够在硬件层面定位磁盘上的任何一个扇区了也知道了连续的地址访问得快跳来跳去访问得慢。但还有一个问题悬在半空数据到了扇区这一层操作系统就直接按 512 字节一个个读吗答案是否定的。而理解为什么否定是理解 MySQL 为什么用 16KB 页的关键跳板。三、再往上一层操作系统为什么不按 512 字节读3.1 三个理由既然磁盘硬件的最小单位是 512 字节的扇区操作系统为什么不用 512 字节做 IO 单位理由有三条一条比一条重要。理由一避免与硬件强耦合。如果操作系统直接按硬件提供的 512 字节来交互那么系统的 IO 代码就和硬件强相关了。一旦硬件发生变化比如换成 4KB 扇区的磁盘操作系统就必须跟着改。这对一个要支持成千上万种硬件的通用系统来说是不可接受的。所以操作系统必须在硬件之上再加一层抽象。理由二512 字节一次的 IO 单位太小了。这是性能上的考量。IO 单位小意味着读取同样的数据内容需要进行更多次磁盘访问。而每一次访问都要付出前面讲过的机械代价寻道、旋转等待、读取。次数越多累积的机械开销越大效率越低。理由三之前学文件系统时就已经埋下伏笔了。文件系统是在磁盘的基本结构之上建立的而文件系统读取的基本单位本来就不是扇区而是数据块。三条理由合起来得出一个结论操作系统读取磁盘是以数据块为单位的这个基本单位是 4KB。顺带提一句内存也是被划分为 4KB 大小的块来管理的分别叫页框Page Frame物理内存和页帧/页面Page虚拟内存。磁盘的 4KB 和内存的 4KB 对齐IO 交互时最省事。3.2 那操作系统一次读多少这就引出一个新的问题你只要一个字节操作系统凭什么给你读 4KB这不是浪费吗表面上确实是浪费。但操作系统这么做有它的考量这个考量叫做局部性原理。3.3 局部性原理预加载为什么能生效局部性原理说的是程序在访问数据和指令时有很大概率还会访问它周边的数据。这包括两个层面时间局部性刚刚访问过的数据很可能马上还会再访问一次空间局部性访问了某个地址的数据很可能接着访问它相邻地址的数据正因为有这个特性操作系统一次预加载 4KB就是一笔划算的买卖你这次可能只用了 20 个字节但剩下的 4KB 也一并被搬进了内存。下次你要访问相邻数据时直接命中内存完全不需要再碰磁盘。这是一个概率上的胜利。你无法严格保证下次一定用到但大概率会用到。而在工程上大概率就足以支撑一个设计了。3.4 一个关键的认知转折在继续往下之前请把这句话刻进脑子里它是整篇文章的题眼IO 效率低下的最主要矛盾不是单次 IO 的数据量太大而是 IO 的次数太多。因为每一次 IO 都伴随机械定位开销次数才是成本。所以减少 IO 次数就是提升效率的核心手段。理解了这一点我们就能理解 MySQL 为什么要把 IO 单位做得更大——因为它和磁盘打交道的机会比操作系统还要多得多。四、回到 MySQL16KB 的页4.1 MySQL 是一个IO 大户现在把视角切回 MySQL。MySQL 作为一款应用软件你完全可以把它理解成一种特殊的文件系统。它比一般文件系统有着更高的 IO 场景——因为它的本职工作就是不停地读写数据。而在软件分层上MySQL 和磁盘之间隔着操作系统MySQL 是应用进程不可能直接和硬件打交道。真正能碰硬件的只有操作系统。所以我们平时说的MySQL 读磁盘严格来说应该是MySQL 向操作系统要数据操作系统再去和磁盘打交道。4.2 为什么是 16KB既然 IO 次数是主要矛盾那么对 MySQL 来说把单次 IO 的单位做大就能减少 IO 次数。于是 MySQL确切地说是 InnoDB 存储引擎选择了16KB作为自己的 IO 基本单位。这个基本数据单元在 MySQL 里叫做page页。请注意和操作系统的 page 区分——这是两个不同的概念MySQL 的 page 是 16KB操作系统的 page 是 4KB。口说无凭我们可以直接查-- 查询 InnoDB 的页大小 show global status like innodb_page_size;------------------------- | Variable_name | Value | ------------------------- | Innodb_page_size | 16384 | ------------------------- 1 row in set (0.01 sec)16384字节 ÷ 1024 16KB。确认无误。三者是层层放大的关系。物理硬件的基本单位是 512 字节而 MySQL InnoDB 引擎使用 16KB 进行 IO 交互。4.3 为什么一次拿一页比用多少拿多少划算你可能会想用多少加载多少不香吗为什么非要一次拿 16KB我们用一组具体数据算笔账。假设有 5 条记录如果一次只加载一条记录那么查 id2 是第 1 次 IO查 id3 是第 2 次 IO……要找第 5 条就要 5 次 IO。而如果这 5 条或者更多条都保存在同一个 page里16KB 足够装很多记录那么第一次查 id2 时整个 page 会被一次性加载到 MySQL 的 Buffer Pool 中这一次 IO 就把后续数据全都带进来了。之后无论查 id1、3、4、5完全不需要再做 IO直接在内存里找就行。这就是单页内大幅减少 IO 次数。但你可能会追问一个很尖锐的问题你凭什么保证用户下次要找的数据就在这个 page 里答案是不能严格保证但有很大概率。依据还是上一条——局部性原理。所以你看为什么是 page这个问题答案其实是两条一是减少 IO 次数二是局部性原理让预加载变得划算。4.4 Buffer PoolMySQL 的缓存池前面反复提到加载到 Buffer Pool现在把它讲清楚。现实需要解决的问题是MySQL 每次要处理数据都得先把数据从磁盘搬到内存。如果每次都临时申请内存、用完就释放那么内存的分配回收开销本身就会拖累性能而且无法复用已经读进来的数据。所以 InnoDB 的设计是在服务器启动时一次性向操作系统申请一大块内存专门用来缓存数据页这块空间就是Buffer Pool缓冲池。-- 查看 Buffer Pool 的大小 show variables like innodb_buffer_pool_size;------------------------------------ | Variable_name | Value | ------------------------------------ | innodb_buffer_pool_size | 134217728 | ------------------------------------ 1 row in set (0.01 sec)134217728字节 ÷ 1024 ÷ 1024 128MB。128MB 就是它的默认大小。这个一次性申请一大块自己内部再管理的思路你在 C 里应该见过类似的——STL 容器底层的空间配置器就是这么干的先申请一大片容器自己负责切分和回收。两者思想一致但是管理方式完全不同不能混为一谈。MySQL 内部还要对这块空间做更复杂的管理哪些页刚被加载、哪些页是脏数据被改过但还没写回磁盘、哪些页很久没用该淘汰了……这些都需要一套机制来维护。简单说读数据时磁盘 → 操作系统 → Buffer Pool → 在内存中处理写入时先在 Buffer Pool 中修改此时这个页变成脏页再按一定的刷新策略刷回磁盘。4.5 建立共识到这里我们已经攒够了继续前进的资本。把前面的结论固化成三条共识后面的推理会反复用到它们。共识一MySQL 中的数据文件是以 page16KB为单位保存在磁盘上的。共识二MySQL 的 CURD 操作都需要经过计算——插入时要算出位置删除时要找到目标查询时要定位数据。而只要涉及计算就必须由CPU参与。为了便于 CPU 参与就一定要先把数据从磁盘移到内存中。所以在特定时间内数据一定是磁盘中有一份内存中也有一份。共识三为了更高的效率一定要尽可能减少系统和磁盘 IO 的次数。一次 IO 搬运的数据量越大需要的 IO 次数就越少。用一句话总结共识三要写 100MB 数据一次写 100MB只需要定位一次磁盘位置 而分成 100 次、每次写 1MB就要寻道 100 次——盘片在转、磁头在摆全是机械开销。硬件、系统、MySQL 三层的关系我们已经全部打通。现在终于可以进入正题了。中篇预告地基已经打好下一篇我们正式开始造索引——从一页数据出发把 B 树一步一步推导出来再逐个审问链表、二叉树、哈希表这些备选方案回答为什么偏偏是 B 树最后落到索引的两种活法聚簇索引与非聚簇索引。