MySQL 索引原理与分类详解
什么是索引
索引本质上是一种数据结构，它帮助数据库高效地查询和更新数据表。通过特定的排序规则排列记录，索引能显著加快检索速度。打个比方，就像书籍的目录，你不需要逐页翻阅就能找到特定内容。在数据库中，如果没有索引，查找某个值可能需要扫描整张表；有了索引，系统可以直接定位到目标位置。
为什么要使用索引？
使用索引的核心价值在于性能优化：
- 提高查询效率：减少扫描的数据量。大数据量下，无索引需全表扫描，有索引则能快速定位。
- 实现唯一约束：创建唯一索引可确保列或列组数据的唯一性，防止重复数据，保障数据完整性。
- 支持排序和分组：若排序或分组字段上有索引，数据库可直接利用有序性，避免额外的排序开销。
- 优化连接操作：多表关联时，索引能帮助数据库更快地匹配连接条件。
索引的分类
哈希索引
- 结构特点：基于哈希表，通过键值的哈希直接定位数据，类似字典的'键 - 值'映射。
- 优势：查找时间复杂度为 O(1)，速度极快。
- 局限性：不支持范围查询、排序和模糊匹配；哈希冲突会影响性能；MySQL 中仅 Memory 引擎默认支持。
二叉搜索树 (BST)
- 定义：一种特殊的二叉树，左子树节点值小于根节点，右子树大于根节点，左右子树本身也是 BST。
- 结构特点：每个节点最多两个子节点，中序遍历结果为有序递增序列。
- 优势：理想情况下插入、删除、查询复杂度为 O(log n)；逻辑简单。
- 局限性：最坏情况下（退化为链表）复杂度为 O(n)；节点过多时树高难以控制，磁盘 IO 效率低；范围查询需遍历多个节点。
N 叉树
- 定义：每个节点最多有 N 个子节点的树形结构，N 根据场景设计。
- 结构特点：节点包含多个关键字及对应指针，关键字有序。
- 优势：降低树高，大幅减少磁盘 IO；高效支持范围查询；适合大规模数据存储。
- 局限性：N 值需合理设计，节点结构较复杂。
B 树
- 定义：平衡的多路搜索树，每个节点子节点数多于两个。
- 查询方式：从根节点开始，根据关键字比较决定进入哪个分支，直到找到目标或到达叶子节点。
B+ 树
- 定义：B 树的变形优化，更适合数据库作为索引结构，是 MySQL 默认采用的数据结构。
- 查询方式：与 B 树类似，但利用叶子节点的链表结构，可快速遍历范围内所有数据。
B+ 树与 B 树的区别
| 区别 | B 树 | B+ 树 |
|---|---|---|
| 节点存储 | 叶子节点和非叶子节点均存储索引 + 数据 | 非叶子节点只存索引，叶子节点存索引 + 数据 |
| 查询路径 | 数据分布在所有节点，可在非叶子节点找到数据 |
