RezeのBlog
← 返回文章列表

索引为什么长成一棵倒过来的树

2024.01.11技术4888 字参考 3

去年有阵子,我自己那个小站的一个查询接口突然从两百毫秒涨到三秒。我第一反应特别朴素:加索引啊,这还用想?我打开建表语句,给那个 where 后面的字段噼里啪啦加了两个索引,改完重启,心想这下稳了。结果第二天,接口更慢了,三秒变四秒。我当时整个人是懵的。加索引不是应该更快吗,怎么还越加越慢?后来花了一整晚,把慢查询日志、EXPLAIN 执行计划、还有 InnoDB 的索引结构翻了个底朝天,才把这件事弄明白。那一晚之后我才算真正理解了:索引不是“加得越多越快”的魔法,它是一棵有严格规矩的树,你喂给它什么形状,它就按什么形状去查。

索引到底是什么,先别急着背 B+ 树

Indexes are used to find rows with specific column values quickly.

—— MySQL 8.0 Reference Manual

我后来发现,讲索引最好的类比不是教科书那套,而是——你手里那本很厚的字典。你要查一个字,不可能从第一页翻到最后一页,那太蠢了。字典前面有个拼音索引或者部首索引,它告诉你“这个字在第 812 页”,你直接翻到 812 页。索引干的就是这件事:它是一份额外的、排好序的“目录”,把“我要找什么”和“东西在哪”对应起来,让你不用扫全表。数据库里的表,就是一本没有目录的书。你 `select * from orders where user_id = 123`,如果没有索引,数据库只能从第一行读到最后一万行,一行行比,这叫全表扫描。数据量小的时候没感觉,几百万行的时候,就是灾难。

所以索引的本质,是一份额外的、有序的数据结构,用空间换时间。那为什么这份“目录”非得长成一棵树?因为数据库的数据不在内存里,在磁盘上。这是理解 B+ 树的钥匙,很多人背了半天 B+ 树的定义,却没抓住这一点。我们平时写代码,习惯用内存的速度去想象一切。内存读写大概是纳秒级,磁盘(尤其是机械硬盘)的随机读写是毫秒级——中间差了十几万倍。就算是现在满大街的 SSD,随机读也就几十上百微秒,跟内存比还是慢几万倍。

所以数据库设计的第一原则,不是“少算几次”,而是“少读几次磁盘”。而磁盘读数据,不是你要一个字节它就给一个字节,它按“块”读。InnoDB 里这个块叫“页”,默认 16KB。你哪怕只想读一行记录,磁盘也得把那一整页 16KB 弄上来。这就决定了:索引这棵树,必须长得“矮胖”,让每一次读磁盘,都能排除掉尽可能多的数据。

为什么不是二叉树,也不是红黑树

学过数据结构的都知道二叉搜索树:每个节点最多两个孩子,左边小右边大。听起来很美好。问题是它太“高”了。你想,一千万条数据,一棵平衡二叉树的高度大概是 log2(一千万),差不多 23 层。意味着最坏情况下你要从根走到叶子,读 23 次节点。如果每个节点都在磁盘上、都要一次 IO,那就是 23 次磁盘读。接口能快才怪。红黑树稍微好点,它是个近似平衡的二叉树,但本质还是二叉树,高度还是 O(log n) 这个量级,一千万行也得几十层。而且每个节点只存一个键,太浪费——磁盘一次给你 16KB,你只用了里面几十个字节,剩下全扔了,血亏。

B+ 树的高明,就在于它“一个节点塞很多个键”。一个 16KB 的页,如果每个键加指针占十几字节,能塞进去上千个键。于是树的“分叉”变得极多,高度被压到很低。一千万行数据,B+ 树大概三到四层——也就是说,查一条记录,最多读三四次磁盘就够。三四次,和二十几次,差着数量级。这就是为什么数据库索引几乎清一色用 B+ 树,而不是你在算法题里更熟悉的二叉树、红黑树。算法题考的是内存里的比较次数,数据库拼的是磁盘 IO 次数。场景变了,最优解就变了。

很多人会问,B 树(B-tree)不也是多叉的吗,为什么不用 B 树?区别在于数据放哪。B 树的每个节点(包括中间节点)都存实际数据;B+ 树只有叶子节点存数据,中间节点只存“键”和“指向孩子的指针”,相当于纯路标。这个差别带来两个好处。第一,中间节点不存数据,就能塞下更多键,树更矮更胖,IO 更少。第二,B+ 树的叶子节点之间用链表连起来了。这意味着你范围查询特别顺:`where id between 100 and 200`,B+ 树先定位到 100 所在叶子,然后顺着叶子链表往后走就行,不用每次都回到根重新找。B 树做不到这么丝滑。

所以对数据库这种“范围查询 + 排序”极其常见的场景,B+ 树是量身定做的。顺带说一句哈希索引。哈希表查询是 O(1),理论上比 B+ 树还快。但它只能做等值查询(`where id = 5`),你让它查范围、排序,它直接歇菜,因为它压根不维护顺序。所以 InnoDB 里哈希索引只用在特定场景(比如自适应哈希索引),主力还是 B+ 树。Redis 那种纯内存、又要 O(1) 的,才用哈希和跳表。

聚簇索引和回表,我第一次听也懵

真正让我那晚开窍的,是“聚簇索引”和“回表”这两个词。InnoDB 里,主键索引就是整张表本身,叫聚簇索引(clustered index)。它的叶子节点里存的不是“主键到行地址的映射”,而是完整的一行数据。也就是说,你按主键查,找到叶子就等于拿到了整行,一步到位。但如果你按 `user_id` 查,而 `user_id` 上是个普通索引(二级索引),情况就不一样了。二级索引的叶子节点里存的,是 `user_id` 和主键值,不是整行。数据库先在这个索引里找到主键,再拿着主键回聚簇索引里把整行捞出来——这一步就叫“回表”。

回表意味着什么?意味着一次查询可能走了两棵树,读了两次磁盘。这就是为什么有时候你明明加了索引,却还是慢:因为你要的字段不在索引里,每次都得回表。解决办法是“覆盖索引”:如果你要查的字段刚好都在索引里(比如联合索引 `(user_id, status)`,你只查这两个字段),数据库就不用回表了,直接从索引返回。这也是为什么老手总说“别写 select *”,除了省流量,还有个原因是它经常逼你回表。

联合索引和最左前缀,那个规矩特别死

再说联合索引。你可以给多个字段建一个索引,比如 `(a, b, c)`。它不是三个独立索引,而是一个按 a 排、a 相同再按 b 排、b 相同再按 c 排的整体。这里有个特别死的规矩,叫“最左前缀”。`where a=1 and b=2` 能用上这个索引,`where a=1` 也能用上,但 `where b=2` 单独查,用不上——因为索引是先按 a 排的,你跳过 a 直接找 b,等于让它在一本按姓氏排的电话簿里只按名字找,它只能从头翻。

我刚学的时候老记不住这个,后来用字典的类比就想通了:字典先按拼音首字母排,你只知道第二个字母,没法直接定位。这也解释了我那次“加索引反而更慢”的一部分原因。我当时加的索引没配合查询的字段顺序,数据库根本用不上,白占空间;而索引一多,每次插入、更新都要维护这棵树,写变得更重,整体反而拖慢了。这点我吃了亏才懂。每加一个索引,就多一棵 B+ 树要维护。你 insert 一行,所有索引都得跟着改;update 一个被索引的字段,相关索引要重排;delete 更不用说。所以索引多了,读可能快一点,写一定变慢,还占磁盘。

而且优化器有时候会“选错索引”——它根据统计信息估算走哪个索引便宜,但统计信息会过期,估错了,本来该走 A 索引的走了 B 索引,反而更慢。这也是为什么有时候你 `force index` 一下,查询突然就快了。所以正确的姿势不是“哪里慢加哪里”,而是:先 `EXPLAIN` 看执行计划,搞清楚它到底走没走索引、走的是哪个、有没有回表、扫了多少行,再决定加什么索引。盲目加索引,就是我现在回头看最蠢的操作。

索引明明建了,为什么还是没用上

这是我踩坑最多的地方,得单独拎出来说。很多时候你不是没建索引,是索引“失效”了——建了等于白建。第一种,对索引字段做了函数运算。比如 `where date(created_at) = '2024-01-01'`,你给 `created_at` 建了索引,但数据库得先把每一行的 `created_at` 都跑一遍 `date()` 函数才能比,索引根本用不上。正确写法是 `where created_at >= '2024-01-01' and created_at < '2024-01-02'`,把函数从字段上挪到常量上。第二种,隐式类型转换。你的 `phone` 字段是 varchar,你写 `where phone = 13800000000`(不带引号,当数字了),数据库得把每一行的字符串转成数字再比,索引失效。加个引号就好。这种坑特别阴,因为它不报错,就是悄悄变慢。

第三种,`like` 用了前置百分号。`like 'abc%'` 能用索引(前缀匹配),`like '%abc'` 和 `like '%abc%'` 用不上,因为它得扫全表才能知道哪一行匹配。第四种,`or` 连接了没索引的字段、用了 `!=`、`not in`、`is not null` 这类“否定式”条件,优化器经常直接放弃索引走全表。不是绝对,但值得警惕。第五种,联合索引不满足最左前缀,前面讲过了。这几种,我都在真实项目里遇到过。最气的是它们全都不报错,只是慢,你不看执行计划根本发现不了。所以现在我写 SQL,只要涉及时间、字符串、模糊匹配,心里都会先过一遍这张清单。这个点很多人听过“用自增主键性能好”,但说不清为什么。理解了聚簇索引就明白了。

前面说过,InnoDB 的主键是聚簇索引,整张表按主键顺序物理存储。你用自增主键,每插一行,新主键永远比之前大,直接追加到 B+ 树的最后,顺序写,很快。但如果你用 UUID 这种随机字符串当主键,新插入的行的主键是随机的,它可能落在 B+ 树中间任何一个位置。于是数据库得先把那个位置所在的页读上来,插进去,页满了还得“分裂”成两页,再把数据挪来挪去。频繁的页分裂,会让写入变慢、索引碎片变多、磁盘占用变大。

而且自增主键是整型,占空间小;UUID 是 36 个字符的字符串,主键又会被存进每一个二级索引的叶子节点里(还记得吧,二级索引存的是主键值),主键越大,所有二级索引跟着膨胀。所以“自增主键”不是玄学,是跟聚簇索引的物理存储方式死死绑定的。当然,分布式场景下自增主键不好搞(多台机器怎么统一发号),才有了雪花算法(Snowflake)这种“趋势递增但不连续”的方案——它既要尽量顺序,又要全局唯一,本质上是在“顺序写”和“分布式唯一”之间找平衡。

现在我看慢查询的顺序

折腾完那一晚,我给自己定了个流程,一直用到现在:先看慢查询日志,确认是哪条 SQL 慢。然后 `EXPLAIN` 看 `type`(是不是 ALL 全表扫)、`key`(用了哪个索引)、`rows`(预估扫多少行)、`Extra`(有没有 `Using filesort`、`Using temporary`、`Using index`)。如果 `type` 是 ALL,那基本就是没索引或者索引失效;如果 `Extra` 里出现 `Using filesort`,说明排序没走索引,数据一多就慢。

再回头看 SQL 本身:有没有对索引字段做函数运算(`where date(created_at) = ...` 会让索引失效)、有没有隐式类型转换(字符串字段用数字查)、有没有 `like '%xxx'` 这种前置模糊(索引也用不上)。这些坑,比“加不加索引”更隐蔽。那晚之后,那个接口最后是靠“建一个覆盖索引 + 改写 SQL 去掉函数运算”救回来的,从四秒回到了一百多毫秒。加索引这件事本身没错,错的是我把它当成了一颗不用动脑的止疼药。

现在我偶尔还是会想起那个“加了索引更慢”的下午。它教会我的不是某个具体知识点,而是一个更朴素的东西:任何“优化”,你都得先搞清楚它底下那台机器是怎么运转的。你不懂磁盘按页读、不懂树为什么长这样,你加的每一个索引,都可能是在给未来的自己挖坑。

参考与延伸