索引是一种特殊的文件，它包含着对数据表里所有记录的引用指针。简单讲，就像一本书前面的目录，能加快查询速度。

- 索引是帮助mysql高效获取数据的数据结构

- 索引存储在文件系统中

- 索引的文件存储形式与存储引擎有关

- 索引文件的结构

可以考虑作为索引的数据结构有如下几种，下面介绍下不同数据结构的特点：

- hash表

- 二叉树

- b树

- b+树

1. 为什么不选 Hash 表

1. 不支持范围查询Hash 是等值匹配（=），没法做 > < >= <= between、排序、分页、前缀模糊查询。
2. 哈希冲突冲突会退化成链表，查询性能退化。
3. 不支持有序遍历索引排序、联合索引最左匹配、order by 完全不友好。
4. 磁盘存储不友好Hash 桶离散，无法按页 / 块批量预读，缓存利用率低。

适用：仅等值查询场景（如 InnoDB 自适应哈希索引），不能做主索引结构。

---

2. 为什么不选 普通二叉树 / 二叉搜索树 BST

1. 树高不可控，容易退化成链表数据有序插入时，BST 直接变成单链表，时间复杂度退化成 O (n)。
2. 层高太高千万级数据，二叉树层高几十层，磁盘要几十次 IO，慢到爆炸。
3. 节点度只有 2，每页存的数据太少磁盘一次读一页，二叉树一个页块存不了几个关键字，IO 次数暴增。

---

3. 为什么不选 红黑树

红黑树是平衡二叉树，解决了 BST 倾斜问题，但仍有硬伤：

1. 还是二叉，分支太少每个节点最多 2 个子节点，树高依然很高，大数据量磁盘 IO 次数多。
2. 不适合磁盘块存储红黑树节点小、碎片化，没法利用磁盘预读、页批量加载特性。
3. 范围查询效率低范围查询要中序遍历，没法像 B + 树一样叶子节点链表直接顺序扫。
4. 维护成本高插入删除旋转调整多，数据库海量数据下开销大。

红黑树适合内存结构，不适合磁盘索引。

---

4. 为什么不选 B 树（多路平衡查找树）

B 树已经是多路平衡树、矮胖结构，比二叉树强很多，但对比 B + 树仍有短板：

1. 非叶子节点也存数据 + 行记录       B 树：所有节点都存关键字 + 数据              B + 树：只有叶子节点存完整数据，非叶子只存索引键→ B 树非叶子节点占用空间大，每页能存的索引个数变少，树高变高，IO 变多。

2. 范围查询麻烦B 树范围查询需要中序遍历整棵树，来回跳节点、跳磁盘块。B + 树叶子节点是双向链表，范围查询直接链表顺序遍历，不用回溯非叶子节点。

3. 磁盘预读利用率低B 树数据分散在各层节点，无法批量顺序读取；B + 树所有数据都在叶子，天然有序、连续、适合批量分页 / 范围扫描。

---

二、B + 树 凭什么胜出？（核心优势）

1. 多路矮胖，树高极低一个节点可以存成百上千个索引，千万级数据也就3~4 层，一次查询仅 3~4 次磁盘 IO。

2. 非叶子只存索引键，不存数据每页能放更多索引，进一步压低树高，IO 次数最少。

3. 叶子节点双向链表有序完美支持：范围查询、排序、分页、全表扫描、前缀匹配。

4. 磁盘预读特性拉满数据全在叶子节点集中存放，符合磁盘局部性原理、顺序预读，缓存命中率极高。

5. 插入删除稳定平衡多路平衡，分裂合并规则简单，维护开销可控，适合高并发数据库。

---

三、一句话总结对比

结构	致命缺点	适用场景
Hash 表	不支持范围、排序、有序遍历	仅等值查询
普通二叉树	易倾斜成链表、层高太高	无实际索引使用
红黑树	二叉分支、层高仍高、不适合磁盘批量读	内存有序容器
B 树	非叶子存数据、每页索引少、范围查询差	文件系统小索引
B + 树	几乎无短板	数据库磁盘索引标配

---

四、面试极简背诵版

1. Hash：只能等值，不支持范围排序；
2. 二叉树：易倾斜、层高太高、IO 爆炸；
3. 红黑树：还是二叉，层高高，不适合磁盘批量预读，范围查询弱；
4. B 树：非叶子存数据，每页索引少、树高更高，范围查询不如 B + 树链表遍历；
5. B + 树：矮胖多路、非叶子只存索引、叶子链表有序、适配磁盘 IO 和范围分页，完美适配数据库索引。

-- 创建普通索引

CREATE INDEX idx_student_name ON students(name);

-- 创建唯一索引

CREATE UNIQUE INDEX idx_student_email ON students(email);

-- 创建复合索引

CREATE INDEX idx_student_class_score ON students(class_id, score);

-- 查看索引

SHOW INDEX FROM students;

-- 删除索引

DROP INDEX idx_student_name ON students;

-- 开启性能分析

SET PROFILING = 1;

-- 无索引查询

SELECT * FROM students WHERE name = '张三';

-- 创建索引后查询

CREATE INDEX idx_name ON students(name);
SELECT * FROM students WHERE name = '张三';

-- 查看查询时间

SHOW PROFILES;

1. 索引像书的目录 - 快速定位，避免全表扫描
2. B+树结构 - 多层查找，效率极高
3. 用EXPLAIN分析 - 查看索引是否生效
4. 复合索引注意顺序 - (A,B)索引能查A，不能只查B
5. 索引有代价 - 占用空间，降低写性能

黄金法则：只为经常查询、数据区分度高的字段创建索引！