引言 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] ↑ 双向链表 ↑ 特点： ...
引言 索引是数据库性能优化的关键。理解索引的本质，才能正确使用索引。 一、没有索引的查询 1.1 全表扫描 -- 查询id=1000的用户（无索引） SELECT * FROM users WHERE id = 1000; 执行过程： 从第1行开始 逐行检查id是否等于1000 找到后返回 如果表有100万行，最坏情况需要扫描100万行 时间复杂度：O(n) 1.2 问题 查询慢（全表扫描） 资源消耗大（CPU、磁盘IO） 并发性能差 二、索引的本质 2.1 从二分查找说起 # 在有序数组中查找 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 时间复杂度：O(log n) 关键：数据有序 + 快速定位 2.2 索引的原理 索引是一种排序的数据结构，存储列值和行位置的映射。 索引结构（简化示例）： +-------+-----------+ | id值 | 行位置 | +-------+-----------+ | 1 | 0x1000 | | 10 | 0x1050 | | 100 | 0x1100 | | 1000 | 0x2000 | <-- 通过索引快速定位 +-------+-----------+ 查询过程： ...
引言：索引的魔法 如果说 CommitLog 是一本厚厚的字典，那么 ConsumeQueue 和 IndexFile 就是目录和索引。它们让 RocketMQ 能够： 秒级定位：从百万条消息中快速找到目标 轻量高效：索引占用空间极小 多维查询：支持按 Queue、Key、时间查询 今天我们深入剖析这两种索引的巧妙设计。 一、为什么需要索引？ 1.1 没有索引的困境 场景：Consumer 想消费 TopicA 的消息 方案1：遍历 CommitLog（❌） ┌────────────────────────────────────┐ │ CommitLog（所有Topic混存） │ ├────────────────────────────────────┤ │ TopicA-Msg1 │ │ TopicB-Msg1 │ ← 需要跳过 │ TopicC-Msg1 │ ← 需要跳过 │ TopicA-Msg2 │ │ TopicB-Msg2 │ ← 需要跳过 │ ... │ └────────────────────────────────────┘ 问题： 1. 需要扫描所有消息 → 慢 2. 无法按 Queue 过滤 → 低效 3. 无法快速定位 Offset → 不可用 1.2 RocketMQ 的索引方案 ┌─────────────────────────────────────────────┐ │ 双层索引架构 │ ├─────────────────────────────────────────────┤ │ │ │ ConsumeQueue（消费索引） │ │ - 按 Topic-Queue 组织 │ │ - 存储消息在 CommitLog 的位置 │ │ - 支持顺序消费 │ │ │ │ IndexFile（查询索引） │ │ - 按 Key/时间 组织 │ │ - Hash 索引结构 │ │ - 支持随机查询 │ │ │ └─────────────────────────────────────────────┘ 二、ConsumeQueue：消费索引 2.1 文件组织结构 $HOME/store/consumequeue/ ├── TopicA/ # Topic 名称 │ ├── 0/ # Queue ID = 0 │ │ ├── 00000000000000000000 # 第1个文件 │ │ ├── 00000000000600000000 # 第2个文件 │ │ └── ... │ ├── 1/ # Queue ID = 1 │ │ └── ... │ └── ... ├── TopicB/ │ └── ... └── ... 文件大小：600万字节（30万条索引 × 20字节） 文件名：该文件第一条索引的逻辑偏移量 2.2 索引格式 ┌────────────────────────────────────┐ │ 单条索引格式（20字节） │ ├────────────────────────────────────┤ │ CommitLog Offset (8字节) │ ← 消息在 CommitLog 的物理位置 │ Size (4字节) │ ← 消息大小 │ Tag HashCode (8字节) │ ← Tag 哈希值（用于过滤） └────────────────────────────────────┘ 实际示例： ...
引言 “计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。” —— 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数据 性能分析: ...
如约数科科技工作室