mysql索引的数据结构

MySQL索引的数据结构：面试必问的底层原理剖析

作为程序员，面试中被问「MySQL为什么用B+树做索引？」几乎是必考题。今天我们就从数据结构的角度，掰开揉碎讲清楚它的设计逻辑，帮你轻松拿下这类面试题！

一、索引的核心作用：加速查询

想象一下，数据库表是一本字典，索引就是目录。没有索引时，查询只能逐行扫描（全表扫描），效率极低。而索引通过特定的数据结构组织关键字段，让查找时间从O(n)降到O(log n)。

二、备选数据结构为什么被淘汰？

1️⃣ 哈希表

哈希表查询速度是O(1)，但它有致命缺点：

• 无法范围查询（如WHERE id > 100）
• 数据无序，排序操作需额外计算
• 哈希冲突影响性能

面试话术：
“哈希索引适合等值查询（如=），但实际业务中范围查询、排序操作更常见，所以InnoDB不用它做主索引”

2️⃣ 二叉搜索树 (BST)

BST的查询复杂度是O(log n)，但存在两大问题：

• 退化成链表：当插入顺序有序时，树高度激增
• 磁盘IO高：每次比较可能触发磁盘读取（数据库数据在磁盘）

关键结论：
索引要尽量减少磁盘I/O次数，而BST的树高不可控，显然不满足

3️⃣ B树 (多路平衡树)

B树通过一个节点存储多个数据+指针降低树高度：

但B树仍有缺陷：

• 非叶子节点也存数据，导致单页能存的指针数减少
• 范围查询需回溯，跨节点遍历效率低

三、B+树：MySQL的终极选择

B+树在B树基础上做了两项关键改进：

1. 非叶子节点只存索引键和指针，不存数据
   → 单页可容纳更多指针，树高进一步降低
2. 叶子节点用双向链表串联
   → 范围查询直接遍历链表，无需回溯父节点

B+树实操优势拆解

| 场景 | B树 | B+树 |
|---------------|---------------------|---------------------|
| 单行查询 | 可能中途命中返回 | 必须到叶子节点 |
| 范围查询 | 需跨层回溯 | 链表直接遍历 |
| 磁盘I/O | 节点数据多I/O量大 | 非叶子节点更轻量 |
| 全表扫描 | 需遍历所有节点 | 遍历叶子链表即可 |

高频面试题：
Q：为什么B+树比B树更适合数据库？
A：核心是两点：一是非叶子节点不存实际数据，使得单页能放更多索引键，降低树高（减少磁盘I/O）；二是叶子节点链表结构让范围查询和全表扫描更高效。

四、索引使用避坑指南

即使懂了数据结构，索引 misuse 仍是性能杀手：

1. 最左前缀原则：联合索引(a,b,c)
   • 能命中：WHERE a=1, WHERE a=1 AND b=2
   • 不命中：WHERE b=2, WHERE c=3
2. 避免索引失效：
   • 对索引列做计算：WHERE id+1=100 ❌
   • 类型隐式转换：WHERE name=123（name是varchar）❌

---

🚀 高效准备面试：
2025年Java面试宝典（点击下载，含MySQL调优、并发编程等高频考点）

需要购买面试鸭会员？通过👉 面试鸭返利网 👈找我下单，立返25元！已有300+程序员成功薅羊毛~

返回面试鸭返利网首页