: 索引为什么用 B+ 树？ 一文讲透)
前言在面试中几乎必问的一个问题是“MySQL 的索引为什么使用 B 树” 很多同学能答出“减少IO”、“叶子节点存储数据”等关键词但往往不够深入。本文将抛开晦涩的学术定义从数据结构、磁盘IO、范围查询、实际存储等角度彻底把这个问题讲清楚。一、索引的本质一个“目录”想象一下你要在一本新华字典里查找“张”这个字。如果没有目录你需要一页一页翻效率极低全表扫描。有了目录拼音检字表你可以直接定位到“Z”部分然后快速找到页码索引查找。数据库索引的本质就是一种数据结构它帮助我们在海量数据中快速定位到目标数据。但问题来了为什么这个“目录”非得是 B 树而不是哈希表、二叉树、AVL 树或 B 树二、淘汰赛为什么不选其他数据结构1. 哈希表哈希表查询速度极快O(1) 的时间复杂度。但淘汰原因不支持范围查询。WHERE id 10这样的 SQL哈希表无法处理只能全表扫描。不支持排序。存在哈希冲突。不支持模糊查询LIKE。结论哈希表只适用于等值查询的特定场景如 Redis不适合关系型数据库的复杂查询。2. 二叉搜索树 (BST)plaintext5 / \ 3 7 / \ 1 9树太高 → I/O 爆炸淘汰每个节点最多两个分支左小右大。但淘汰原因容易退化成链表。如果插入的数据是递增的如1,2,3,4...二叉树会变成线性结构查询复杂度退化为 O(n)。树太高。数据量一大千万级树高可能达到几十层查找一个数据需要几十次磁盘 IO。3. AVL 树 / 红黑树plaintext5 / \ 3 7 / \ / \ 1 4 6 9平衡树高小一点但每个节点只存 1 个 key大数据量下树依然很高不适合磁盘为了解决 BST 退化问题出现了自平衡的 AVL 树和红黑树。它们能保证树的高度平衡。但淘汰原因还是太高。虽然平衡了但依然是二叉树。在 MySQL 中节点数 数据量。当数据量为 2000 万时树高大约为log2(2000w) ≈ 24层。磁盘 IO 致命每访问一层节点就相当于一次磁盘 IO。24 次 IO 意味着查询需要几十毫秒在高并发下不可接受。核心矛盾内存操作关注“比较次数”磁盘 IO 关注“寻道次数”。在数据库中IO 成本远高于 CPU 计算成本因此必须降低树的高度。三、为什么 B 树也不行plaintext[ 15 30 45 ] / | | \ [5,10] [20,25] [35,40] [50,55]B 树多路平衡查找树是 B 树的前身它解决了二叉树“太高”的问题。B 树的优点多叉一个节点可以存储多个键值和多个子节点指针。在 MySQL 中一个节点通常对应一个磁盘页16KB。在 16KB 的空间里可以存储大量的键值从而让树的高度变得非常低通常 2~4 层。平衡所有叶子节点都在同一层。B 树的缺点为何被 B 树取代数据存储分散B 树的每个节点包括根节点和中间节点都存储了数据或数据的指针。这意味着当你按范围查询如id BETWEEN 10 AND 20时可能需要在中序遍历中来回访问不同层级的节点造成随机 IO。非叶子节点占用空间如果非叶子节点也存储数据那么在 16KB 的页中能存储的键值数量就会变少。导致同样数据量下B 树比 B 树高度更高或者分支更少。四、B 树的王者优势plaintext[ 15 30 45 ] ← 非叶子只存索引key / | | \ [5,10] ↔ [20,25] ↔ [35,40] ↔ [50,55] ← 叶子存完整数据 双向链表B 树在 B 树的基础上做了两个关键优化完美契合了磁盘预读和范围查询的需求。1. 结构特点数据只存在叶子节点非叶子节点只存储键值索引列的值和指向子节点的指针不存储数据。叶子节点形成有序链表所有叶子节点之间通过双向指针连接构成了一个有序链表。2. 优势分析优势一查询性能极其稳定由于数据只存在于叶子节点任何查询无论单行还是范围都必须走到叶子节点才能拿到数据。因此所有查询的 IO 次数都等于树的高度。这使得 B 树的查询效率非常稳定不会出现“运气好查根节点运气差查叶子节点”的情况。优势二极大的“出度”树高极低假设主键 ID 为bigint占用 8 字节。指针大小在 InnoDB 中约为 6 字节。一个非叶子节点的一条索引条目大约占8614字节。磁盘一个数据页默认为 16KB16384 字节。那么一个非叶子节点可以存储的索引条目数量为16384/14≈1170 条16384/14≈1170 条也就是说一个 3 层的 B 树根节点存储 1170 条记录。第二层1170 个节点每个节点再存 1170 条共 1170×1170≈136万1170×1170≈136万 条。叶子节点假设每行数据包括行记录占用 1KB那么一个叶子节点可存 16 条数据。总存储数据量136万×16≈2176万 条数据136万×16≈2176万 条数据结论2000 万条数据B 树的高度仅为3层这意味着查找一条数据最多只需要3 次磁盘 IO根节点常驻内存实际往往只需要 2 次 IO。这是 B 树无法比拟的。优势三范围查询无敌这是 B 树最惊艳的特性。因为叶子节点是有序链表当你执行sqlSELECT * FROM user WHERE age BETWEEN 18 AND 25;过程如下利用树结构快速定位到age18所在的叶子节点3 次 IO。沿着叶子节点的链表向后遍历直到age25为止。不需要再回到非叶子节点查找。如果使用 B 树范围查询可能需要不断回溯到父节点导致大量的随机 IO。优势四更好的磁盘预读磁盘读取数据时不是按需读取而是预读读取一整页。由于 B 树的非叶子节点只存索引不存数据同一个磁盘页能容纳的索引条目更多。操作系统或数据库在读取一个节点时加载到内存的是一整页16KB的索引相当于一次性把几百上千个索引值加载到内存中减少了后续的 IO 请求。五、结合 InnoDB 存储引擎深入理解在 MySQL 的 InnoDB 引擎中B 树的实现更加精妙。1. 聚簇索引InnoDB 的数据文件.ibd本身就是一颗 B 树。叶子节点存储完整的一行数据所有列。非叶子节点存储主键 ID 和页指针。这意味着表必须有一个主键如果没有显式定义InnoDB 会自动生成一个隐藏的ROW_ID作为主键。2. 二级索引辅助索引二级索引也是 B 树结构但它的叶子节点不存储完整数据只存储主键值。回表通过二级索引查到主键后再去聚簇索引中查数据的过程。3. 为什么自增主键性能好顺序插入自增主键保证插入的数据总是在 B 树的最右边只需要不断追加新的叶子节点或者分裂极少的数据页。页分裂如果使用 UUID 这种无序的值作为主键插入时会导致 B 树频繁地页分裂不仅性能差还会造成磁盘碎片。六、总结数据结构是否适合 MySQL 索引原因哈希表❌不支持范围查询、排序、模糊查询二叉树❌树高太高可能退化为链表AVL/红黑树❌树高仍然太高logNIO 次数多B 树⚠️非叶子节点存数据出度小范围查询需回溯B 树✅出度大树高 3-4 层、范围查询快链表、查询稳定、完美适配磁盘预读一句话总结B 树通过非叶子节点只存索引实现了极大的出度降低树高通过叶子节点存数据链表实现了高效的范围查询完美平衡了磁盘 IO 成本和查询效率因此成为 MySQL 索引的终极选择。写在最后理解 B 树不仅仅是应付面试更是理解 MySQL 性能优化的基础。当你明白了为什么用 B 树你就能自然理解为什么主键要选择自增为什么不要建立过多的索引为什么大字段不适合建索引为什么联合索引要遵循最左前缀原则如果你觉得本文对你有帮助欢迎点赞、收藏、评论一键三连支持作者
MySQL面试(2): 索引为什么用 B+ 树？ 一文讲透
发布时间：2026/5/19 10:50:09
前言在面试中几乎必问的一个问题是“MySQL 的索引为什么使用 B 树” 很多同学能答出“减少IO”、“叶子节点存储数据”等关键词但往往不够深入。本文将抛开晦涩的学术定义从数据结构、磁盘IO、范围查询、实际存储等角度彻底把这个问题讲清楚。一、索引的本质一个“目录”想象一下你要在一本新华字典里查找“张”这个字。如果没有目录你需要一页一页翻效率极低全表扫描。有了目录拼音检字表你可以直接定位到“Z”部分然后快速找到页码索引查找。数据库索引的本质就是一种数据结构它帮助我们在海量数据中快速定位到目标数据。但问题来了为什么这个“目录”非得是 B 树而不是哈希表、二叉树、AVL 树或 B 树二、淘汰赛为什么不选其他数据结构1. 哈希表哈希表查询速度极快O(1) 的时间复杂度。但淘汰原因不支持范围查询。WHERE id 10这样的 SQL哈希表无法处理只能全表扫描。不支持排序。存在哈希冲突。不支持模糊查询LIKE。结论哈希表只适用于等值查询的特定场景如 Redis不适合关系型数据库的复杂查询。2. 二叉搜索树 (BST)plaintext5 / \ 3 7 / \ 1 9树太高 → I/O 爆炸淘汰每个节点最多两个分支左小右大。但淘汰原因容易退化成链表。如果插入的数据是递增的如1,2,3,4...二叉树会变成线性结构查询复杂度退化为 O(n)。树太高。数据量一大千万级树高可能达到几十层查找一个数据需要几十次磁盘 IO。3. AVL 树 / 红黑树plaintext5 / \ 3 7 / \ / \ 1 4 6 9平衡树高小一点但每个节点只存 1 个 key大数据量下树依然很高不适合磁盘为了解决 BST 退化问题出现了自平衡的 AVL 树和红黑树。它们能保证树的高度平衡。但淘汰原因还是太高。虽然平衡了但依然是二叉树。在 MySQL 中节点数 数据量。当数据量为 2000 万时树高大约为log2(2000w) ≈ 24层。磁盘 IO 致命每访问一层节点就相当于一次磁盘 IO。24 次 IO 意味着查询需要几十毫秒在高并发下不可接受。核心矛盾内存操作关注“比较次数”磁盘 IO 关注“寻道次数”。在数据库中IO 成本远高于 CPU 计算成本因此必须降低树的高度。三、为什么 B 树也不行plaintext[ 15 30 45 ] / | | \ [5,10] [20,25] [35,40] [50,55]B 树多路平衡查找树是 B 树的前身它解决了二叉树“太高”的问题。B 树的优点多叉一个节点可以存储多个键值和多个子节点指针。在 MySQL 中一个节点通常对应一个磁盘页16KB。在 16KB 的空间里可以存储大量的键值从而让树的高度变得非常低通常 2~4 层。平衡所有叶子节点都在同一层。B 树的缺点为何被 B 树取代数据存储分散B 树的每个节点包括根节点和中间节点都存储了数据或数据的指针。这意味着当你按范围查询如id BETWEEN 10 AND 20时可能需要在中序遍历中来回访问不同层级的节点造成随机 IO。非叶子节点占用空间如果非叶子节点也存储数据那么在 16KB 的页中能存储的键值数量就会变少。导致同样数据量下B 树比 B 树高度更高或者分支更少。四、B 树的王者优势plaintext[ 15 30 45 ] ← 非叶子只存索引key / | | \ [5,10] ↔ [20,25] ↔ [35,40] ↔ [50,55] ← 叶子存完整数据 双向链表B 树在 B 树的基础上做了两个关键优化完美契合了磁盘预读和范围查询的需求。1. 结构特点数据只存在叶子节点非叶子节点只存储键值索引列的值和指向子节点的指针不存储数据。叶子节点形成有序链表所有叶子节点之间通过双向指针连接构成了一个有序链表。2. 优势分析优势一查询性能极其稳定由于数据只存在于叶子节点任何查询无论单行还是范围都必须走到叶子节点才能拿到数据。因此所有查询的 IO 次数都等于树的高度。这使得 B 树的查询效率非常稳定不会出现“运气好查根节点运气差查叶子节点”的情况。优势二极大的“出度”树高极低假设主键 ID 为bigint占用 8 字节。指针大小在 InnoDB 中约为 6 字节。一个非叶子节点的一条索引条目大约占8614字节。磁盘一个数据页默认为 16KB16384 字节。那么一个非叶子节点可以存储的索引条目数量为16384/14≈1170 条16384/14≈1170 条也就是说一个 3 层的 B 树根节点存储 1170 条记录。第二层1170 个节点每个节点再存 1170 条共 1170×1170≈136万1170×1170≈136万 条。叶子节点假设每行数据包括行记录占用 1KB那么一个叶子节点可存 16 条数据。总存储数据量136万×16≈2176万 条数据136万×16≈2176万 条数据结论2000 万条数据B 树的高度仅为3层这意味着查找一条数据最多只需要3 次磁盘 IO根节点常驻内存实际往往只需要 2 次 IO。这是 B 树无法比拟的。优势三范围查询无敌这是 B 树最惊艳的特性。因为叶子节点是有序链表当你执行sqlSELECT * FROM user WHERE age BETWEEN 18 AND 25;过程如下利用树结构快速定位到age18所在的叶子节点3 次 IO。沿着叶子节点的链表向后遍历直到age25为止。不需要再回到非叶子节点查找。如果使用 B 树范围查询可能需要不断回溯到父节点导致大量的随机 IO。优势四更好的磁盘预读磁盘读取数据时不是按需读取而是预读读取一整页。由于 B 树的非叶子节点只存索引不存数据同一个磁盘页能容纳的索引条目更多。操作系统或数据库在读取一个节点时加载到内存的是一整页16KB的索引相当于一次性把几百上千个索引值加载到内存中减少了后续的 IO 请求。五、结合 InnoDB 存储引擎深入理解在 MySQL 的 InnoDB 引擎中B 树的实现更加精妙。1. 聚簇索引InnoDB 的数据文件.ibd本身就是一颗 B 树。叶子节点存储完整的一行数据所有列。非叶子节点存储主键 ID 和页指针。这意味着表必须有一个主键如果没有显式定义InnoDB 会自动生成一个隐藏的ROW_ID作为主键。2. 二级索引辅助索引二级索引也是 B 树结构但它的叶子节点不存储完整数据只存储主键值。回表通过二级索引查到主键后再去聚簇索引中查数据的过程。3. 为什么自增主键性能好顺序插入自增主键保证插入的数据总是在 B 树的最右边只需要不断追加新的叶子节点或者分裂极少的数据页。页分裂如果使用 UUID 这种无序的值作为主键插入时会导致 B 树频繁地页分裂不仅性能差还会造成磁盘碎片。六、总结数据结构是否适合 MySQL 索引原因哈希表❌不支持范围查询、排序、模糊查询二叉树❌树高太高可能退化为链表AVL/红黑树❌树高仍然太高logNIO 次数多B 树⚠️非叶子节点存数据出度小范围查询需回溯B 树✅出度大树高 3-4 层、范围查询快链表、查询稳定、完美适配磁盘预读一句话总结B 树通过非叶子节点只存索引实现了极大的出度降低树高通过叶子节点存数据链表实现了高效的范围查询完美平衡了磁盘 IO 成本和查询效率因此成为 MySQL 索引的终极选择。写在最后理解 B 树不仅仅是应付面试更是理解 MySQL 性能优化的基础。当你明白了为什么用 B 树你就能自然理解为什么主键要选择自增为什么不要建立过多的索引为什么大字段不适合建索引为什么联合索引要遵循最左前缀原则如果你觉得本文对你有帮助欢迎点赞、收藏、评论一键三连支持作者
