B+树

引言 MySQL的InnoDB引擎使用B+树作为索引的数据结构。理解B+树是掌握索引优化的基础。 一、从二叉树到B+树的演进 1.1 二叉查找树（BST） 10 / \ 5 15 / \ / \ 3 7 12 20 问题：可能退化为链表，查询O(n) 1.2 平衡二叉树（AVL） 通过旋转保持平衡，查询O(log n)。 问题： 每个节点只存1个元素 树高度大：100万数据需要20层 磁盘IO次数多（每层一次IO） 1.3 B树 [10, 20, 30] / | | \ [1,5] [12,15] [22,25] [35,40] 特点： 多路：每个节点存多个元素 所有节点都存数据 降低树高度 问题： 非叶子节点也存数据，占用空间 范围查询需要中序遍历 1.4 B+树 非叶子节点（只存索引）： [10, 20, 30] / | | \ / | | \ 叶子节点（存数据+索引）： [1,5,8] → [10,12,15] → [20,22,25] → [30,35,40] ↑ 双向链表 ↑ 特点： ...

引言 “计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。” —— David Wheeler 在上一篇文章《MySQL第一性原理:为什么我们需要数据库?》中,我们了解到MySQL通过索引将查询性能从O(n)提升到O(log n),实现了10万倍的性能飞跃。 但你有没有想过: 为什么索引能这么快? 从1亿条数据中查找一条,只需要3-4次磁盘IO 为什么MySQL选择B+树? 而不是哈希表、二叉搜索树、红黑树? 为什么有些查询用不上索引? WHERE id + 1 = 100 vs WHERE id = 99 联合索引的最左前缀原则是什么? 为什么(user_id, created_time)索引无法优化WHERE created_time > xxx? 今天,我们从第一性原理出发,通过对比5种数据结构,深度剖析MySQL索引的演进历程: 顺序扫描 → 哈希索引 → 二叉搜索树 → B树 → B+树 O(n) O(1) O(log₂n) O(logₘn) O(logₘn) + 顺序IO 1秒 ? ? ? 10微秒 我们还将手写300行代码,实现一个简化版B+树,彻底理解索引的实现原理。 一、问题的起点:全表扫描的性能瓶颈 让我们从一个最简单的查询开始: -- 用户表,1亿条数据 SELECT * FROM users WHERE id = 50000000; 如果没有索引,MySQL会怎么做? 1.1 顺序扫描（Full Table Scan） 执行过程: 1. 从磁盘读取第1页数据（16KB,约100行）→ 判断id是否等于50000000 → 不是 2. 从磁盘读取第2页数据 → 判断 → 不是 3. 从磁盘读取第3页数据 → 判断 → 不是 ... 500000. 从磁盘读取第50万页数据 → 判断 → 是! ✅ 总计:扫描50万页,约8GB数据 性能分析: ...

引言 “计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。” —— David Wheeler 在上一篇文章《MySQL第一性原理:为什么我们需要数据库?》中,我们了解到MySQL通过索引将查询性能从O(n)提升到O(log n),实现了10万倍的性能飞跃。 但你有没有想过: 为什么索引能这么快? 从1亿条数据中查找一条,只需要3-4次磁盘IO 为什么MySQL选择B+树? 而不是哈希表、二叉搜索树、红黑树? 为什么有些查询用不上索引? WHERE id + 1 = 100 vs WHERE id = 99 联合索引的最左前缀原则是什么? 为什么(user_id, created_time)索引无法优化WHERE created_time > xxx? 今天,我们从第一性原理出发,通过对比5种数据结构,深度剖析MySQL索引的演进历程: 顺序扫描 → 哈希索引 → 二叉搜索树 → B树 → B+树 O(n) O(1) O(log₂n) O(logₘn) O(logₘn) + 顺序IO 1秒 ? ? ? 10微秒 我们还将手写300行代码,实现一个简化版B+树,彻底理解索引的实现原理。 一、问题的起点:全表扫描的性能瓶颈 让我们从一个最简单的查询开始: -- 用户表,1亿条数据 SELECT * FROM users WHERE id = 50000000; 如果没有索引,MySQL会怎么做? 1.1 顺序扫描（Full Table Scan） 执行过程: 1. 从磁盘读取第1页数据（16KB,约100行）→ 判断id是否等于50000000 → 不是 2. 从磁盘读取第2页数据 → 判断 → 不是 3. 从磁盘读取第3页数据 → 判断 → 不是 ... 500000. 从磁盘读取第50万页数据 → 判断 → 是! ✅ 总计:扫描50万页,约8GB数据 性能分析: ...