深入浅出 MySQL 索引原理与优化详解：B+Tree、Hash、二分查找全解析
索引的基本概念
MySQL官方对索引的定义是：存储引擎用于快速查找记录的一种数据结构。
索引的优缺点
优点
- 查询加速
- 排序优化
- 范围查询
- 连接优化
缺点
- 存储开销
- 维护成本
- 写入延迟
二分查找法
二分查找（Binary Search），也叫折半查找，是一种在有序数组中高效查找指定数据的搜索算法。
算法步骤：
- 设置left和right指针
- 计算中间位置mid
- 比较中间元素与目标值
- 缩小查找范围
Hash结构
Hash底层实现是由Hash表来实现的，根据键值 Key、Value 存储数据。
Hash索引：
- 适合等值查询
- 不支持范围查询
- Memory原生Hash索引、InnoDB自适应哈希索引
InnoDB 自适应哈希索引(AHI)
- 自动在内存中基于B+Tree创建哈希索引
- 只对热点数据创建哈希索引
- 优点：等值查询只需一次哈希计算
B-Tree
B-Tree是一种平衡的多路搜索树：
- 索引值和data数据分布在整棵树中
- 每个节点可存放多个索引值
- 所有叶子节点都位于同一层级
B+Tree
B+Tree是一种平衡多路搜索树：
特点
- 非叶子节点仅存储索引键值，不存储实际数据
- 叶子节点包含完整的索引键值和对应数据
- 叶子节点通过双向指针连接形成有序链表
优势
- 范围查询更高效
- 磁盘I/O次数更少
- 缓存局部性更好
- 全表扫描更高效