MySQL 索引数据结构和原理

一、为什么用索引

索引是排好序的数据结构，加速查询。

二、B+ 树

为什么不用二叉树

二叉树退化成链表。

为什么不用 B 树

B 树每个节点存数据，一次 IO 拿的数据少。

B+ 树特点

• 非叶子节点只存 key，不存数据。
• 叶子节点存所有数据，用链表连接。
• 树矮胖，IO 次数少。

三、为什么用 B+ 树

• 一次 IO 读更多 key。
• 范围查询快（叶子链表）。
• 查询稳定（都到叶子）。

四、索引类型

• 主键索引（聚簇）。
• 二级索引（非聚簇）。
• 联合索引。
• 覆盖索引。

五、索引失效

• 函数操作。
• 隐式转换。
• like %xx。
• or。
• 不符合最左匹配。

一句话

B+ 树：矮胖、叶子链表、范围快。