一、MySQL的索引B+树

1，索引要求

• 能在尽可能少的磁盘的 I/O 操作中完成查询工作；
• 要能高效地查询某一个记录，也要能高效地执行范围查找；
• MySQL数据存储在磁盘，需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存；
• 查询过程中会发生多次磁盘 I/O，而磁盘 I/O 次数越多，所消耗的时间也就越大；
• 磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，操作系统的最小读写单位是块（Block），一次会读写多个扇区，Linux 中的块大小为 4KB，也就是一次磁盘 I/O 操作会直接读写 8 个扇区；

2，二分查找

• 时间复杂度 O(logn)；
• 用数组来实现线性排序的数据结构简单，但是插入和删除元素时性能太低；

3，二分查找树

• 时间复杂度 O(logn)，可能会退化成了链表，查找数据的时间复杂度变成了 O(n)；
• 一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点；
• 插入的数据越多，树的高度越高，I/O次数会变多，性能下降；

4，自平衡二叉树

• 时间复杂度 O(logn)，且稳定；
• 每个节点的左子树和右子树的高度差不能超过 1；
• 插入删除时都需要维持树的自平衡，性能有影响；
• 插入的数据越多，树的高度越高，I/O次数会变多，性能下降；

5，B树

• 允许一个节点有 M 个子节点 (M>2)，从而降低树的高度；
• B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到；
• 每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」；
• 做范围查询时，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降；

6，B+树

• 特点：
  • 叶子节点才存放实际数据（索引+记录），非叶子节点只存放索引；
  • 所有索引都会在叶子节点出现，叶子节点之间构成一个有序双向链表；
  • 非叶子节点的索引也会同时存在在子节点中，并且在子节点中所有索引最大（或最小）。
  • 非叶子节点中有多少个子节点，就有多少个索引；
• 单点查询I/O次数：
  • B+ 树的非叶子仅存放索引，在数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少；
• 插入和删除效率高：
  • B+ 树有大量的冗余节点，删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，删除非常快；
  • B+ 树在删除根节点的时候，由于存在冗余的节点，甚至不会发生复杂的树的变形；
  • B 树没有冗余节点，删除节点的时候非常复杂，可能涉及复杂的树的变形；
  • B+ 树的插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径，而且会自动平衡；
• 范围查找：
  • 所以叶子节点用双向链表连接，有利于范围查找；

二、MySQL如何使用B+树索引

1，数据存储

• 数据页
  • InnoDB 的数据是按「数据页」为单位来读写的，默认数据页大小为 16 KB；
  • 每个数据页之间通过双向链表的形式组织起来，物理上不连续，但是逻辑上连续；
  • 数据页包含了七个部分：文件头、页头、最大最小记录、用户记录、空闲空间、页目录、文件尾；
• 用户记录
  • 数据页中的记录按照「主键」顺序组成单向链表；
  • 数据页中有一个页目录，起到记录的索引作用，弥补单向链表的检索速度；
• 页目录
  • 将所有的记录划分成几个组，每个组最后一条就是组内最大的那条记录，并且最后一条记录的头信息中会存储该组一共有多少条记录；
  • 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽（slot），每个槽相当于指针指向了不同组的最后一个记录；
  • 页目录就是由多个槽组成的，槽相当于分组记录的索引，按照「主键值」从小到大排序的，可以使用二分法快速定位要查询的记录在哪个槽，再遍历槽内的所有记录，找到对应的记录；
  • InnoDB 对每个分组中的记录条数都是有规定的：
    • 第一个分组中的记录只能有 1 条记录；
    • 最后一个分组中的记录条数范围只能在 1-8 条之间；
    • 剩下的分组中记录条数范围只能在 4-8 条之间;
• 索引数据结构
  • 索引页中记录的是页 (数据页，索引页) 的最小主键 id 和页号，以及在索引页中增加了层级的信息；
  • id ：对应页中记录的最小记录 id 值；
  • 页号：地址是指向对应页的指针；
• 对比
  • InnoDB 存储引擎：B+ 树索引的叶子节点保存数据本身；
  • MyISAM 存储引擎：B+ 树索引的叶子节点保存数据的物理地址；

2，数据查询

• 从根节点开始，通过二分法快速定位到符合页内范围包含查询值的页；
• 在非叶子节点中，继续通过二分法快速定位到符合页内范围包含查询值的页；
• 在叶子节点中，使用二分法快速定位要查询的记录在哪个槽（哪个记录分组）；
• 定位到槽后，再遍历槽内的所有记录，找到对应的记录；

3，聚集索引

• 聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点；
• 聚簇索引的叶子节点还记录了主键值、事务 id、用于事务和 MVCC 的回滚指针以及所有的剩余列；
• 二级索引的叶子节点存放的是主键值，而不是实际数据；
• 由于数据在物理上只会保存一份，所以聚簇索引只能有一个；
• InnoDB 在创建聚簇索引时，会根据不同的场景选择不同的列作为索引：
  • 如果有主键，默认会使用主键作为聚簇索引的索引键；
  • 如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键；
  • 在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键；
• 如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程叫作「回表」，也就要查两个 B+ 树才能查到数据；
• 当查询的数据是主键值时，只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据；

三、索引介绍

1，索引分类：

• 按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。
• 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。
• 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。
• 按「字段个数」分类：单列索引、联合索引。

2，特性

• 最左匹配
  • 使用联合索引时，存在最左匹配原则，也就是按照最左优先的方式进行索引的匹配，从左至右字段依次有序；
  • 没有最左字段，将无法使用最左匹配原则，形成全局乱序；
  • 联合索引的最左匹配原则，在遇到范围查询（如 >、<）的时候，就会停止匹配，也就是范围查询的字段可以用到联合索引，但是在范围查询字段的后面的字段无法用到联合索引；
• 索引下推
  • MySQL 5.6 引入的索引下推优化，可以在联合索引遍历过程中，对联合索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数；
  • 索引下推的大概原理是：截断的字段不会在 Server 层进行条件判断，而是会被下推到「存储引擎层」进行条件判断，然后过滤出符合条件的数据后再返回给 Server 层，由于在引擎层就过滤掉大量的数据，无需再回表读取数据来进行判断，减少回表次数，从而提升了性能；
• 索引区分区
  • 建立联合索引时，要把区分度大的字段排在前面，这样区分度大的字段越有可能被更多的 SQL 使用到；
  • 区分度就是某个字段 column 不同值的个数「除以」表的总行数；
• 缺点：
  • 需要占用物理空间，数量越大，占用空间越大；
  • 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增大；
  • 会降低表的增删改的效率，每次增删改索引，B+ 树为了维护索引有序性，都需要进行动态维护；

3，使用索引的情况

• 字段有唯一性限制的，比如商品编码；
• 经常用于 WHERE 查询条件的字段，这样能够提高整个表的查询速度，如果查询条件是多个字段，可以建立联合索引；
• 经常用于 GROUP BY 和 ORDER BY 的字段，这样在查询的时候就不需要再去做一次排序，因为建立索引之后在 B+Tree 中的记录都是排序好的；

4，无需使用索引的情况

• WHERE 条件，GROUP BY，ORDER BY 里用不到的字段；
• 字段中存在大量重复数据，不需要创建索引，比如性别字段；
• 表数据太少的时候，不需要创建索引；
• 经常更新的字段不用创建索引，索引字段频繁修改，由于要维护 B+Tree的有序性，就需要频繁的重建索引，这个过程是会影响数据库性能的；

5，索引优化方法

• 前缀索引优化
  • 使用某个字段中字符串的前几个字符建立索引，可以减小索引字段大小，增加一个索引页中存储的索引值，提高索引的查询速度；
  • 在一些大字符串的字段作为索引时，使用前缀索引可以帮助我们减小索引项的大小；
  • 局限性：order by 就无法使用前缀索引，无法把前缀索引用作覆盖索引；
• 覆盖索引优化
  • 在索引 B+Tree 的叶子节点上都能找得到的记录，而不需要通过聚簇索引查询获得，可以避免回表的操作；
  • 使用覆盖索引的好处就是，不需要查询出包含整行记录的所有信息，也就减少了大量的 I/O 操作；
  • 一般需要查询主键的时候的，就可以通过覆盖索引查到；
  • 对于主键之外的字段，可以建立一个联合索引，即索引中存在这些数据，查询将不会再次检索主键索引，从而避免回表；
• 主键索引自增
  • 如果使用自增主键，每次插入的新数据就会按顺序添加到当前索引节点的位置，不需要移动已有的数据，当页面写满，会自动开辟一个新页面；
  • 每次插入一条新记录，都是追加操作，不需要重新移动数据，因此这种插入数据的方法效率非常高；
  • 如果使用非自增主键，每次插入主键的索引值都是随机的，就可能会插入到现有数据页中间的某个位置；
  • 将不得不移动其它数据来满足新数据的插入，甚至需要从一个页面复制数据到另外一个页面，通常将这种情况称为页分裂；
  • 页分裂还有可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率；
  • 键字段的长度不要太大，因为二级索引的叶子节点存放的数据是主键值，主键字段长度越小，二级索引占用的空间也就越小；
• 索引最好设置为 NOT NULL
  • 索引列存在 NULL 就会导致优化器在做索引选择的时候更加复杂，更加难以优化，比如进行索引统计时，count 会省略值为NULL 的行；
  • NULL 值是一个没意义的值，但是它会占用物理空间；
• 防止索引失效

6，索引失效

• 使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx% 会造成索引失效，因为索引 B+ 树是按照「索引值」有序排列存储的，只能根据前缀进行比较；但是只有两个字段，且都是索引字段时，会触发全索引扫描而不是失效；
• 在查询条件中对索引列做了表达式计算、函数、类型转换操作，会造成索引失效，因为索引保存的是索引字段的原始值，而不是经过函数计算后的值，且MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较；
• 联合索引要按照最左优先的方式进行索引的匹配，否则就会导致索引失效；
• 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效，因为 OR 的含义就是两个只要满足一个即可，只要有条件列不是索引列，就会进行全表扫描；

7，count()

• 查询性能：count(*)=count(1)>count(主键字段)>count(其他字段)；
• 使用 count(*) 时，MySQL 会将 * 转化为 0 来处理，count(*) 其实等于 count(0)，所以执行过程基本一样，性能没有什么差异；
• count(主键字段)需要在server层判断字段非NULL；
• count(1)、 count(*)、 count(主键字段)在执行的时候，如果表里存在二级索引，优化器就会选择二级索引进行扫描；
• 且优化器会自动采用 key_len 最小的二级索引进行扫描，相比于扫描主键索引效率会高一些，拷贝的数据少；
• count(字段) 会采用全表扫描的方式来统计，效率是最差的；