MySql——索引（上）

何为索引

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。
但是实现索引的方式却有很多种，有三种常见且简单的数据结构，它们分别是哈希表、有序数组和搜索树
这里只说以下使用场景，哈希表索引适用于只有等值查询的场景，对于范围查询并不适用。
而有序数组在等职查询和范围查询场景中性能都非常优秀，但是有序数组在插入和删除数据时，需要挪动大量的数据，比较耗时，所以有序数组索引只适用于静态存储引擎。
二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。

为了维持O(logn)的时间复杂度，需要保持这棵树的平衡性，为了达到这个保证，更新的时间复杂度也是O(logn)。
但是二叉搜索树每一层存储的结点并不多，这就会导致树高较大，而索引不仅是要存在内存中的，还要存储在磁盘中的，这就会导致磁盘中每次需要查找一个结点时，从磁盘随机读取一个数据块的次数较多（树高较大的情况）。
举个例子，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
所以，为了让一个查询尽量少地读磁盘，就不应该使用二叉树，而是要使用N叉树，这里的N取决于数据块的大小。以InnoDB的一个整数字段索引为例，这个N大概为1200，如果一棵树树高为4的话，就可以村1200的3次方，也就是17亿，这时，查找一个数据最多只需要访问3次磁盘（甚至更少），大大提高了访问速度。
数据库技术发展到今天，跳表、LSM 树等数据结构也被用于引擎设计中，这里我就不再一一赘述。

InnoDB的索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在 InnoDB 里面对应一棵 B+ 树。
假设，有一个主键为id的表，表中有字段k，并且在k上有索引。则这个表的建表语句是：

create table t(
	id int,
    k int not null,
    name varchar(16),
    index (k)
)engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。

根据叶节点的内容，索引类型分为主键索引（聚簇索引）和非主键索引（二级索引）。

这两种索引的区别是：

如果语句是select * from t where id=500，就会使用主键索引；

如果语句是select * from t where k=5，就会使用非主键索引，需要先搜索k索引树，得到id的值为500，再到id索引树搜索一次，这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引的维护

为了维护索引树的有序性，需要再插入和删除操作做必要的维护，在InnoDB中，每一个B+树的子节点为一个数据页，而数据页的默认大小是16KB。
以上图为例，如果插入的新行id值为700，则只需要在R5后面插入一个新记录，而如果新插入的值为400，就会比较麻烦，需要逻辑上挪动后面的数据，空出位置。
而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。
这里利用率降低50%的原因是，为了避免每次插入时都会挪动数据，InnoDB并不会去填满每个数据页，它会留有一小部分的空间以防下一次的插入，而这些空间就称为数据页的空洞。
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。
所以，为了保证不会在数据的中间插入数据，可以将主键设置为自增模式，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
还有一个选择索引原则：主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。所以，一般不会用业务字段去作为索引，这样做也不能保证索引的有序性。
使用业务字段做索引的情况：
1. 只有一个索引；
2. 该索引必须是唯一索引。