没有索引的世界有多可怕#

假设你有一本1000页的电话簿，要找「张三」的电话号码。如果没有目录（索引），你只能一页一页翻——这就是数据库里的「全表扫描」（Full Table Scan）。每次查询都要把所有数据读一遍，时间复杂度是 $O(n)$。

当 n = 一亿的时候，哪怕每条记录只读1微秒，也要100秒。这在线上服务里是完全不可接受的。

B+树：数据库索引的核心#

几乎所有主流关系型数据库（MySQL、PostgreSQL、Oracle）的默认索引结构都是 B+树。B+树长这样：

• 只有叶子节点存数据：非叶子节点只存索引键，不存实际数据行
• 叶子节点之间用链表连接：所以范围查询（BETWEEN、>、<）特别快
• 树的高度极低：因为每个节点可以存很多个键（几百上千个），树非常「矮胖」

为什么 B+树这么快？#

关键在于树的高度。假设每个节点存500个键：

• 高度为 2：最多存 $500 \times 500 = 25$ 万条
• 高度为 3：最多存 $500 \times 500 \times 500 = 1.25$ 亿条

也就是说，查1亿条数据，最多只需要3次磁盘IO！这就是索引魔法的本质。

1
        [100 | 200 | 300]          ← 非叶子节点（只存键）
2
        /    /      \     \
3
    [50,80] [150]  [250]  [350]    ← 非叶子节点
4
     /  \     |      |      |
5
  [实际数据行...]                   ← 叶子节点（存数据 + 链表串联）

索引不是越多越好#

虽然索引很香，但也不能乱建：

• 每建一个索引，写入速度就会变慢——因为每次 INSERT、UPDATE、DELETE 都要维护索引树
• 索引本身占用磁盘空间
• 查询优化器可能选错索引，反而变慢

所以一般在 WHERE、ORDER BY、JOIN 条件中用到的列上建索引就好～

延伸：哈希索引 vs B+树#

你可能想问：为什么不直接用哈希表？哈希查找不是 $O(1)$ 吗？

确实——但哈希索引不支持范围查询。你要查 age BETWEEN 20 AND 30，哈希索引完全没用。B+树的叶子链表天然支持范围扫描，这也是它成为数据库默认索引的原因 💡

好啦～今天的科技小课堂就到这里！下次写 SQL 的时候，记得看看 EXPLAIN 输出了解索引使用情况哦～还有问题评论区见！ 🎀✨

参考资料：《高性能MySQL》（第3版）第5章