MySQL 索引按不同维度可以分成多类，底层核心是 B+ 树，配合 哈希索引 做特定场景加速，整体查询时间复杂度为 O(log N)。
索引类型
- 按数据结构：B+ 树索引、哈希索引、全文索引（倒排索引）、空间索引（R-Tree）。
- 按物理存储：聚簇索引（叶子节点存整行数据，InnoDB 主键默认）和非聚簇索引（叶子节点存数据地址或主键值，MyISAM 默认）。
- 按字段特性：主键索引、唯一索引、普通索引、全文索引。
- 按字段个数：单列索引、联合索引（复合索引，遵循最左前缀原则）。
底层实现原理
B+ 树是 MySQL 默认且最核心的索引结构（InnoDB 和 MyISAM 都支持），它的设计目标就是减少磁盘 I/O：
- 非叶子节点只存索引键，不存数据，因此单个节点能容纳大量键值，树高度很低（通常 2~4 层），查询任意数据只需少量磁盘 I/O。
- 所有数据都存在叶子节点，且叶子节点通过有序链表串联，范围查询（
BETWEEN、>、<）和排序效率极高，直接沿链表遍历即可。 - 数据物理有序（聚簇索引下），InnoDB 表数据本身按主键顺序存储在 B+ 树的叶子节点上，主键查询直接定位到行数据。
哈希索引 在 InnoDB 中以“自适应哈希索引”形式存在：当某个索引值被频繁访问时，InnoDB 会在 B+ 树之上自动构建哈希索引，等值查询可以 O(1) 定位，但不支持范围查询，且该过程由引擎自动管理，无法人工干预。
MyISAM 与 InnoDB 的关键差异：MyISAM 的索引叶子节点存的是数据行的物理地址，查到地址后直接取数据；InnoDB 的二级索引叶子节点存的是主键值，需要再回主键索引树查一次（回表查询）。
时间复杂度对比
| 引类型 | 等值查询 | 范围查询 | 排序 | 说明 |
|---|---|---|---|---|
| B+ 树索引 | O(log N) | O(log N + M) | 支持 | M 为结果集大小，InnoDB 默认 |
| 哈希索引 | O(1) | 不支持 | 不支持 | 仅等值，有哈希冲突风险 |
| 全文索引 | O(N) | 不支持 | 不支持 | 倒排索引实现关键词匹配 |
| 无索引全表扫描 | O(N) | O(N) | 不支持 | 性能最差 |
B+ 树查询之所以稳定在 O(log N)，是因为树高可控（通常 3~4 层），百万和千万级数据量下等值查询耗时几乎一致；而哈希索引虽然等值 O(1)，但无法用于范围查询和排序，所以不能作为通用索引结构。
面试/理解要点
- 为什么不用哈希做默认索引：等值查询虽快，但数据库高频操作是范围查询和排序，哈希完全无法支持。
- 为什么不用二叉树/红黑树：数据量巨大时树高过深，每次向下查找都是一次磁盘 I/O，性能急剧下降；B+ 树通过多路分支大幅降低树高。
- 聚簇索引与二级索引：InnoDB 表必有且仅有一个聚簇索引（优先主键）；二级索引查询通常需要回表，覆盖索引可以避免回表，是常见优化手段。
- 联合索引最左前缀：复合索引查询时必须从最左列开始，否则索引失效，这是 B+ 树结构直接决定的。
MySQL 索引按不同维度可以分成好几类，底层最核心的实现是 B+树，InnoDB 引擎下主键索引就是典型的聚簇索引。下面给你按分类讲清楚，再配个例子说明查找过程。
按数据结构分类
- B+树索引：绝大多数存储引擎的默认索引类型，也是 InnoDB 和 MyISAM 最常用的实现方式。数据有序存储，支持等值、范围和排序查询。
- 哈希索引：能以 O(1) 时间复杂度做等值查找，但数据无序，不支持范围查询。InnoDB 有个特殊优化叫“自适应哈希索引”，当某个索引值被频繁访问时，会在 B+树之上自动建一层哈希索引，兼顾两者优点。
- 全文索引：用于在文本列中查找关键词，而不是比较是否相等。底层用倒排索引实现，记录“关键词 → 所在文档”的映射，配合
MATCH AGAINST使用。MyISAM 一直支持，InnoDB 从 MySQL 5.6.4 开始支持。 - 空间数据索引：用于存储地理数据，能从所有维度索引数据，支持任意维度组合查询。MyISAM 支持，MySQL 从 5.7 版本开始支持。
按应用功能分类
- 普通索引：最基本的索引，基于普通字段建立，没有任何限制，创建方式：
CREATE INDEX idx_name ON table(col); - 唯一索引：与普通索引类似，但索引字段的值必须唯一，允许有空值。创建或修改表时加唯一约束会自动创建对应索引。
- 主键索引：一种特殊的唯一索引，不允许有空值。每个表只能有一个主键，InnoDB 中它同时就是聚簇索引。
- 复合索引（联合索引）：在多个列上建立的索引，如
(a, b, c)。相比多个单列索引，复合索引开销更小，但使用时必须遵循最左前缀原则——查询条件从最左列开始连续匹配才能用到索引。
按物理存储分类
- 聚簇索引（聚集索引）：叶子节点直接存储完整行数据，数据物理顺序与索引顺序一致。InnoDB 中主键索引就是聚簇索引，一个表只能有一个。如果没有定义主键，InnoDB 会选第一个非空唯一索引；再没有的话，自动生成一个 6 字节的隐藏主键。
- 非聚簇索引（二级索引/辅助索引）：叶子节点不存完整行数据，只存索引字段值和主键值。通过二级索引查数据时，需要先用主键到聚簇索引里再查一次，这个过程叫回表。MyISAM 的索引叶子节点存的是数据行地址，也属于非聚簇实现。
底层实现原理举例
InnoDB 主键查询：假设有一张用户表user(id, name, age)，id是主键。InnoDB 会把整张表按主键id构建成一棵 B+树，树的叶子节点就是完整的数据行。当执行SELECT * FROM user WHERE id = 5时，从根节点开始二分查找，约 2—3 次磁盘 I/O 就能定位到叶子节点直接取出整行数据，速度非常快。
二级索引回表查询：如果给name建了普通索引，会再生成一棵 B+树，叶子节点存的是(name, id)。执行SELECT * FROM user WHERE name = '张三'时，先在这棵二级索引树里找到id，再用id到主键聚簇索引树里查完整行数据——这就是回表。如果只查SELECT id FROM user WHERE name = '张三'，二级索引里已经有id，不需要回表，这种情况叫覆盖索引，效率更高。
为什么选 B+树而不是其他结构：数据库的瓶颈在磁盘 I/O。二叉树或红黑树每个节点只能存一个 key，数据量大时树很高，查询要多次 I/O；B树虽然能存多个 key，但非叶子节点也存数据，单个节点能容纳的 key 数量有限。B+树的非叶子节点只存索引不存数据，同样大小的节点能存更多 key，树更矮（千万级数据通常 3 层），一次查询只需 2—3 次磁盘 I/O；而且叶子节点用链表串起来，范围查询和排序遍历非常高效。
使用建议
- 主键尽量用自增整型，避免用 UUID 等随机值。随机主键会导致频繁页分裂和碎片，自增主键顺序写入效率最高。
- 复合索引遵循最左前缀原则，比如建立了
(a, b, c)索引，查询条件里有a和c但缺b，只有a能用上索引。 - 索引不是越多越好，每个索引都要额外占用存储空间，还会拖慢插入、更新和删除操作。
)
