【MySQL（2）| MySQL索引机制】
什么是索引？
索引是存储引擎用于快速找到记录数据行的一种分散存储的数据结构。
索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。
在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但是当数据量逐渐增大时，性能则会急剧下降。
所以 正确的创建合适的索引是提升数据库查询性能的基础。
为什么要使用索引？
- 索引可以把随机IO变成顺序IO
- 索引能极大的减少存储引擎需要扫描的数据量
- 索引可以帮助我们在进行分组、排序等操作时，避免使用临时表
索引有哪些类型？
索引有很多类型，可以为不同的场景提供更好的性能。
MySQL中，索引是在存储引擎层面实现的，所以，并没有统一的索引标准，一般来说，不同存储引擎的工作方式是不一样的，也不是所有的存储引擎都支持所有类型的索引
哈希索引
哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。
对于每一个数据行，存储引擎都会对所有的索引列根据一定的计算规则计算出一个哈希码，然后哈希索引将所有的哈希码存储在索引中，同时在哈希表中会保存一个指向对应数据行的指针。
MySQL中，Memory引擎是显式支持哈希索引的，他也是该引擎默认的索引类型，值得注意的一点是：Memory引擎是支持非唯一哈希索引的，也就是说如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希表中。
哈希索引的应用场景
根据本人的理解，这种直接通过哈希索引的存储引擎，因为索引自身只需要存储对应的哈希值，所以索引的结构十分紧凑，这会让哈希索引查找的速度非常快
哈希索引的一些限制
- 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行（即不能使用哈希索引来做覆盖索引扫描），不过，访问内存中的行的速度很快（因为memory引擎的数据都保存在内存里），所以大部分情况下这一点对性能的影响并不明显。
- 哈希索引数据并不是按照索引列的值顺序存储的，所以也就无法用于排序
- 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引的全部列值内容来计算哈希值的。如：数据列（a,b）上建立哈希索引，如果只查询数据列a，则无法使用该索引。
- 哈希索引只支持等值比较查询，如：=,in(),<=>(注意，<>和<=>是不同的操作)，不支持任何范围查询（必须给定具体的where条件值来计算hash值，所以不支持范围查询）。
- 访问哈希索引的数据非常快，除非有很多哈希冲突，当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
- 如果哈希冲突很多的话，一些索引维护操作的代价也很高，如：如果在某个选择性很低的列上建立哈希索引（即很多重复值的列），那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。
B-Tree索引
B-Tree索引使用B-Tree树数据结构存储数据，大多数MySQL引擎都支持这种索引（Archive引擎是个例外）
B+Tree索引图
详细的B-Tree和B+Tree可以参考 【MySQL一】开发人心里都该有的那颗 B 树
B树被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”。
什么是局部性原理与磁盘预读？
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B树为何适合做索引？
(1)由于是m分叉的，高度能够大大降低；
(2)每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO；
注意：高度降低的原因在于：
- 在利用了局部性原理前提下，我们把一个节点的大小设为一页，一页4K，假设一个KEY有8byte，一个节点可以存储500个KEY，即j=500
- m叉树，大概m/2<= j <=m，即可以差不多是1000叉树
- 一层树：1个节点，1*500个KEY，大小4K 二层树：1000个节点，1000500=50W个KEY，大小10004K=4M 三层树：10001000个节点，10001000500=5亿个KEY，大小10001000*4K=4G
所以：《高性能Mysql第三版》这本书也说了，一般的B+树都不会超过三层，也就意味着绝大数数据通过三次IO就可以找到
B树，它的特点是：
- 不再是二叉搜索，而是m叉搜索；
- 叶子节点，非叶子节点，都存储数据；
- 中序遍历，可以获得所有节点；
B+树的特点是：
B+树，是在B树的基础上，做了一些改进：
- 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
- 叶子之间，增加了链表，获取所有节点，不再需要中序遍历；
以上改进让B+树比B树有更优的特性：
- 范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势）；
- 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；
- 非叶子节点，不存储实际记录，而只存储记录的KEY的话，那么在相同内存的情况下，B+树能够存储更多索引；
索引体现形式
Myisam引擎
使用Myisam引擎的表在数据库中会存在三个文件
以user表为例：
一个是表定义文件 user.frm
一个是索引存储文件 user.MYI
还有一个是数据存储文件 user.MYD
因为Myisam引擎的索引和数据是分开存储的，叫做非聚集索引（UnClustered Index）。并且在B+tree树的叶子节点存储的是数据行的地址，在检索数据时，以此从根节点开始检索，直到找到对应的关键字，然后到数据区获取数据行地址，最后根据这个数据行地址返回检索的数据行
Innodb引擎
Innodb和Myisam最大的不同是他是以主键为索引来组织数据的存储，叫做聚簇索引（Clustered Index），也叫作聚集索引。
可能你会说，如果我的表没有主键怎么办？你也尽可放心:
- 如果你没有主键，innodb会选择一个唯一的非空索引代替;
- 如果没有这样的唯一索引可用，Innodb会自己创建一个隐式的row-id索引用于组织存储数据，
使用Innodb引擎的表在数据库中会存在三个文件
以teacher表为例：
一个是表定义文件 teacher.frm
一个是数据和索引存储文件 teacher.IBD
此处引入一个聚簇索引（也叫聚集索引）：数据库表行中数据的物理顺序与键值得逻辑顺序（也就是索引）相同，聚集索引并不是一种单独的索引类型，而是一种数据存储技术。
当有聚簇索引时，它的所有数据行实际上存放在索引的叶子页中，此处应该注意的是，因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
聚簇索引的优点
- 可以把相关数据保存在一起
- 数据访问更快。聚簇索引将索引和数据保存在同一个b-tree中，因此从聚簇索引中查询数据通常比在非聚簇索引中查找要快
- 使用覆盖索引（后文会有介绍）扫描的查询可以直接使用页节点中主键值
聚簇索引的缺点
- 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到Innodb表中速度最快的方式。
- 更新聚簇索引列的代价很高，因为Innodb会强制将每个被更新的行移动到新的位置
- 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂（当行的主键值要求必须将这一行插入到某个已满的页时，存储引擎会将该页分裂成两个页面来存储该行，这就是一页分裂操作，页分裂会占用更多的磁盘空间）导致数据存储不连续的时候
- 二级索引访问需要两次索引查找
关于最后一点，是因为，二级索引叶子节点保存的并不是指向行的物理位置的指针，而是保存的是主键值，这意味着通过二级索引查找行的时候，存储引擎首先需要找到二级索引所对应的主键值，然后通过主键值再去聚簇索引找到对应的行。
小结
MyISAM和InnoDB都使用B+树来实现索引：
- MyISAM的索引与数据分开存储
- MyISAM的索引叶子存储指针，主键索引与普通索引无太大区别
- InnoDB的聚集索引和数据行统一存储
- InnoDB的聚集索引存储数据行本身，普通索引存储主键
- InnoDB一定有且只有一个聚集索引
- InnoDB建议使用趋势递增整数作为PK，而不宜使用较长的列作为PK
其他索引策略
覆盖索引
如果一个索引包含所有需要查询的字段的值，我们就称之为“覆盖索引” 换言之，如果查询列可以通过索引节点中的关键字直接返回，则该索引称之为覆盖索引
覆盖索引的优点
- 索引条目通常远小于数据行大小，因为只需要读取索引，自然极大减少了数据访问量，减少数据库IO
- 将随机IO变成顺序IO：因为索引是按照列值顺序存储的。
联合索引
单列索引可以理解成是一种特殊的联合索引
很多人对多列索引的理解都不够，一个常见错误哪就是 为每个列创建独立的索引，或者按照错误的顺序创建多列索引
记得之前看过一个博客说 建议把 where条件里边的列都加上索引，实际上这个建议是非常错误的。
在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能
联合索引有几个选择原则：
- 经常用的列优先【最左匹配原则】
- 选择性（离散度）高的列优先【离散度越高 选择性越好】
- 宽度小的列优先【最少空间原则】
选用B+Tree的原因
- B+树是B-树的变种（PLUS版）多路绝对平衡查找树，他拥有B-树的优势
- B+树扫库、表能力更强
- B+树的磁盘读写能力更强
- B+树的排序能力更强
- B+树的查询效率更加稳定