MySQL索引数据结构详解

索引的定义：方便Mysql更高效的获取排好序的数据结构

数据结构分为：

1. 二叉树
2. 红黑树
3. hash表
4. B-Tree

二叉树规则：可视化二叉树

从父节点查找数据，每个节点最多有两个子节点，左子节点比父节点小，右子节点比父节点大

mysql底层没有用到二叉树

主要原因：

1. 磁盘IO问题
   • 二叉树层级可能很深
   • 每查找一次需要一次磁盘IO
   • IO次数多就会影响性能
2. 性能问题：
   • 数据量大树的层级就会高
   • 一百万数据可能需要20层
   • 查询效率低

红黑树规则（二叉自动平衡树）:可视化红黑树

每个节点要么是红色，要么是黑色，根节点必须是黑色，叶子节点（NIL）是黑色，红色节点的子节点必须是黑色，从根到叶子的所有路径都包含相同数量的黑色节点

mysql底层没有用到红黑树

主要原因：

1. 磁盘IO问题
   • 树高度可能很大
   • 每个节点只存储一个键值
   • 查询可能需要多次磁盘IO
2. 性能问题：
   • 一百万数据可能需要20层
   • 查询需要20次IO

B-Tree规则（二叉自动平衡树）:可视化B-Tree

所有节点都存储数据，非叶子节点也存储数据，叶子节点没有指针相连，节点中的数据索引从左到右递增排列

mysql底层没有用到B-Tree

主要原因：

1. 磁盘IO问题
   • 树高度可能很大
   • 每个节点只存储一个键值
   • 查询可能需要多次磁盘IO
2. 性能问题：
   • 一百万数据可能需要20层
   • 查询需要20次IO

B+Tree规则（B-Tree变种、加强版）:可视化B+Tree

只有叶子节点存储数据，非叶子节点只存索引，叶子节点通过指针相连（提高区间访问速度，叶子节点相邻使用指针连接，比如：A B节点相连，A有点空间存储了B在磁盘的位置，B也有点空间存储A在磁盘的位置 ），节点中的数据索引从左到右递增排列

mysql底层真正用到的是B+Tree

主要原因：

1. 磁盘IO问题
   • 非叶子节点不存数据，可以存更多索引
   • 树高度更低，减少IO次数
2. 性能问题：
   • 顺序读取，IO次数少
   • 一百万数据树高度约3-4层
   • 查询只需3-4次IO
   • 范围查询很快