为什么 MySQL 偏偏选了 B+ 树?

简介: 大家在业务里应该都碰到过这种事:- 一张两千多万行的 `user` 表,`select * from user where id = 12345` 眨眼就回来了;- 同一张表,`where nickname = 'leikooo'` 却慢到能感觉出来,`explain` 一看,`type = ALL`,全表扫描;- 给 `nickname` 加一个索引,同样的 SQL 立刻变快;- 面试

大家在业务里应该都碰到过这种事:

  • 一张两千多万行的 user 表,select * from user where id = 12345 眨眼就回来了;
  • 同一张表,where nickname = 'leikooo' 却慢到能感觉出来,explain 一看,type = ALL,全表扫描;
  • 给 nickname 加一个索引,同样的 SQL 立刻变快;
  • 面试时被问「MySQL 的索引为什么用 B+ 树」,脱口而出「因为快」,再往下问就卡住了。

索引天天用,可真要问起来,大家可能也说不太清:索引到底是什么(what)?InnoDB 里的 B+ 树怎么一步步找到那一行(how)?它为什么偏偏是 B+ 树,而不是 hash、红黑树或者 B 树(why)?这篇文章就顺着这三个问题,把 B+ 树索引从头讲一遍。

索引是什么

先说是什么。一句话:索引是一份「按 key 排好序、能快速跳到目标位置」的目录。

大家去图书馆找一本书,不会从第一排书架挨本翻,而是先查索书号,比如 TP311.13,T 区、P 架、311 那一层,三步就站到了书跟前。字典的部首目录、书最前面的目录页,都是同一个思路:多花一点空间存一份目录,换来查找时不用从头翻。

数据库也一样。没有索引的时候,where nickname = 'leikooo' 只能把两千多万行全读一遍,一行一行比;有了索引,就能像查索书号一样,几步跳到目标。

InnoDB 里的索引分两种,后面会反复用到:

  • 聚簇索引(主键索引):按主键排序,叶子里存的就是整行数据。也就是说,InnoDB 的表本身就是一棵按主键组织的 B+ 树,「数据」和「索引」是同一个东西。
  • 二级索引:比如给 nickname 建的索引,按 nickname 排序,叶子里存的不是整行,而是这一行的主键值。查到主键后,还得回聚簇索引里再找一次整行,这一步叫回表。

目录有了,接下来的问题是:这份目录在磁盘上长什么样?

B+ 树长什么样,一次查找怎么走

InnoDB 读写磁盘的最小单位是页(page),默认 16KB。B+ 树的每个节点就是一页。整棵树分两类页:

  • 非叶子页:只存 key 和「指向下一层哪一页」的指针,像书的目录,不存任何行数据;
  • 叶子页:按 key 排好序,存真正的数据(聚簇索引存整行,二级索引存主键);而且相邻的叶子页之间用双向链表串起来。

B+ 树:上面几层是目录,最下面一层才是数据

一次查找具体怎么走? 以 where id = 37 为例(图里的 key 是示意):

  1. 读根页:根页里有 1 | 30 | 60 三格,30 ≤ 37 < 60,所以顺着 30 这一格的指针往下走;
  2. 读非叶子页:这一页是 30 | 40 | 50,30 ≤ 37 < 40,继续顺着 30 往下走;
  3. 读叶子页:到了「30~39」这一页,页内的记录是有序的,二分一下就找到了 id = 37 这一行。

查 id = 37:从根页一路往下,每层只读一页

整个过程每层只读一页,树有几层就读几页。页内那点二分查找是在内存里做的,和从磁盘读一页比起来几乎可以忽略。所以衡量一棵索引树快不快,看的就是一个数:树高。

为什么叶子之间还要串一条链表? 因为业务里大量的查询不是「找一行」,而是「找一段」:where id between 30 and 50、order by create_time limit 20、where age > 18。有了链表,定位到第一条之后,顺着链表往后读就行,不用每找一条都从根重新走一遍。这一点到「为什么」那一节会变成决定性的理由。

三层能装多少行

树高决定了查找次数,那三层的 B+ 树到底能装多少数据?大家可以自己算一遍,用的都是很朴素的数:

  • 一页:16KB,也就是 16,384 字节;
  • 非叶子页里的一项:一个 bigint 主键 8 字节,加一个页指针(按常见估算口径记 6 字节),一共 14 字节,所以一页能放 16384 ÷ 14 ≈ 1170 项;
  • 叶子页:假设一行数据 1KB,一页能放 16384 ÷ 1024 = 16 行。

一层一层乘下去:

  • 第 1 层:1 个根页,指向 1,170 个子页;
  • 第 2 层:1,170 个非叶子页,一共指向 1,170 × 1170 = 1,368,900 个叶子页;
  • 第 3 层:1,368,900 个叶子页,每页 16 行,一共 1,368,900 × 16 = 21,902,400 行。

三层 B+ 树能装多少行:约 2190 万

三层,约 2190 万行。只有两层的话是 1170 × 16 = 18,720 行;四层就到了 1170³ × 16 ≈ 256 亿 行。也就是说,绝大多数业务表,从几万行到几千万行,B+ 树都只有 24 层。这也是开头那张两千多万行的表查主键依然很快的原因:最多读 3 页。而且根页和上面几层的页访问极其频繁,通常一直待在 InnoDB 的 buffer pool 里,真正要去磁盘读的往往只有最底下的 12 页。

当然,这是估算:页头、页目录、每条记录的头信息、为后续插入预留的空间都被忽略了,真实容量会小一些,但量级不会变。

为什么说主键越短越好? 因为非叶子页能放多少项,直接取决于 key 有多长。同样用上面的口径(指针 6 字节、一行 1KB),换几种常见的主键类型算一下:

主键类型 key 长度 非叶子页能放 三层能存
int 4 字节 1,638 项 42,928,704 行
bigint 8 字节 1,170 项 21,902,400 行
binary(16) 存 UUID 16 字节 744 项 8,856,576 行
char(36) 存 UUID 字符串 36 字节 390 项 2,433,600 行

同样三层,char(36) 的 UUID 只能装 243 万行,不到 bigint 的九分之一。表一旦超过这个数,就要长到第四层,每次查找多读一页。

为什么偏偏是 B+ 树

先别急着背「B+ 树的优点」,换个角度想:我们真正想要的是什么?

数据放在磁盘上,磁盘有个特点:按页读,一次随机读很贵。机械盘一次随机 IO 大约 10ms,SSD 快得多,但和内存比起来仍然差着几个数量级。所以我们想要的索引要同时做到两件事:

  • 点查时读的页尽量少,也就是树要尽量矮;
  • 范围查询、排序也要快,因为业务里「找一段」和「找一个」一样常见。

把能想到的数据结构都过一遍,看看每个卡在哪:

  1. 办法一:hash 索引。 点查确实是一步到位,算一下 hash 就知道在哪个桶。但 hash 的本事恰恰是把相邻的 key 打散(讲 hash 的那篇文章里说过,它是「确定性的随机」)。where id between 30 and 50 这 21 个 id,用 crc32(id) % 8 算一下,会散满全部 8 个桶,hash 索引根本不知道「30 后面是 31」,只能把所有桶扫一遍;order by、>、like 'abc%' 同理全都用不上。MySQL 的 Memory 引擎支持 hash 索引,InnoDB 也有一个自适应 hash 索引,但都只是给热点等值查询加速的配角。
  2. 办法二:平衡二叉树 / 红黑树。 有序,范围查询也能做。问题出在太高:每个节点只放 1 个 key,存 21,902,400 行,平衡二叉树最矮也要 ⌈log₂(21,902,401)⌉ = 25 层。一层一次随机 IO,按机械盘算就是 250ms,一次点查都受不了。Java 的 TreeMap 用红黑树没问题,是因为它在内存里,读一个节点只要几纳秒。
  3. 办法三:B 树。 B 树也是多路的,一个节点放很多 key,已经矮了很多。但 B 树的非叶子节点也存整行数据,一行 1KB 的话,一页只能放 15 行,扇出只有 16。同样存 2190 万行,B 树要 7 层。而且数据分散在每一层,范围查询要在树里上上下下地中序遍历,没法顺着一条链表一路读下去。
  4. 办法四:跳表。 Redis 的 ZSet 就用跳表,有序、实现简单。但跳表的层高是随机的,节点之间靠指针随意跳,没法把「一个节点 = 一页」对齐到磁盘页上,每跳一次都可能是一次随机 IO。它适合内存,不适合磁盘。

存 2190 万行,树要多高:25 层 vs 7 层 vs 3 层

四个办法摆在一起,B+ 树做对的事情就清楚了:

  • 非叶子页只存 key,一页塞下 1170 个分叉,树就变得极矮:2190 万行,3 层;
  • 数据全部在叶子,叶子有序且串成链表,范围查询定位到起点后顺着链表往后读,between 30 and 50 只读 3 个叶子页,读出来天然就是有序的。

范围查询:hash 只能全扫,B+ 树顺着叶子链表走

B+ 树的精髓可以压成一句话:矮胖的目录 + 有序成链的叶子。「矮胖」让点查只需要 3 次左右的磁盘 IO,「有序成链」让范围查询变成顺序读。hash 有前者没有后者,红黑树和跳表有后者没有前者,B 树两样都只做到一半。

想通这一点,B+ 树的其它优点就都是推论了:查询性能稳定(任何一行都在叶子,路径长度一样)、全表扫描只要顺着叶子链表扫一遍、非叶子页小而热,很容易整个缓存在内存里。

落到业务里:主键、回表和最左前缀

理解了「矮胖 + 有序」,很多大家耳熟能详的 MySQL 规范,就都能自己推出来了。

为什么推荐自增主键,不推荐 UUID? 除了上一节说的「UUID 太长、扇出小」,还有一个更要命的问题:插入位置。自增 id 一个比一个大,新行永远追加在最右边那个叶子页的末尾,前面写满的页再也不会被动。UUID 是随机的,新行可能要插进任何一个已经满了的页中间,InnoDB 只好把这一页分裂成两页,各留一半空间,还要去上一层改指针。

主键怎么选:顺序写只追加,随机写会把页撑裂

后果是写入时频繁分裂、随机 IO 变多,页里留下大量空洞,同样的数据要占更多页。更隐蔽的是,每一个二级索引的叶子里都存着主键,主键从 8 字节的 bigint 变成 36 字节的字符串,一张表有 5 个二级索引,就有 5 份这样的膨胀。业务确实需要全局唯一 id 时,大家常用的是雪花算法这类「整体递增」的 bigint,就是同时照顾了唯一性和顺序写。

为什么 select * 有时比 select id, nickname 慢一大截? 假设在 nickname 上建了索引:

-- 二级索引的叶子里有 nickname 和主键 id,直接返回,不用回表(覆盖索引)
select id, nickname from user where nickname = 'leikooo';

-- 还要其它列:先在二级索引里拿到 id,再回聚簇索引走一遍 B+ 树取整行(回表)
select * from user where nickname = 'leikooo';

回表等于再走一次三层的树。查一行无所谓,where nickname like 'lei%' 命中一万行,就是一万次回表,而且这一万个主键往往是乱序的,每次都可能落在不同的页上。如果要的列都在索引里,就叫覆盖索引,explain 的 Extra 里会显示 Using index。

为什么联合索引要讲「最左前缀」? 联合索引 (city, age) 的叶子,是先按 city 排,city 相同再按 age 排,就像电话簿先按姓排、同姓再按名排:

查询条件 能不能用索引 原因
city = '北京' 能 所有北京的行在叶子里挨在一起
city = '北京' and age > 18 能 北京这一段里,age 也是有序的
age > 18 不能直接定位 age 只在同一个 city 内部有序,整体看是乱的

这和电话簿一样:知道姓张,能一下翻到张姓那几页;只知道名叫「伟」,就只能从头翻到尾。说到底,B+ 树只能利用「有序」,哪一列在全局上有序,就只能从哪一列开始用。

最后回到开头的问题:

  • 是什么:索引是一份按 key 排好序的目录,InnoDB 用 B+ 树来存它,表本身就是一棵按主键组织的 B+ 树;
  • 怎么做:从根页往下,每层读一页,16KB 的页能放 1170 个分叉,三层就能装下约 2190 万行;
  • 为什么:磁盘按页读、随机 IO 贵,B+ 树用「矮胖的目录 + 有序成链的叶子」,同时把点查压到 3 次 IO 左右、把范围查询变成顺序读。

所以开头那张两千多万行的表,where id = 12345 只是在一棵三层的树上往下走了三步;而 where nickname = 'leikooo' 慢,是因为 nickname 没有自己的那份目录,只能一页一页地翻完整本书

目录
相关文章
|
6天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
7071 17
|
6天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2341 10
|
8天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
8天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
4天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
21天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
10231 59
|
4天前
|
人工智能 弹性计算 开发工具
零成本玩各大模型!DeepSeek Harness dsh-our-free-model 插件,13 个厂商模型直接用
总结一下:装这个插件,你不用注册、不用绑卡、不用填一个 Key,就能在 DeepSeek Harness 里用上 DeepSeek V4.1 Flash、Kimi K3 这一批前沿模型,而且是白嫖的、还不限量。三步搞定:下载插件,复制包含 `package.json` 的插件目录路径,在「添加插件」里粘贴路径安装并重启。无论是在阿里云 ECS 上通过命令行部署的 Web 版,还是本地的 Electron 桌面端,都能顺利跑通,快速搭建一套零成本的免费模型使用环境。
1060 1
|
7天前
|
Linux API iOS开发
【DSH】DeepSeek Harness新手保姆教程(下载+安装+配置+使用,2026最新实测)
DeepSeek Harness(dsh)是DeepSeek AI开源的智能体框架,秉持“一切皆插件”理念,支持读文件、改代码、跑命令、处理表格、联网搜索等操作。免费开源,兼容Windows/macOS/Linux,提供桌面端与网页端,可灵活安装插件扩展能力。
|
16天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3501 9