MySQL数据库——索引

如果SQL查询比较慢，就会要给字段加索引。索引就像书的目录，可以提高查询效率。

索引的分类：主键索引、唯一索引、普通索引、组合索引、全文索引。

（1）主键索引：非空唯一索引，一个表只有一个主键索引。

在InnoDB中，主键索引的B+树包含表数据信息。PRIMARY KEY(key)

（2）唯一索引：可以有NULL值，但是不能重复。UNIQUE (key)

（3）普通索引：可以出现相同的索引内容。

（4）组合索引：对表上的多个列进行索引。

Q：主键是怎么选择的呢？

答：索引组织表有且只有一个主键。如果显示设置PRIMARY KEY，该设置的key为表的主键。如果没有设置，就从非空唯一索引中选择。如果没有非空唯一索引，就自动生成一个6字节的_rowid作为主键。

B+树是高度平衡的多叉搜索树。一个节点的长度是一页16K(磁盘上物理页的四倍，连续四块物理页)。

每次访问一个节点都是一次磁盘IO。 

聚集索引和辅助索引都是一棵B+树。

（1）聚集索引：按照主键构造的B+树，叶子节点存放具体行数据，数据也是索引的一部分。

select * from user where id >= 18 and id < 40

（2）辅助索引：叶子节点不包含行记录的全部数据。存储“索引+主键key”，即辅助索引的叶子节点中，除了用来排序的key，还包含一个bookmark，该书签存储了聚集索引的key。

select * from user where luckynum = 33;

实现索引的方式很多，常见的索引模型有哈希表、有序数组、搜索树。

哈希表这种结构适用于只有等值查询的场景，比如Memcached以及其他一些NoSQL，不适用范围查询。

有序数组在等值查询（二分法）和范围查询（二分法先找左）都非常优秀，但是更新数据麻烦得很，所以只适用于静态存储引擎。

二叉搜索树BST，等值查询是O(logN)，更新也是，但是要是平衡二叉树。

二叉搜索树效率高，但是实际却不使用，因为耗空间。索引不仅存在内存中，还要写到磁盘里面。树高有多少，就要访问多少次磁盘。为了访问尽量少的数据块，因此决定用N叉树替换。N叉树在读写上有性能优点，同时也适配磁盘的访问模式。跳表、LSM树等数据结构也被用于引擎设计。

关于InnoDB的索引模型。在InnoDB中，表都是根据主键顺序以索引形式存放，这种存储方式的表称为索引组织表。使用B+树。

可以根据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引的叶子节点存整行数据，也叫聚簇索引。比如select * from T where ID=500；只需搜索ID这棵B+树。

非主键索引的叶子节点存主键的值，也叫二级索引。比如select * from T where k=5；需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程被叫做回表。

回表很麻烦的。比如执行select * from T where k between 3 and 5，在下面的结构中，需要执行几次树的搜索操作，会扫描多少行？

 过程：首先在k索引树找到k=3取得ID=300，再去ID索引树查到R3。接下来k=5，k=6。由于查询结果所需要的数据只在主键索引上，所以不得不回表。可不可以经过索引优化，避免回表过程？答案就是覆盖索引。覆盖索引其实就是联合索引。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

比如在市民信息表上，将身份证号和名字建立联合索引。现在有一个高频请求，根据市民的身份证号查询他的名字，这个联合索引就有意义了。它可以在这个高频请求上用到覆盖索引，不需要回表查询整行记录，减少语句的执行时间。

B+树这种索引结构，可以利用索引的最左前缀来定位记录。最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。

为了维护B+树的索引有序性，需要做索引维护。当插入的时候，数据页满了，就要新申请页，然后挪动部分数据过去，就是页分裂，也影响数据页的利用率。当删除的时候，利用率很低之后，就要将数据页做合并。

哪些场景下应该使用自增主键，哪些场景下不应该。自增主键是指自增列上定义的主键。AUTO_INCREMENT。