MySQL学习笔记（2）——索引
MySQL索引类型
B+ Tree索引
MySQL索引默认的数据结构为B+树。
B+树是B树（Balance Tree）的进化版本，具有$O(log_2n)$的查找、插入、删除的时间复杂度，其设计目的是减少硬盘IO次数。
B+树特点
- 所有父节点元素出现在其子节点中，作为子节点的最大（或最小）元素。
- 所有的叶子节点位于同一层，节点中的元素从小到大排列，叶子结点之间按从小到大的顺序相互连接，形成了有序的链表。
- 非叶子节点不存储数据，仅作为索引，叶子节点存储了全部信息。
与其他结构比较
与B树相比：
- 非叶子节点不存储数据，意味着中间节点可以容纳更多元素，因此B+树比B树更加矮胖，减少IO次数；
- B树查询次数不稳定，B+树每一次查找都是稳定的；
- 叶子节点相对有序，且连接成链表，便于范围查找。
相比于红黑树和AVL树，B+树深度小，因此需要较少IO的次数，并且红黑树等AVL树不能利用磁盘预读性能。
B+树数据量
- B+树叶子节点大小默认情况下等于一个磁盘页的大小（16KB），这样每个节点只需要一次IO就可以完全载入，并且可以利用磁盘预读的功能，加载该节点附近的数据，降低磁盘IO次数。
- InnoDB中非叶子节点存放主键ID和指针，为
8+6=14B，那么一个非叶子节点大约可以存放16KB/14B=1170个指针。假设一行记录的大小为1KB，一个叶子节点能存放16条记录，则3层高度的B+树能存放1170*1170*16=21902400条记录。
Hash索引
Hash索引根据一定的映射函数找到表中数据的具体位置，具有O(1)的读写性能，但它是无序的，用于范围查找时需要全表查找。
自适应哈希索引
InnoDB会监控表上二级索引的查找，如果某二级索引被频繁访问，会在缓存池中建立哈希索引，可以提升查询性能，但只支持等值查询。
全文索引
MySQL 5.6版本前只有MyISAM支持全文索引，之后InnoDB加入了对全文索引的支持。MySQL 5.7.6版本开始内置ngram全文解析器，支持中文分词。
全文索引基于倒排索引实现。
MySQL存储引擎
InnoDB
- 从MySQL 5.5版本起作为默认的存储引擎。
- 支持事务，支持外键，支持行级锁，支持奔溃后的安全恢复。
- 聚簇索引：InnoDB是聚簇索引，数据存放于主键索引的叶子节点上，辅助索引的叶子节点存放主键的值。走主键索引查询时性能很好，但走辅助索引时，先查询到主键，再返回主键索引去查找数据。
- 覆盖索引：如果走辅助索引就能得到所要查询的全部信息，则无需回到主键索引去查询，可以减少IO操作，大幅提升性能。例如：
a为主键索引、b为辅助索引，SELECT a FROM table WHERE b=1发生了覆盖索引，不需要回表查找。
MyISAM
- 不支持事务，只支持表级锁，不支持外键，不支持奔溃后的安全恢复。
- 非聚簇索引：MyISAM的索引和数据文件是分开的，主键索引和辅助索引的叶子节点存放的是指向数据文件物理地址的指针。
MEMORY
- MEMORY引擎数据全部存放在内存中，如果掉电就会失去所有数据，因此多用于临时表。
- MEMORY引擎默认为Hash索引。
联合索引
- 对表上多个列建立索引，本质上也是建立B+树，优先对建立联合索引的最左的列进行排序，当满足最左列的顺序时，才会依次按照第二列、第三列排序。
- 使用联合索引时需要满足最左前缀原则。例如创建
a,b,c的联合索引，等同于创建了a、a,b、a,b,c的索引，此时部分情况会导致索引失效：SELECT id FROM t WHERE a = xxx AND b = yyy——a和b的索引有效；SELECT id FROM t WHERE a = xxx AND c = yyy——仅a的索引有效；SELECT id FROM t WHERE b = xxx AND c = yyy——索引失效；SELECT id FROM t WHERE a > xxx AND b = yyy——仅a的索引有效；SELECT id FROM t WHERE b = xxx AND a = yyy——a和b的索引有效。
索引失效的场景
- 联合索引，未满足最左前缀原则；
- 模糊查询，
LIKE以%开头； - 查询条件含有
OR； WHERE条件含有运算、不等号、使用了函数。
主键
- 每个表只能有一个主键，不允许为NULL。
- 一个字段只能在联合主键中出现一次，联合主键不能包含多余的不必要字段。
- InnoDB采用聚簇索引，B+树的构建依赖于主键，因此InnoDB必须要有主键。如果没有手动指定主键，InnoDB会选择第一个非空的唯一索引作为主键，如果找不到这样的索引，会自动生成一个不可见的名为
row_id的索引，它是一个6字节的自增数值。