前言
磁盘存取时间
- 寻道时间（速度慢，费时）
-
旋转时间（速度较快）
image.png
image.png
局部性原理与磁盘预读
为了提升效率，要尽量减少磁盘IO的次数。实际过程中，磁盘并不是每次严格按需读取，而是每次都会预读。磁盘读取完需要的数据后，会按顺序再多读一部分数据到内存中，这样做的理论依据是计算机科学中注明的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用
程序运行期间所需要的数据通常比较集中
（1）由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间)，
因此对于具有局部性的程序来说，预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。
（2）MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改)。linux 默认页大小为4K。
1. 索引到底是什么
索引是帮助MySQL高效获取数据的排好序的数据结构
索引存储在文件里
索引结构
为什么不用二叉树、红黑树、HASH 作为索引结构
二叉树 数据向一方偏离，一个节点的左键点小于该节点，右节点大于该节点，但是如果插入二叉树的数据是有序的，就会形成二叉树的极端情况，形成链表，我们知道树的查询复杂度跟树的高度有关，树越高，那么查询事件复杂度就越高，并且需要更多的磁盘IO，所以需要通过某种约束来保证树的平衡，
红黑树
虽然数据较二叉树树形能翻转保持平衡，数据大量的时候，数据深度会很大
红黑树就是平衡二叉树中的一种，它通过一系列的规则来保证树的平衡。但是在大规模数据存储的时候，红黑树常常会因为树的深度过高而导致磁盘IO读写过于频繁，导致效率底下，为什么会形成这种情况呢，我们知道要获取磁盘上的数据，必须通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后进行读写，这种涉及到物理操作情况下，性能自然会很低下。
HASH
1.hash表只能匹配是否相等，不能实现范围查找
select * from xx where id > 23; 这时就没办法索引了
2.当需要按照索引进行order by时，hash值没办法支持排序
select * from xx order by score desc;如果score为建立索引的字段，hash值没办法辅助排序。
3.组合索引可以支持部分索引查询，如(a,b,c)的组合索引，查询中只用到了阿和b也可以查询的，如果使用hash表，组合索引会将几个字段合并hash，没办法支持部分索引
4.当数据量很大时，hash冲突的概率也会非常大
一般来说有多少层高（数据深度）就有多少次IO耗时操作，减少层高非常有必要
BTree
- 度(Degree)一节点的数据存储个数
- 叶子节点具有相同的深度
- 叶子节点的指针为空
-
节点中的数据key从左到右递增排列
注意：由于计算机硬件限制，度(Degree)无限增大，并不能减少IO次数
image.png
B+Tree(B-Tree上优化)
- 非叶子节点不存储data，只储存key，
可以增大度(Degree) - 叶子节点不存储指针
-
顺序访问指针，提高区间访问的性能
image.png
B+Tree索引的性能分析
- 一般使用磁盘I/O次数评价索引结构的优劣
- 预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存
- 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
- B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O
- B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)
为什么mysql的索引使用B+树而不是B树呢？？
上面大致介绍了B-树，B+树，哈希索引。那么B+树的优势大致总结如下
- 不同于B-树只适合随机检索，B+树同时支持随机检索和顺序检索；
- B+树的磁盘读写代价更低。B+树内部结点比B-树小，盘块能容纳的结点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。
- B+树的查询效率更加稳定。B-树搜索有可能会在非叶子结点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找。而在B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。
-
B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起，只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B-树不支持这样的操作（或者说效率太低）。
image.png
2. MySQL数据库存储引擎
MyISAM索引实现(非聚集)
MyISAM索引文件和数据文件是分离的
有些 MySQL 版本还缺乏完整的存储过程支持 — 意味着不支持事务，这是 MyISAM 系统的最大缺点。
InnoDB索引实现(聚集)
- 数据文件本身就是索引文件
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
首先，为了满足MySQL的索引数据结构B+树的特性，必须要有索引作为主键，可以有效提高查询效率，因此InnoDB必须要有主键。如果不手动指定主键，InnoDB会从插入的数据中找出不重复的一列作为主键索引，如果没找到不重复的一列，这时候InnoDB会选择内置的ROWID作为主键，写入顺序和ROWID增长顺序一致；
其次，索引的数据类型是整型，一方面整型占有的磁盘空间或内存空间相比字符串更少，另一方面整型比较比字符串比较更快速，字符串比较是先转换为ASCII码，然后再比较的。
最后，B+树本质是多路多叉树，如果主键索引不是自增的，那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡，影响数据插入的效率，如果是自增主键，只用在尾节点做增加就可以。
- 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
主键索引和非主键索引维护各自的B+树结构，当插入的数据的时候，由于数据只有一份，通过非主键索引获取到主键值，然后再去主键索引的B+树数据结构中找到对应的行数据，节省了内存空间；
如果非主键索引的叶子节点也存储一份数据，如果通过非主键索引插入数据，那么要向主键索引对应的行数据进行同步，那么会带来数据一致性问题。可以通过事务的方式解决，我们都知道使用事务后，就会对性能有所消耗。
联合索引结构
联合索引的底层存储结构长什么样？
定义联合索引(员工级别，员工姓名，员工出生年月)，将联合索引按照索引顺序放入节点中，新插入节点时，先按照联合索引中的员工级别比较，如果相同会按照是员工姓名比较，如果员工级别和员工姓名都相同 最后是员工的出生年月比较。可以从图中从上到下，从左到右看，第一个B+树的节点 是通过联合索引的员工级别比较的，第二个节点是 员工级别相同，会按照员工姓名比较，第三个节点是 员工级别和员工姓名都相同，会按照员工出生年月比较。
