[数据结构与算法]深入理解MySQL底层数据结构算法

什么是索引？

1. 索引是帮助MySQL高效获取数据的排好序的数据结构
2. 索引的数据结构：二叉树，红黑树，Hash表，B-树

分析select语句

select * from t_user where age = 18;

没有加索引

没有加索引时，MySQL底层是通过一行一行的进行查找的，当找找到age=18的字段后依然不能确定后面的数据时候还有age=18的字段，所以依然需要继续查找，一次查找就是一次磁盘IO（Mysql 通过磁盘 IO 次数衡量查询效率的），如果一张表有10万条数据那么就需要进行10万次的查找，把数据从磁盘加载到内存的速度不快，如果数据量大的话，需要花费相当多的时间，才能扫描完整张表。

加索引（二叉树）

加索引后，MySQL的查找就发生了变化，索引就是一种数据结构，如果索引是二叉树的话，就通过二叉树来查找。使用age索引后，就先去二叉树里去查找，每一个节点就相当于是键值对key存储的是age的值，value存储的就是文件地址指针（指向一列的数据）。要知道二叉树中一个节点的值大于它的左孩子小于它的右孩子，所以查找速度会很快。

MySQL索引使用的数据结构

体会了一把索引查找数据结构，发现索引确实提高了我们的查找速度。而我们知道MySQL索引使用额数据结构是B+树，先不考虑为什么选用B+树，先来考虑为什么不选用二叉树，因为二叉树存在弊端，当数据是按一定顺序来存储的话，二叉树就会退化成链表，这样的话查找速度就没有得到提升。那有没有一种数据结构能够做到避免这种弊端呢?接下来我们看看平衡二叉树红黑树。

给出一段数据1,2,3,4,5,6,7,8,9。

用二叉树存储

用红黑树来存储，如下

从红黑树额构建中发现当红黑树自身不能满足红黑树的特性的时候，红黑树会自旋，以保持红黑树的特性。那么既然解决了退化成链表的问题为什么又没有选择它呢？

我们要知道AVL 树和红黑树基本都是存储在内存中才会使用的数据结构。在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘 IO 读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘 IO 代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘 IO 频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，我们需要通过某种较好的树结构减少树的结构尽量减少树的高度来优化。

这时有人就会说B-树，很好B-树能够解决树的深度的问题

我们先来看看B-树的索引原理：B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；因此，B-Tree的查找过程是一个顺指针查找结点和在结点的关键字中进行查找的交叉进行的过程。

接下来看看B-树对数据的存储，依然使用上面的数据1,2,3,4,5,6,7,8,9，且设置Max.degree=4

了解完B-树的索引原理，这时候我们就可以拍手叫绝了，B-树相对于红黑树一定程度上解决了树的高度问题了，那么mysql的索引就可以使用B-树了吧。这时候mysql就会给你当头一击，mysql实际使用的数据结构是B+树。

B+树存储1,2,3,4,5,6,7,8,9，且设置Max.degree=4

通过以上的图有一定数据结构基础的朋友就会想起一些区别

这里就直接贴上总结：

B树的特征：

• 关键字集合分布在整颗树中
• 任何一个关键字出现且只出现在一个结点中
• 搜索有可能在非叶子结点结束（data与在节点）
• 其搜索性能等价于在关键字全集内做一次二分查找
• 自动层次控制

B+树的特征：

• 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的
• 不可能在非叶子结点命中（data域在叶子节点）
• 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
• 每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历。
• 更适合文件索引系统

B+树是B树的一个变体，区别在于，B+树：

1. 叶子结点包含所有关键字以及指向相应记录的指针
2. 叶子结点中的关键字有序，相邻节点用指针连接
3. 非叶子结点仅存储其子树的最大（或最小）关键字，可以看成是索引

B+ 树作为数据库索引的原因

• B+ 树非叶结点仅存储其子树的最大（或最小）关键字（不存放真正数据），一个结点可以存储更多的关键字
• 每个结点能索引的范围更大更精确
• B+ 树单次磁盘IO的信息量大于 B 树，I/O 的次数相对减少
• MySQL是一种关系型数据库，区间访问是常见的一种情况，B+树叶结点增加的链指针，加强了区间访问性；B 树则无法进行区间查找

索引存储在文件系统中

索引是占据物理空间的，在不同的存储引擎中，索引存在的文件也不同

MySQL叶结构示意图

聚集索引与非聚集索引

• 聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据，主文件按照对应字段排序存储，索引文件无重复排序存储。
  

  • 聚集：把索引的元素和数据存储在一个文件中（*.ibd）

• 非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行，主文件并没有按照对应字段排序存储，索引文件有重复排序存储。
  

  • 非聚集：把索引的元素和数据存储在不同的文件中，*.MYI存储索引， *.MYD存储数据

InnoDB索引的实现（聚集）

• 表数据文件本身就是按B+Tree组织的一个索引结构文件
• 聚集索引叶子结点包含完整的数据记录
• 为什么InnoDB表必须有主键，并且推荐使用整形的自增主键？
  • 如果设置了主键，那么InnoDB会选择主键作为聚集索引、
  • 如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。
  • MySQL官方工程师就是这么设计的（更具主键来存储）
  • 如果表使用自增主键那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页
  • 如果使用非自增主键（如果身份证号或学号等）由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
  • uuid的使用与整形的对比：uuid比整形占用更多的存储空间；整形的比较效率更快（UUID是16字节128位长的数字，通常以36字节的字符串表示）
• 为什么非主键索引结构叶子结点存储主键？（一致性和节约存储空间）
  • 保持一致性：
    当数据库表进行DML操作时，同一行记录的页地址会发生改变，因非主键索引保存的是主键的值，无需进行更改。
  • ** 节省存储空间：**
    Innodb数据本身就已经汇聚到主键索引所在的B+树上了， 如果普通索引还继续再保存一份数据，就会导致有多少索引就要存多少份数据。

参考：

1. https://blog.csdn.net/wangfeijiu/article/details/113409719
2. https://long97.blog.csdn.net/article/details/106084627