一、索引的本质与数据结构
为什么需要索引？
先问大家一个问题：一本500页的技术书，你想找「B+树」这个知识点，会怎么做？
正常人不会从第1页翻到第500页。你会翻目录，找到对应的页码，直接翻过去。索引，就是数据库的目录。
没有索引的时候，数据库只能做全表扫描。我见过一个真实案例：某电商平台的订单表有2000万行，每次查用户最近订单都要扫全表，耗时8秒多。加了个合适的索引后，降到20毫秒。差了400倍。
说白了，索引的核心价值就两点：
- 快速定位：把O(n)的全表扫描，变成O(log n)的树查找
- 避免排序：索引本身是有序的，order by可以直接用索引
核心观点：索引是空间换时间的典型。它占用额外的磁盘空间，但能大幅提升查询速度。没有索引的数据库，就像没有目录的百科全书——能用，但效率极低。
B+树 vs LSM树
聊索引，绕不开数据结构。目前主流数据库的索引底层，基本就两派：B+树和LSM树。
B+树：关系型数据库的标配
MySQL的InnoDB、PostgreSQL、Oracle，用的都是B+树。为什么大家都选它？
我个人的理解是：B+树太适合磁盘IO了。你想想看，磁盘随机读写很慢，但顺序读写快。B+树的叶子节点是双向链表，范围查询时只需要沿着链表走，顺序读就行。
B+树有几个关键特征：
- 非叶子节点只存键，不存数据。这样每个节点能存更多键，树的高度更低
- 叶子节点存数据，并且用链表串联起来
- 所有数据都在叶子层，查询任何一条数据的IO次数基本一致
举个例子，假设每个节点能存100个键，三层B+树就能存100万条数据。查任何一条数据，最多3次磁盘IO。我在项目中遇到过一张10亿级的订单表，B+树深度也就4层，查询依然很快。
小技巧：B+树的扇出（每个节点能存的键数量）取决于键的大小和页大小。MySQL默认16KB一页，如果键是bigint（8字节），加上指针，一个节点能存上千个键。这就是为什么B+树能撑住海量数据。
LSM树：写优化的利器
LSM树（Log-Structured Merge-Tree）是另一条路。它牺牲了点读性能，换来了极致的写性能。
LSM树的核心思想是：先把数据写到内存里，攒够了再批量刷到磁盘。磁盘写入是顺序的，所以很快。
它的工作流程大致是：
- 写入先到内存的MemTable（一般用跳表实现）
- MemTable满了，冻结成不可变的MemTable，后台刷到磁盘变成SSTable
- 磁盘上的SSTable越来越多，后台线程做合并（Compaction）
Cassandra、HBase、LevelDB、RocksDB都用LSM树。我曾在日志系统里用过RocksDB，每秒写入几十万条毫无压力。但读的时候，如果数据在多个SSTable里，需要合并查询，性能就不如B+树了。
| 特性 | B+树 | LSM树 |
|---|---|---|
| 读性能 | 稳定，O(log n) | 可能较差，需要合并多层 |
| 写性能 | 随机写，较慢 | 顺序写，极快 |
| 空间放大 | 低 | 较高（重复数据多） |
| 写放大 | 低 | 较高（Compaction导致） |
| 典型代表 | MySQL InnoDB, PostgreSQL | Cassandra, HBase, RocksDB |
避坑指南：我曾经帮一个团队排查问题，他们用Cassandra做订单查询，结果读延迟经常飙到几秒。原因就是LSM树的读放大——数据分散在多个SSTable里，查询需要合并。后来加了布隆过滤器，才把无效的SSTable扫描过滤掉。所以选型时一定要想清楚：你的场景是读多还是写多？
聚簇索引与非聚簇索引
这个知识点，我见过太多人搞混了。其实一句话就能说清楚：聚簇索引的叶子节点存的是整行数据，非聚簇索引的叶子节点存的是主键值。
聚簇索引
InnoDB的表，一定会有一个聚簇索引。如果你定义了主键，主键就是聚簇索引。如果你没定义主键，InnoDB会选一个唯一非空索引，或者自己生成一个隐藏的ROW_ID。
聚簇索引的特点：
- 数据即索引，索引即数据。叶子节点就是数据页
- 物理存储顺序和索引顺序一致。按主键范围查询时，数据是连续存放的，IO效率高
- 二级索引（非聚簇索引）的叶子节点存的是主键值，不是数据地址
举个例子：
-- 假设有一张用户表
CREATE TABLE users (
id INT PRIMARY KEY, -- 聚簇索引
name VARCHAR(50),
age INT,
INDEX idx_name (name) -- 二级索引，非聚簇
);
-- 查询走聚簇索引
SELECT * FROM users WHERE id = 100;
-- 直接通过B+树找到id=100的叶子节点，数据就在那里
-- 查询走二级索引
SELECT * FROM users WHERE name = '张三';
-- 先通过idx_name找到name='张三'对应的主键id
-- 再通过主键id回表查询完整数据
-- 这就是所谓的"回表查询"
重要：回表查询意味着两次B+树查找。如果二级索引能覆盖所有需要的字段，就不需要回表。这就是「覆盖索引」的优化思路。
非聚簇索引
MyISAM引擎用的就是非聚簇索引。它的索引和数据是分开存储的：
- .MYI文件存索引，叶子节点存的是数据行的磁盘地址
- .MYD文件存数据，按插入顺序存放
非聚簇索引的叶子节点不存数据，只存一个指针。查询时先找到指针，再根据指针去数据文件里取数据。这其实也是一种「回表」，只不过回的是数据文件。
我个人习惯：生产环境几乎只用InnoDB。MyISAM不支持事务，不支持行锁，崩溃恢复也慢。除非是只读的报表场景，否则别碰它。
| 对比项 | 聚簇索引（InnoDB） | 非聚簇索引（MyISAM） |
|---|---|---|
| 数据存储 | 索引和数据在一起 | 索引和数据分开 |
| 二级索引 | 存主键值，需回表 | 存数据地址，需回数据文件 |
| 主键顺序 | 物理顺序和主键一致 | 物理顺序和插入顺序一致 |
| 范围查询 | 快，数据连续 | 较慢，数据分散 |
| 插入性能 | 主键乱序时可能页分裂 | 直接追加，较快 |
我的建议：设计表时，尽量用自增ID做主键。为什么？因为InnoDB的聚簇索引是按主键顺序存储的。如果用UUID这种随机值做主键，每次插入都可能触发页分裂，性能会急剧下降。我曾经优化过一个表，把UUID主键改成自增ID后，写入性能提升了3倍。
核心知识体系
下面这张图，是我梳理的本章知识脉络。建议你保存下来，后面几章都会用到。
嗯，这一章的内容就到这里。记住一句话：理解索引的本质，就是理解数据是怎么存、怎么找的。B+树和LSM树各有千秋，聚簇和非聚簇各有适用场景。后面几章，我们会深入聊索引的具体使用策略和优化技巧。
本章要点回顾：
- 索引是数据库的目录，核心作用是快速定位和避免排序
- B+树适合读多写少的场景，LSM树适合写多读少的场景
- 聚簇索引的叶子节点存数据，非聚簇索引的叶子节点存主键值或指针
- InnoDB必须有聚簇索引，建议用自增ID做主键
公众号:蓝海资料掘金营，微信deep3321