目录
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索引数据结构一致，但是其值存储的是主键值
- 然后拿到主键值后再进行回表查询
