Mysql索引解密(上)

索引是数据库概念最重要的概念之一，也是我们经常要使用的优化手段，索引的出现其实就是为了提高数据查询的效率，就像书的目录一样

索引的常见模型

索引的的提出是为了提高查询数据的效率，索引索引模型的概念使我们必须要知道的概念，我们常见的提高读写效率的数据结构很多，我们仅仅介绍常见也是比较简单的数据结构，分别是哈希表，有序数组，搜索树.

哈希表是一种键-值存储的数据结构，我们输入待查询的key,就可以找到其对应的值value,哈希表的思路很简单，就是把一个key进行哈希成一个下表，放到一个数组的位置.当然不可避免的多个key的值经过哈希值可能一样，处理这种情况就是建立一个链表。

比如下面建议一个用户的信息，包括身份证和姓名等，更具身份证查找对应的用户

图中，我们看到id_card_n2和id_card_n4的哈希值都是4，然后他们就会把用户变成一个链表，其中id_card_n是没有顺序的，索引新增一条是数据是比较快的，但是同时由于不是有序的因此区间查找的速度是很慢的，如果必须区间查找，就必须遍历全表扫描。哈希表适应于等值的查找，比如Memcached以及其他Nosql引擎。

而有序数组在等值查询和范围查询场景中性能都比较优秀，如果使用有序数据存储的话，如下图

假设身份证没有重复的话，按照身份证递增的顺序保存的，这时候如果你要对应的名字，用二分法可以快速得到，他的时间复杂度O(logN),同时也支持区间查找，比如[id_card_n,id_card_m],先要使用二分法查询到id_card_n，然后顺序查找到id_card_m。虽然他的查询的速度相对比较好，但是如果要插入一条数据，就必须移动数据，成本还是比较高的。

因此有序数组索引适用于静态存储引擎，比如保存一些固定必变的数据，比如深圳去年的人口信息等等

接下来就是经典的数据结果二叉树，使用二叉树查找身份证实现，如下图

二叉树的特点，就是左节点小于父节点，右节点大于父节点，查找的时间复杂度是O(logN),但是为了保持查询的复杂度不会增加，就需要保持这棵树是一个平衡二叉树，为了保证这个他的更新的复杂度也是O(logN)，

树也可以是二叉也可以是多叉，二叉树的查找速度虽然高，但是由于索引不仅仅在内存也会存在磁盘上，因此他的会造成多次访问磁盘。

可以想象，一棵100万节点的平衡二叉树，数高20，一次查询可能要访问20个数据块，在机械硬盘时代，从磁盘随机读一个数据块需要10 ms左右的寻址时间。也就是说，对于一个100万行的表，如果使用二叉树来存储，单独访问一个行可能需要20个10 ms的时间，这个查询可真够慢的。因此我们就必须减少访问磁盘，那么，我们就不应该选择二叉树，而是使用N叉树。

以InnoDB为例，这个N差不多就是1200，这颗数的高度就是4，就可以存储1200的3次方个值，这已经是17亿数据，考虑到树根的数据块总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

在Mysql中，索引是存储引擎层实现的，索引并没有统一的标准，因此不同的存储引擎的索引结果不一样。

InnoDB的索引模型

在InnoDB中，表都是根据主键顺序以多音的形式存放的，这种存放的表为索引表，InnoDB使用的B+树索引模型，每一个索引对应InnoDB对应一棵B+树，如下图

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

• 主键索引的叶子节点存在是整合的数据，主键索引就是聚簇索引
• 非主键索引的叶子节点的内容是主键的值，非主键索引就是非聚簇索引

基于主键索引和非主键索引的区别

如果语句是如下sql,他是根据主键索引查询

select *  from  table where id = 300

如果语句是如下，他是搜索K索引数，找到id后，在到Id索引搜索一次，这个过程叫做回表，因此在应用中我们尽可能的使用主键索引查询。

索引的维护

B+树为了维护索引的有序性，在插入新值的时候需要做必要的维护，以上面为例，当要插入一条id=700的数据，就直接在R5后面插入一条数据，但是如果要插入一条数据是id=400，对比较麻烦，因为逻辑上要挪动数据，空出位置.再如果R5所在的页已经满了，就必须进行分页，挪动部分数据到新的分页，性能会受到影响，分页以后可能还影响页的利用率，原本一个页的数据，分不到两个页中，整体的空间利用率降低到50%.当然在删除数据的时候，可能也会产生合并页，认为是页分裂过程的逆过程。

正如上面介绍，自增主键插入模式，正符合我们前面提到的递增插入场景，每次插入数据，获取多大id的值，向后面追加一条数据，都不涉及数据的挪动，也不会触发页分裂。

如果使用业务逻辑的字段作为主键，往往不容易按照顺序插入，这样成本比较高，除了性能以外，我们还要考虑存储空间角度去看，比如我们的表中有一个唯一的子弹，比如身份证，我们用身份证做主键还是自增主键呢？

由于每个非主键索引的叶子节点都是主键的值，如果要用身份证做主键，那么每个非聚簇索引的叶子节点占用20个字节，而如果用整数做主键则只要4个字节，长整型占8个字节。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用空间就小，所以，从性能和空间看，自增主键往往是更合适的选择。

什么时候使用业务字段做主键呢

只有一个索引且该索引必须是唯一索引，由于没有其他索引，也就没有考虑其他索引节点大小问题。