索引 - 《MySQL》 - 极客文档

对B+树的概念认知
- B+树的维护
InnoDB的索引模型
索引优化

索引有三种数据结构：hash表，有序数组，搜索数
hash表适用于等值查找的场景，做区间查询很慢；
有序数组可以很快做等值查找和范围查找，但是增改时效率很低（需要在数组中间插入时），适合不发生变化的数据；
搜索树即是B+树；

对B+树的概念认知

想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询可真够慢的。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

树中的每一个分支对应磁盘中的一个盘块，需要读盘指针移动；
B+树的节点中只保存了键，所有的数据都保存在叶子节点，这样做的好处是压缩了单个节点的大小，可以让N叉树的N尽可能的大，从而降低树的高度，减少磁盘的访问次数；
B+树的叶子节点之间按顺序进行了连接，方便顺序查找的场景；

B+树的维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以“InnoDB的索引模型”中这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。
而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

（基于B+树维护的特性，一般情况下的建表规范会要求主键自增，就是为了避免在树的中间范围内进行插入数据，另一方面，主键越小，中间结点能够装的节点越多，树越矮）

InnoDB的索引模型

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

每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。这个表的建表语句是：


mysql> create table T(
id int primary key, 
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)，两棵树的示例示意图如下。

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。
主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

索引优化


mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;
insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

在这个表 T 中，如果我执行 select * from T where k between 3 and 5，需要执行几次树的搜索操作，会扫描多少行？
1.在 k 索引树上找到 k=3 的记录，取得 ID = 300；
2.再到 ID 索引树查到 ID=300 对应的 R3；
3.在 k 索引树取下一个值 k=5，取得 ID=500；
4.再回到 ID 索引树查到 ID=500 对应的 R4；
5.在 k 索引树取下一个值 k=6，不满足条件，循环结束。

在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录（步骤 1、3 和 5），回表了两次（步骤 2 和 4）。

覆盖索引

在索引中覆盖需要查询出来的字段，可以免去回表这个步骤；
比如 select id from T where k between 3 and 5; 走的是字段k的索引，索引字段覆盖了需要查询出来的id，因此不需要回表，如果想要覆盖更多的字段，可以建立联合索引

最左前缀原则


CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

现在有一张市民表，从图上可以看出，联合索引就是按照索引中字段定义的顺序来进行排列，所有的条件查询中涉及到从最左边开始连续的组合都可以走这个联合索引，比如上图中的 where name=xx and age=yy 或者where name=xx这两种都可以走(name,age)这个联合索引，又比如(a,b,c)这样的联合索引，(a),(a,b),(a,b,c)都可以走这个索引，但是(b),(b,c)这样的就走不了

索引下推

索引下推针对的是筛选条件不能完全使用最左前缀定位到记录时，每一条都需要回表到主键索引中查看条件值，那么在遍历索引的过程中，可以把最左前缀中能用到的值直接使用，去掉不满足的那些记录避免对这部分进行回表
比如 where name like “%张%” and age = 10 and female=1 ，使用了索引下推和不使用的区别如下：

不使用索引下推

使用了索引下推

索引下推的解释

ICP（index condition pushdown）是mysql利用索引（二级索引）元组和筛字段在索引中的where条件从表中提取数据记录的一种优化操作。ICP的思想是：存储引擎在访问索引的时候检查筛选字段在索引中的where条件（pushed index condition，推送的索引条件），如果索引元组中的数据不满足推送的索引条件，那么就过滤掉该条数据记录。ICP（优化器）尽可能的把index condition的处理从server层下推到storage engine层。storage engine使用索引过过滤不相关的数据，仅返回符合index condition条件的数据给server层。也是说数据过滤尽可能在storage engine层进行，而不是返回所有数据给server层，然后后再根据where条件进行过滤。使用ICP（mysql 5.6版本以前）和没有使用ICP的数据访问和提取过程如下（插图来在MariaDB Blog）：

优化器没有使用ICP时，数据访问和提取的过程如下：

当storage engine读取下一行时，首先读取索引元组（index tuple），然后使用索引元组在基表中（base table）定位和读取整行数据。
sever层评估where条件，如果该行数据满足where条件则使用，否则丢弃。
执行1），直到最后一行数据。

优化器使用ICP时，server层将会把能够通过使用索引进行评估的where条件下推到storage engine层。数据访问和提取过程如下：

storage engine从索引中读取下一条索引元组。
storage engine使用索引元组评估下推的索引条件。如果没有满足wehere条件，storage engine将会处理下一条索引元组（回到上一步）。只有当索引元组满足下推的索引条件的时候，才会继续去基表中读取数据。
如果满足下推的索引条件，storage engine通过索引元组定位基表的行和读取整行数据并返回给server层。
server层评估没有被下推到storage engine层的where条件，如果该行数据满足where条件则使用，否则丢弃。

而使用ICP时，如果where条件的一部分能够通过使用索引中的字段进行评估，那么mysql server把这部分where条件下推到storage engine（存储引擎层）。存储引擎通过索引元组的索引列数据过滤不满足下推索引条件的数据行。

索引条件下推的意思就是筛选字段在索引中的where条件从server层下推到storage engine层，这样可以在存储引擎层过滤数据。由此可见，ICP可以减少存储引擎访问基表的次数和mysql server访问存储引擎的次数。

注意一下ICP的使用条件：

只能用于二级索引(secondary index)。
explain显示的执行计划中type值（join 类型）为range、 ref、 eq_ref或者ref_or_null。且查询需要访问表的整行数据，即不能直接通过二级索引的元组数据获得查询结果(索引覆盖)

ICP的开启优化功能与关闭

MySQL5.6可以通过设置optimizer_switch([global|session],dynamic)变量开启或者关闭index_condition_push优化功能，默认开启。

mysql > set optimizer_switch=’index_condition_pushdown=on|off’

用explain查看执行计划时，如果执行计划中的Extra信息为“using index condition”，表示优化器使用的index condition pushdown。

在mysql5.6以前，还没有采用ICP这种查询优化，where查询条件中的索引条件在某些情况下没有充分利用索引过滤数据。假设一个组合索引（多列索引）K包含（c1,c2,…,cn）n个列，如果在c1上存在范围扫描的where条件，那么剩余的c2,…,cn这n-1个上索引都无法用来提取和过滤数据（不管不管是唯一查找还是范围查找），索引记录没有被充分利用。即组合索引前面字段上存在范围查询，那么后面的部分的索引将不能被使用，因为后面部分的索引数据是无序。比如，索引key（a，b）中的元组数据为(0,100)、(1,50)、（1，100），where查询条件为 a < 2 and b = 100。由于b上得索引数据并不是连续区间，因为在读取（1，50）之后不再会读取（1，100），mysql优化器在执行索引区间扫描之后也不再扫描组合索引其后面的部分。

表结构定义如下：

CREATE TABLE person (
person_id smallint(5) unsigned NOT NULL AUTO_INCREMENT,
postadlcode int(11) DEFAULT NULL,
age tinyint(4) DEFAULT NULL,
first_name varchar(45) NOT NULL,
last_name varchar(45) NOT NULL,
last_update timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
PRIMARY KEY (person_id),
KEY idx_p_a (postadlcode,age),
KEY idx_f_l (first_name,last_name)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8

关闭ICP优化，Extra信息为“Using Where”

mysql> set optimizer_switch = "index_condition_pushdown=off";
mysql> explain select  *   from person  where postadlcode between 300000 and 400000 and age > 40;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | person | range | idx_p_a       | idx_p_a | 7       | NULL |   21 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

开启ICP之后，Extra信息为“Using Index Condition”

mysql> set optimizer_switch = "index_condition_pushdown=on";
mysql> explain select  *   from person  where postadlcode between 300000 and 400000 and age > 40;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra                 |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------+
|  1 | SIMPLE      | person | range | idx_p_a       | idx_p_a | 7       | NULL |   21 | Using index condition |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-----------------------+

前缀索引

  可以选取一个字段的前n个字节建立索引，使用前缀索引的好处是减少索引节点的大小，坏处是可能使表的扫描次数增多，并且无法使用覆盖索引（因为必须回表）；<br />      确定前缀索引长度的方法：

首先使用下面这个SQL确定该字段有多少个不同值


mysql> select count(distinct email) as L from SUser;

计算候选长度的不同数量，然后确定精度损失的比率，比如5%，那么就选择最短的达到了95%的那个长度


mysql> select 
  count(distinct left(email,4)）as L4,
  count(distinct left(email,5)）as L5,
  count(distinct left(email,6)）as L6,
  count(distinct left(email,7)）as L7,
from SUser;

建立前缀索引的其他技巧：
比如对于一个地区的身份证号码字段上建立索引，前面的七八位都是相同的；
（1）倒序存储身份证号


mysql> select field_list from t where id_card = reverse('input_id_card_string');

（2）使用hash计算的方式
你可以在表上再创建一个整数字段，来保存身份证的校验码，同时在这个字段上创建索引。mysql> alter table t add id_card_crc int unsigned, add index(id_card_crc);然后每次插入新记录的时候，都同时用 crc32() 这个函数得到校验码填到这个新字段。由于校验码可能存在冲突，也就是说两个不同的身份证号通过 crc32() 函数得到的结果可能是相同的，所以你的查询语句 where 部分要判断 id_card 的值是否精确相同。

mysql> 
select field_list from t 
where id_card_crc=crc32('input_id_card_string') and id_card='input_id_card_string'

这样，索引的长度变成了 4 个字节，比原来小了很多。