目录

1 索引常用的数据结构

1.1 二叉树

1.2 平衡二叉树

1.3 红黑树

1.3 Hash表

1.4 B树

1.4 B+树

2 MySQL索引的数据结构

2.1 MyISAM存储引擎索引

2.2 InnoDB存储引擎索引

2.2.1 聚集索引

2.2.2 非聚集索引

2.2.3 联合索引数

2.2.4 hash索引

---

1 索引常用的数据结构

1.1 二叉树

二叉树特点：

• 最顶端的称为根节点
• 没有子节点的称为叶节点
• 节点中k-v数据结构，key必须，v非必须
• 非叶子节点只能允许最多两个子节点存在
• 每个节点比左子树所有节点的值大，比右子树所有节点的值小

二叉树查找：

• 采取二分查找
• 最大查找的次数为树的高度
• 查找的时间复杂度为O(log n)

那么如果key的数据分布特点是单调递增或者递减呢？

• 二叉树会退化为链表
• 查找的时间复杂度变为O(n)

1.2 平衡二叉树

为解决二叉树存在的问题，引入了平衡二叉树

当左子树高度和右子树高度的差大于1时，进行旋转，那么就得到了平衡二叉树

平衡二叉树特点：

• 每个节点最多有两个子节点
• 每个节点的值比左子树所有节点的值大，比右子树所有节点的值小
• 每个节点的左子树的高度与右子树的高度差不超过1

那么为了保证二叉树的平衡，在插入数据需要进行一定的操作来保持二叉树的平衡，包括以下几种情况：

左左右

• 插入1节点后导致3号子树与8号子树高度差大于1
• 产生的原因是3号节点的左子树节点多了一个左节点，此时将3号节点右旋

• 右旋的流程为（当前节点为3节点，右旋就是让自己变成右子节点）
  • 将父节点的左子节点设置为左子节点
  • 将左子节点的右子节点设置为当前节点

左右左右

• 插入4节点后导致5子树与8子树高度差大于1
• 产生的原因是5节点的左子树多了一个右节点，此时先将3节点左旋，再将5节点右旋

• 左旋流程（当前节点为3节点）
  • 将父节点的左子节点设置为右子节点
  • 将右子节点的左子节点设置为当前节点
• 右旋流程（当前节点为5节点）
  • 将父节点的左子节点设置为左子节点
  • 将左子节点的右子节点设置为当前节点

右右左

• 插入5节点后导致3子树与8子树高度差大于1
• 产生的原因是3节点的右子节点多了一个右节点，此时将3节点左旋解决问题

• 左旋流程（当前节点为3节点）
  • 将父节点的左子节点设置为右子节点
  • 将右子节点的左子节点设置为当前节点

右左右左

• 插入4节点时导致3子树与8子树的高度差大于1
• 产生的原因是3节点的右子节点多了一个左子节点，此时将5节点右旋后再将3节点左旋解决

• 右旋流程（当前节点为5节点）
  • 将父节点的右子节点设置为左子节点
  • 将左子节点的右子节点设置为当前节点
• 左旋流程（当前节点为3号节点）
  • 将父节点的左子节点设置为右子节点
  • 将右子节点的左子节点设置为当前节点

思考：以上四种情况均考虑的是左子树高度大于右子树高度，那么反过来时又该如何呢？

平衡树虽然解决了数据单调递增或者递减时导致退化为链表的问题，但是在插入时，需要频繁的旋转来保持二叉树的平衡，对于插入修改的性能影响极大。

1.3 红黑树

为解决平衡二叉树插入更新时频发旋转带来的性能问题，引入了红黑树，红黑树通过以下两方面避免了频繁旋转问题

• 红黑树在某些时候允许左右子树的高度差大于1，只要符合红黑树规则即可
• 红黑树不平衡时，不一定非要旋转才能平衡，也可以通过改变颜色达到平衡

红黑树特点：

• 规则1：每个节点不是黑色就红色
• 规则2：根节点是黑色
• 规则3：红色节点的子节点都为黑色
• 规则4：所有所有叶子节点都是黑色
• 规则5：每个节点到叶子节点的每个路径黑色节点的个数都相等

红黑树变色逻辑

• 新插入的节点总认为是红色
• 如果在插入之后不符合规则，则变色

• 变色逻辑（当前节点为2节点）
  • 父节点和叔节点变黑
  • 如果祖父节点不是根节点，则变为红色，然后递归向上检查是否需要变色
  • 如果是祖父节点是根节点，则不变，完成变色

红黑树旋转逻辑

• 变色之后如果还不满足红黑树规则，则进行选择
• 旋转的规则与平衡树一致

红黑树似乎已经解决了很多问题，那么再来想一下，当数据量很大的时候会导致红黑树的高度增大，那么再检索的时候，在最差的情况下每个节点会产生一次磁盘IO，对于检索的性能是影响是巨大的。

1.3 Hash表

• hash表在大多数情况下只需要计算一次hash，就可以定位到元素的位置
• 当hash冲突问题严重时，hash表也会退化成链表，导致检索性能降低
• 仅仅只能满足=，in等查询，不支持范围的查询

1.4 B树

B-Tree特点

• 节点中索引从左到右为递增序列
• 所有的索引元素不重复
• 叶子节点和非叶子节点都包含数据
• 叶子节点具备相同的深度，并且叶节点的指针为空

B树一个节点中包含多个数据，可以有效的降低树的高度，从而加快检索的性能

但是因为其非叶子节点中包含数据，会导致以下问题

• 一个非叶子节点中包含的数据量有限
• 插入时，如果一个节点数据达到上限时，势必会导致数据页的分裂和合并
• 而且由于非叶子节点包含数据，数据页的分裂和合并将会发生的非常频繁
• 如果需要进行范围查询时，如何实现高效查询呢？

1.4 B+树

B+Tree特点

• 非叶子节点不存储data，只存储索引，使得可以容纳更多的数据量
• 叶子节点包含所有索引和数据
• 叶子节点间按照索引递增排序，并且两个相邻叶子节点间有双向指针

B+树由于非叶子节点仅仅包含索引，使其在相同数据量的情况下，树的高度远远低于B树，从而加快检索的效率

2 MySQL索引的数据结构

2.1 MyISAM存储引擎索引

• MySQL中MyISAM存储引擎的数据文件和索引文件是分离的

• MyISAM存储引擎索引的数据结构

• 其采用B+树的数据结构，并进行了一些调整
• MyISAM叶子节点不存储真正的数据，而是存储其数据的指针
• MyISAM索引属于非聚集索引

2.2 InnoDB存储引擎索引

• MySQL InnoDB的数据文件和索引文件为同一个

2.2.1 聚集索引

• InnoDB的聚集索引是一个标准的B+树
• 其叶子节点存储的真实的行记录
• 当行记录过大时，会将数据存储在别的数据页，然后叶子节点存储部分列数据以及指向其余数据的指针

• InnoDB肯定会有一个列充当聚集索引
• 当创建表是指定主键时，主键为聚集索引
• 未指定主键时，选定唯一索引为聚集索引
• 没有唯一索引时，innodb生成rowid充当聚集索引

2.2.2 非聚集索引

除了聚集索引，InnoDB还可以创建辅助索引提升查询效率

辅助索引又称为非聚集索引

InnoDB的辅助索引也采用B+树数据结构，但其叶节点存储的是主键值，而非真实数据

• 拿到主键值后，通过回表的方式在聚集索引检索匹配数据

2.2.3 联合索引数

• 联合索引为给多个字段创建索引
• 其排序规则为依次按照字段的顺序进行排序
• 上一个字段相同时按照下一个字段进行排序

• 按照联合索引的排序规则得出，查询时的查询条件需要严格按照联合索引的字段顺序给出，当查询条件中缺失某个索引字段时，从该字段起，不能通过索引查询
• 以上为最左前缀匹配原则

2.2.4 hash索引

• 与hash索引数据结构一致，但是其值存储的是主键值
• 然后拿到主键值后再进行回表查询