MySQL 索引为什么用 B+ 树？从 B 树、Hash、红黑树讲起-云帆数科

先给结论因为磁盘。索引结构的所有设计权衡最后都归结到一件事怎么把一次查询需要的磁盘 IO 次数压到最低。理解了这条B 树的每个设计点都能自己推出来。如果把数据全放进内存B 树未必是最优解。Redis 的有序集合用的是跳表没用 B 树是因为它压根不走磁盘。反过来看这个对照恰恰证明了 B 树是为磁盘量身定做的。一次真实的慢查询说起这个我想起一个 case。一张订单表3000 万行主键查询正常走的是 secondary index 的时候偶发 1.2 秒。第一反应当然是索引没生效。但看执行计划type 是 refrows 只有 40 多行索引用上了。真正的原因在别处走了二级索引之后要拿着主键值回表去聚簇索引里捞整行数据而那 40 行散落在 40 个不同的页里。40 次随机 IO而机械盘一次约 10ms加起来就接近 400ms 了。后来改成覆盖索引不需要回表直接降到了 8ms。这个 case 说明的就是本文的主题理解的单位是页是 IO 次数不是比较了几次字符串。有了这个视角下面所有的取舍都会变得很自然。逐个排除为什么不是这几种Hash 为什么不行Hash 做等值查找是 O(1)比 B 树的 O(log n) 快得多理论上更优。MySQL 也确实支持 Hash 索引——Memory 引擎就是用 HashInnoDB 还有个自适应哈希索引AHI不过那个是 InnoDB 自己偷偷建的你没法手动指定。它不能当主力卡在四点不定范围查询。Hash 之后的值是无序的where id 100 and id 200 这种只能全表扫。而范围查询在线上业务里占比不低。搞不定排序。order by 用不上索引只能额外排序。最左前缀原则失效。联合索引里 Hash 是把整个 key 拼起来算的只用左边部分字段就查不了。冲突代价不可控。冲突会退化成链表遍历而数据量增大会让冲突变频繁性能没有下限保证。所以Hash 只擅长按这个值找这一条而数据库要应付的场景远不止这一种。二叉树和红黑树排除它们的理由更简单树太高了。红黑树是二叉树每个节点最多两个孩子。100 万行数据红黑树高度大约是 20。如果这个索引长在磁盘上一次比较就可能是一次 IO最坏要 20 次磁盘 IO 才能找到一个值。更麻烦的是平衡操作。红黑树插入要旋转、变色在磁盘结构上做这种调整代价远高于内存。有人说 AVL 树更平衡、高度更低。问题是它为了维持严格平衡插入时的旋转次数比红黑树还多。在读多写少的理想场景里 AVL 更优但数据库不能假设写入很少。那 B 树呢它已经很接近了到这一步才进入正题。B 树是多路平衡查找树一个节点可以有几十上百个孩子高度一下就降下来了。但 InnoDB 还是没选它用的是 B 树。差别在两点差别一数据搁哪儿B 树的每个节点都存数据整行非叶子节点也存。B 树只有叶子节点存数据非叶子节点只存索引键和指针不存数据。这个差别带来的连锁反应很关键。InnoDB 一页默认 16KB。如果非叶子节点要塞整行数据能放的节点数就少扇出fan-out就低树就高。而 B 树的非叶子节点只放键和指针一页能塞进去上千个树的高度自然就被压扁了。差别二叶子之间连不连B 树的叶子节点之间有一条双向链表串起来的。B 树没有叶子彼此独立。这条链表是范围查询的胜负手。B 树做范围查询找到起点之后顺着链表往后扫就行了不用再回到父节点。B 树要做中序遍历得在树的不同层之间来回跳中途还要回溯会产生大量随机 IO。顺带说一句这也是为什么 MySQL 的叶子节点是双向链表而不是单向——order by desc 倒着扫的时候数据也能用到。算个数三层树能存多少行这一段建议直接记下来面试官很喜欢问。InnoDB 页默认 16KB。假设主键是 bigint8 字节指针按 6 字节算一个非叶子页能放 16 * 1024 / (8 6) ≈ 1170 个指针一个叶子页装的完整行假设一行 1KB → 16 行那三层树能索引多少行1170 × 1170 × 16 21,902,400**约 2100 万行**。两千万左右的数据量三次磁盘 IO 就能定位到某一行。而且因为根节点几乎肯定被缓存在内存里实际往往只有 2 次 IO。这就是索引为什么快的数字答案。它不神秘就是算术加上两个设计选择让非叶子节点只存索引、让叶子节点串成链表。面试官在等的那句到这里普通候选人讲完了多路、矮、链表。如果停在这面试官会客套地点点头然后换下一题。真正拉开差距的是这一句B 树的查询复杂度是不稳定的——运气好要找的数据就在根节点一次命中运气不好得一路走到最深的叶子。最坏情况下两者差距很大。B 树强制每次查询都落到叶子节点查询路径长度固定复杂度稳定是 O(log n)。线上系统要的不是平均更快而是延迟可预测。这句话的价值在于它说明你不是从书上抄答案而是真正想过生产环境要什么。稳定比快更重要这是运维和 DBA 视角才有的判断。四个常见的错误答案错误一只说B 树是多路平衡查找树这是教科书定义不是对这个问题的回答。面试官问的是为什么是它你要回答的是取舍不是名词解释。错误二说B 树一定比 B 树快不准确。单条等值查询B 树可能更快因为数据可能在高层就命中了不用走到叶子。B 树赢在**范围查询**和**整体稳定**不是赢在每一次单点查询上。错误三以为 InnoDB 的索引只有一种InnoDB 除了 B 树还有自适应哈希索引AHI全自动、不可干预、全文索引倒排。面试时提一句 AHI能证明你知道体系边界在哪。错误四把 B 树和 Hash 当成互斥关系它们不是替代关系。InnoDB 在一定条件下会给热点页自动加 AHI是两套机制并存。标准答法可以直接背MySQL 选 B 树核心是为了减少磁盘 IO。相比二叉树和红黑树它是多路的树高被压到很低千万级数据只需 2~3 次 IO相比 Hash它支持范围查询、排序和最左前缀相比 B 树它的非叶子节点只存索引键不存数据扇出更高且叶子节点之间用双向链表相连范围查询不用回溯。另外 B 树的查询路径长度固定每次都落到叶子复杂度稳定。生产环境要的是延迟可预测这一点比平均性能更重要。说完这段如果面试官还想继续聊大概率会顺着往下问联合索引、回表、覆盖索引那几个坑。一个还没聊完的问题有个细节我一直没找到特别好的解释InnoDB 为什么死守 16KB 的页大小而不是像某些数据库那样做成可配置的官方文档给的理由是和历史兼容性有关。但如果从 SSD 随机读特性出发重新设计16KB 未必还是最优解。你在生产中调过页大小吗或者遇到过因为页大小导致的问题评论区聊聊。

企业数字化 ERP 产品动态

相关推荐

官方扩展被投毒11小时：5000台开发机装上SSH后门，自动更新与主机取证怎么补

11 小时窗口：官方 ID、官方渠道、官方签名2026 年 10 月 29 日，Cursor 在自己的扩展市场里发现了一件不该发生的事：Anthropic.claude-code 的 2.1.312 与 2.1.313 两个版本被人改过，装进去的是一套持久化 SSH 后门。恶意版本从当天… · 2026/11/2 15:27:00

WordPress 表单显示「提交成功」但收不到邮件：先核 SMTP 与 wp_mail，再查垃圾箱与主机出站端口

前台 Contact Form / WPForms / Fluent Forms 已经弹出「提交成功」，后台询盘列表里也有一条新记录，但「站点管理员邮箱」和「收件测试地址」两边都空——这和今天写过的「登录 Cookie / CDN 循环」「Elementor 空白」「502/503」「Fatal 白屏」「Shopif… · 2026/11/2 15:27:00

java开发心得

曾有人说Java于2026年已死，但我不信立个flag在此，并整理工作经验于此，供大家缅怀，如果大家喜欢，请加入粉丝以供鼓励一、Java入门1.如何理解产品需求2.Java常用概念3.SSM框架4.中间件5.数据库6.Spring Cloud 核心组件7.… · 2026/11/2 15:27:00

Paperclip：轻量级AI工作流胶合层设计与Node.js+React落地实践

1. 项目概述：Paperclip 不是回形针，而是一个被严重误读的 AI 工程实践入口“Paperclip”这个词在中文技术社区里，最近半年正经历一场诡异的语义漂移。它不再指代办公桌上那个弯折金属丝制成的物理小物件，而是悄然演变成一个高频混… · 2026/11/3 14:22:20

Paperclip：本地AI协作胶水层原理与实践

1. “Paperclip”不是回形针：一个被严重误读的开源项目代号最近在多个技术社区和开发者群聊里，频繁看到有人问：“Paperclip 是不是 Ruby on Rails 里的那个文件上传 gem？”“Paperclip 支持 React 吗？”“有没有 Pape… · 2026/11/3 14:22:20

电商高并发架构实战：从分层设计到稳定性保障

1. 电商网站架构的核心挑战当订单量突破每秒1000单时，你会发现原本运行良好的系统开始出现各种诡异问题——购物车突然清空、支付结果不同步、库存显示超卖。这不是代码bug，而是架构设计到了必须重构的临界点。我经历过三次这样的架构升级，从… · 2026/11/3 14:22:20

多维数据集增量处理原理与实战优化

1. 增量处理多维数据集的核心价值在商业智能领域，我们每天都要面对一个现实问题：数据量在持续增长，但决策时效性要求越来越高。传统全量刷新多维数据集的方式，在数据量达到TB级别时往往需要数小时甚至更长时间，这显然… · 2026/11/3 14:22:20

eVTOL与城市空中交通：技术突破与商业落地

1. 城市空中交通的产业变革信号上周在深圳机场附近，我亲眼目睹了一场电动垂直起降飞行器（eVTOL）的试飞。这个形似放大版无人机的家伙，在150米高度完成转向时几乎无声，和想象中直升机轰鸣的场景完全不同。这个瞬间让我意… · 2026/11/3 14:22:20

红外小目标检测：TDC技术原理与PyTorch实现

1. 项目概述：红外小目标检测的技术挑战与TDC创新红外小目标检测（Infrared Small Target Detection, IRSTD）是计算机视觉领域一个极具挑战性的研究方向。在无人机侦察、搜索救援等实际应用场景中，我们需要从复杂的红外图像背景中检… · 2026/11/3 14:21:19

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

STM32F411RE与MAX14431实现SPI隔离：工业现场抗共模干扰实战

ESP32+大模型AI硬件开发：从Demo到产品的8个工程问题

基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

MySQL 索引为什么用 B+ 树？从 B 树、Hash、红黑树讲起

相关推荐

了解更多？预约专属演示