Mysql InnoDB索引与算法原理
InnoDB存储引擎索引概述
InnoDB 存储引擎索引有
(1)B+ 树索引
(2)全文索引
(3)哈希索引
B+树
B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树和索引顺序访问方法（ISAM，是不是很熟悉？对，这也是MyISAM引擎最初参考的数据结构）演化而来，但是在实际使用过程中几乎已经没有使用B树的情况了。
B+树的定义十分复杂，因此只简要地介绍B+树：B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。
我们先来看一个B+树，其高度为2，每页可存放4条记录，扇出（fan out）为5。
可以看出，所有记录都在叶节点中，并且是顺序存放的，如果我们从最左边的叶节点开始顺序遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90。
B+树的插入操作
B+树的插入必须保证插入后叶节点中的记录依然排序，同时需要考虑插入B+树的三种情况，每种情况都可能会导致不同的插入算法，如表5-1所示。
我们用实例来分析B+树的插入，我们插入28这个键值，发现当前Leaf Page和Index Page都没有满，我们直接插入就可以了。
这次我们再插入一条70这个键值，这时原先的Leaf Page已经满了，但是Index Page还没有满，符合表5-1的第二种情况，这时插入Leaf Page后的情况为50、55、60、65、70。我们根据中间的值60拆分叶节点。
因为图片显示的关系，这次我没有能在各叶节点加上双向链表指针。最后我们来插入记录95，这时符合表5-1讨论的第三种情况，即Leaf Page和Index Page都满了，这时需要做两次拆分。
可以看到，不管怎么变化，B+树总是会保持平衡。但是为了保持平衡，对于新插入的键值可能需要做大量的拆分页（split）操作，而B+树主要用于磁盘，因此页的拆分意味着磁盘的操作，应该在可能的情况下尽量减少页的拆分。因此，B+树提供了旋转（rotation）的功能。
旋转发生在Leaf Page已经满了、但是其左右兄弟节点没有满的情况下。这时B+树并不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。通常情况下，左兄弟被首先检查用来做旋转操作，这时我们插入键值70，其实B+树并不会急于去拆分叶节点，而是做旋转，50，55，55旋转。
可以看到，采用旋转操作使B+树减少了一次页的拆分操作，而这时B+树的高度依然还是2。
B+树的删除操作
B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑如表5-2所示的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。
首先，删除键值为70的这条记录，该记录符合表5-2讨论的第一种情况，删除后。
接着我们删除键值为25的记录，这也是表5-2讨论的第一种情况，但是该值还是Index Page中的值，因此在删除Leaf Page中25的值后，还应将25的右兄弟节点的28更新到Page Index中，最后可得到图。
最后我们来看删除键值为60的情况，删除Leaf Page中键值为60的记录后，填充因子小于50%，这时需要做合并操作，同样，在删除Index Page中相关记录后需要做Index Page的合并操作，最后得到图。
InnoDB的B+树索引
B+树索引其本质就是B+树在数据库中的实现，但是B+索引在数据库中有一个特点就是其高扇出性，因此在数据库中，B+树的高度一般都在2～3层，也就是对于查找某一键值的行记录，最多只需要2到3次IO，这倒不错。因为我们知道现在一般的磁盘每秒至少可以做100次IO，2～3次的IO意味着查询时间只需0.02～0.03秒。
数据库中的B+树索引可以分为聚集索引（clustered index）和辅助聚集索引（secondary index）辅助聚集索引有时也称非聚集索引（non-clustered index）。
但是不管是聚集还是非聚集的索引，其内部都是B+树的，即高度平衡的，叶节点存放着所有的数据。聚集索引与非聚集索引不同的是，叶节点存放的是否是一整行的信息。
聚集索引
InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，并且叶节点中存放着整张表的行记录数据，因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。
由于实际的数据页只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。在许多情况下，查询优化器非常倾向于采用聚集索引，因为聚集索引能够让我们在索引的叶节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。
现在我们来看一张表，我们以人为的方式让其每个页只能存放两个行记录，如：
MySQL [qiushibaike]> create table t(
-> a int not null,
-> b varchar(8000),
-> c int not null,
-> primary key (a),
-> key idx_c(c)
-> )engine=INNODB;
```~
```~
insert into t select 1,repeat('a',7000),-1;
insert into t select 2,repeat('a',7000),-2;
insert into t select 3,repeat('a',7000),-3;
insert into t select 4,repeat('a',7000),-4;
```~
可以看到，我们表的定义和插入方式使得目前每个页只能存放两个行记录，我们用py_innodb_page_info工具来分析表空间，可得：py_innodb_page_info.py-v mytest/t.ibd
page level为0000的即是数据页。我们要分析的是page level为0001的页，该页是B+树的根，我们来看看索引的根页中存放的数据。
我们直接通过页尾的Page Directory来分析，从00 63可以知道该页中行开始的位置。接着通过Recorder Header来分析，0xc063开始的值为69 6e 66 69 6d 75 6d 00，就代表infimum伪行记录。之前的5个字节01 00 02 00 1b就是Recorder Header，分析第4位到第8位的值1代表该行记录中只有一个记录（需要记住的是，InnoDB的Page Directory是稀疏的），即infimum记录本身。我们通过Recorder Header中最后的两个字节00 1b来判断下一条记录的位置，即c063+1b=c073，读取键值可得80 01，就是主键为1的键值（我们制定的INT是无符号的，因此二进制是0x8001，而不是0x0001），80 01后值00 00 00 04代表指向数据页的页号。以同样的方式，可以找到80 02和80 04这两个键值以及它们指向的数据页。
通过以上对于非数据页节点的分析，我们发现数据页上存放的是完整的行记录，而在非数据页的索引页中，存放的仅仅是键值以及指向数据页的偏移量，而不是一个完整的行记录。因此我们构造的这颗二叉树大致如图5-14所示。
许多数据库的文档会这样告诉读者：聚集索引按照顺序物理地存储数据。但是试想，如果聚集索引必须按照特定顺序存放物理记录的话，则维护成本即显得非常之高了。所以，聚集索引的存储并不是物理上的连续，相反是逻辑上连续的。这其中有两点：一是我们前面说过的页通过双向链表链接，页按照主键的顺序排列。另一点是每个页中的记录也是通过双向链表进行维护，物理存储上可以同样不按照主键存储。
聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶节点的数据就是我们要查询的数据，如我们要查询一张注册用户的表，查询最后注册的10位用户，由于B+树索引是双向链表的，我们可以快速找到最后一个数据页，并取出10条记录，我们用Explain进行分析，可得：
`explain select * from Profile order by id limit 10;`
另一个是范围查询（range query），如果要查找主键某一范围内的数据，通过叶节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可，又如：
`explain select * from Profile where id＞10 and id＜10000;`
Explain得到了MySQL的执行计划（execute plan），并且rows列给出了一个查询结果的预估返回行数。要注意的是，rows代表的是一个预估值，不是确切的值，如果我们实际进行这句SQL的查询，可以看到实际上只有9 946行记录：
`select count(*) from Profile where id＞10 and id＜10000; `
### 辅助索引
对于辅助索引（也称非聚集索引），叶级别不包含行的全部数据。叶节点除了包含键值以外，每个叶级别中的索引行中还包含了一个书签（bookmark），该书签用来告诉InnoDB存储引擎，哪里可以找到与索引相对应的行数据。因为InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。显示了InnoDB存储引擎中辅助索引与聚集索引的关系。
辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。举例来说，如果在一颗高度为3的辅助索引树中查找数据，那么需要对这颗辅助索引遍历3次找到指定主键；如果聚集索引树的高度同样为3，那么还需要对聚集索引进行3次查找，才能最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO来访问最终的一个数据页。
对于其他的一些数据库，如Microsoft SQL Server数据库，其表类型有一种不是索引组织表，称为堆表。在数据的存放按插入顺序方面，与MySQL的MyISAM存储引擎有些类似。堆表的特性决定了堆表上的索引都是非聚集的，但是堆表没有主键。因此这时书签是一个行标识符（row identifier，RID），可以用如“文件号：页号：槽号”的格式来定位实际的行。
堆表的非聚集索引既然不需要再通过主键对聚集索引进行查找，那不是速度会更快吗？答案是也许，在某些只读的情况下，书签为行标识符方式的非聚集索引可能会比书签为主键方式的非聚集索引快。但是考虑在OLTP（OnLine Transaction Processing，在线事务处理）应用的情况下，表可能还需要发生插入、更新、删除等DML操作。当进行这类操作时，书签为行标识符方式的非聚集索引可能需要不断更新行标识符所指向数据页的位置，这时的开销可能就会大于书签为主键方式的非聚集索引了。
Microsoft SQL Server数据库DBA问过这样的问题，为什么在SQL Server上还要使用索引组织表？堆表的书签性使得非聚集查找可以比主键书签方式更快，并且非聚集可能在一张表中存在多个，我们需要对多个非聚集索引的查找。而且对于非聚集索引的离散读取，索引组织表上的非聚集索引会比堆表上的聚集索引慢一些。当然，在一些情况下，使用堆表的确会比索引组织表更快，但是我觉得大部分是由于存在于OLAP（On-Line Analytical Processing，在线分析处理）的应用。其次就是前面提到的，表中数据是否需要更新，并且更新会否影响到物理地址的变更。此外另一个不能忽视的是对于排序和范围查找，索引组织表可以通过B+树的中间节点就找到要查找的所有页，然后进行读取，而堆表的特性决定了这对其是不能实现的。最后，非聚集索引的离散读，的确是存在上述情况，但是一般的数据库都通过实现预读（read ahead）技术来避免多次的离散读操作。因此，具体是建堆表还是索引组织表，这取决于你的应用，不存在哪个更优的情况。这和InnoDB存储引擎好还是MyISAM存储引擎好的问题是一样的，具体情况具体分析。
接下来，我们通过阅读表空间文件来分析InnoDB存储引擎的非聚集索引，我们还是分析上一小节所用的表t。
不同的是，在表t上再建立一个列c，并对列c创建非聚集索引：
```~
alter table t add c int not null;
update t set c=0-a;
alter table t add key idx_c(c);
show index from t;
select a,c from t;
```~
然后用py_innodb_page_info工具来分析表空间，可得：py_innodb_page_info.py-v t.ibd
对比前一次我们的分析，可以看到这次多了一个页。分析page offset为4的页，该页为非聚集索引所在页，通过工具hexdump分析可得：
因为只有4行数据，并且列c只有4个字节，因此在一个非聚集索引页中即可完成，整理分析可得下图所示的关系：
显示了表t中辅助索引idx_c和聚集索引的关系。可以看到辅助索引的叶节点中包含了列c的值和主键的值。这里键值因为我特意设为负值，你会发现-1以7f ff ff ff的方式进行内部存储。7（0111）最高位为0，代表负值，实际的值应该取反后，加1，即得-1。
### B+树索引的管理
索引的创建和删除可以通过两种方法，一种是ALTER TABLE，另一种是CREATE/DROP INDEX。ALTER TABLE创建索引的语法为：
```~
ALTER TABLE tbl_name
|ADD{INDEX|KEY}[index_name]
[index_type] (index_col_name，……) [index_option]……
ALTER TABLE tbl_name
DROP PRIMARY KEY
|DROP {INDEX|KEY} index_name
CREATE/DROP INDEX的语法同样很简单：
CREATE [UNIQUE] INDEX index_name
[index_type]
ON tbl_name（index_col_name，……）
DROP INDEX index_name ON tbl_name
```~
索引可以索引整个列的数据，也可以只索引一个列的开头部分数据，如前面我们创建的表t，b列为varchar(8000)，但是我们可以只索引前100个字段，如：
`alter table t add key idx_b (b(100));`
目前MySQL数据库存在的一个普遍问题是，所有对于索引的添加或者删除操作，MySQL数据库是先创建一张新的临时表，然后把数据导入临时表，删除原表，再把临时表重名为原来的表名。因此对于一张大表，添加和删除索引需要很长的时间。对于从Microsoft SQL Server或Oracle数据库的DBA来说，MySQL数据库的索引维护始终让他们非常苦恼。
InnoDB存储引擎从版本InnoDB Plugin开始，支持一种称为快速索引创建方法。当然这种方法只限定于辅助索引，对于主键的创建和删除还是需要重建一张表。对于辅助索引的创建，InnoDB存储引擎会对表加上一个S锁。在创建的过程中，不需要重建表，因此速度极快。但是在创建的过程中，由于上了S锁，因此创建的过程中该表只能进行读操作。删除辅助索引操作就更简单了，只需在InnoDB存储引擎的内部视图更新下，将辅助索引的空间标记为可用，并删除MySQL内部视图上对于该表的索引定义即可。
查看表中索引的信息可以使用SHOW INDEX语句。如我们来分析表t，之前先加一个联合索引，可得：
`alter table t add key idx_a_b(a,c);`
`show index from t;`
因为在表t上有3个索引：一个主键索引，c列上的索引，和b列前100个字节构成的索引。
接着我们来具体讲解每个列的含义：
**Table**：索引所在的表名。
**Non_unique**：非唯一的索引，可以看到primary key是0，因为必须是唯一的。
**Key_name**：索引的名称，我们可以通过这个名称来DROP INDEX。
**Seq_in_index**：索引中该列的位置，如果看联合索引idx_a_b就比较直观了。
**Column_name**：索引的列
**Collation**：列以什么方式存储在索引中。可以是'A'或者NULL。B+树索引总是A，即排序的。如果使用了Heap存储引擎，并且建立了Hash索引，这里就会显示NULL了。因为Hash根据Hash桶来存放索引数据，而不是对数据进行排序。
**Cardinality**：非常关键的值，表示索引中唯一值的数目的估计值。Cardinality/表的行数应尽可能接近1，如果非常小，那么需要考虑是否还需要建这个索引。
**Sub_part**：是否是列的部分被索引。如果看idx_b这个索引，这里显示100，表示我们只索引b列的前100个字符。如果索引整个列，则该字段为NULL。
**Packed**：关键字如何被压缩。如果没有被压缩，则为NULL。
**Null**：是否索引的列含有NULL值。可以看到idx_b这里为Yes。因为我们定义的b列允许NULL值。
**Index_type**：索引的类型。InnoDB存储引擎只支持B+树索引，所以这里显示的都是BTREE。
**Comment**：注释。
**Cardinality**值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的，并非每次索引的更新都会更新该值，因为这样代价太大了。因此这个值是不太准确的，只是一个大概的值。上面显示的结果主键的Cardinality为2，但是很显然我们表中有4条记录，这个值应该是4。如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。如：
**`analyze table t;`**
**`show index from t;`**
这时的Cardinality的值就对了。不过，在每个系统上可能得到的结果不一样，因为ANALYZE TABLE现在还存在一些问题，可能会影响得到最后的结果。
另一个问题是MySQL数据库对于Cardinality计数的问题，在运行一段时间后，可能会看到下面的结果：
`show index from Profile;`
Cardinality为NULL，在某些情况下可能会发生索引建立了、但是没有用到，或者explain两条基本一样的语句，但是最终出来的结果不一样。一个使用索引，另外一个使用全表扫描，这时最好的解决办法就是做一次ANALYZE TABLE的操作。因此我建议在一个非高峰时间，对应用程序下的几张核心表做ANALYZE TABLE操作，这能使优化器和索引更好地为你工作。
****
## Cardinality值
### 什么是Cardinality值
不是所有的查询条件出现的列都需要添加索引。对于什么时候添加B+树索引。一般的经验是，在访问表中很少一部分时使用B+树索引才有意义。对于性别字段、地区字段、类型字段，他们可取值范围很小，称为低选择性。如
SELECT * FROM student WHERE sex='M'
按性别进行查询时，可取值一般只有M、F。因此SQL语句得到的结果可能是该表50%的数据(加入男女比例1:1)这时添加B+树索引是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，属于高选择性。则此时使用B+树的索引是最合适的。例如对于姓名字段，基本上在一个应用中不允许重名的出现
怎样查看索引是否有高选择性？通过SHOW INDEX结果中的列Cardinality来观察。非常关键，表示所以中不重复记录的预估值，需要注意的是Cardinality是一个预估值，而不是一个准确值基本上用户也不可能得到一个准确的值，在实际应用中，Cardinality/n_row_in_table应尽可能的接近1，如果非常小,那用户需要考虑是否还有必要创建这个索引。故在访问高选择性属性的字段并从表中取出很少一部分数据时，对于字段添加B+树索引是非常有必要的。如
SELECT * FROM member WHERE usernick='David';
表member大约有500W行数据,usernick字段上有一个唯一索引。这是如果查找用户名为David的用户，将得到如下执行计划
可以看到使用了usernick这个索引。这也符合之前提到的高可选择性，即SQL语句取表中较少行的原则
### InnoDB存储引擎的Cardinality统计
建立索引的前提是高选择性。这对数据库来说才具有实际意义，那么数据库是怎样统计Cardinality的信息呢?因为MySQL数据库中有各种不同的存储引擎，而每种存储引擎对于B+树索引的实现又各不相同。所以对Cardinality统计时放在存储引擎层进行的
在生成环境中，索引的更新操作可能非常频繁。如果每次索引在发生操作时就对其进行Cardinality统计，那么将会对数据库带来很大的负担。另外需要考虑的是，如果一张表的数据非常大，如一张表有50G的数据，那么统计一次Cardinality信息所需要的时间可能非常长。这样的环境下，是不能接受的。因此，数据库对于Cardinality信息的统计都是通过采样的方法完成
在InnoDB存储引擎中，Cardinality统计信息的更新发生在两个操作中：insert和update。InnoDB存储引擎内部对更新Cardinality信息的策略为:
***表中1/16的数据已发生了改变***
***stat_modified_counter>2000 000 000***
第一种策略为自从上次统计Cardinality信息后，表中的1/16的数据已经发生过变化，这是需要更新Cardinality信息
第二种情况考虑的是，如果对表中某一行数据频繁地进行更新操作，这时表中的数据实际并没有增加，实际发生变化的还是这一行数据，则第一种更新策略就无法适用这种情况，故在InnoDB存储引擎内部有一个计数器start_modified_counter,用来表示发生变化的次数,当start_modified_counter>2 000 000 000 时，则同样更新Cardinality信息
接着考虑InnoDB存储引擎内部是怎样进行Cardinality信息统计和更新操作呢？同样是通过采样的方法。默认的InnoDB存储引擎对8个叶子节点Leaf Page进行采用。采用过程如下
取得B+树索引中叶子节点的数量，记为A
随机取得B+树索引中的8个叶子节点，统计每个页不同记录的个数，即为P1，P2....P8
通过采样信息给出Cardinality的预估值: **Cardinality=(P1+P2+...+P8)\*A/8**
根据上述的说明可以发现，在InnoDB存储引擎中，Cardinality值通过对8个叶子节点预估而得的。而不是一个实际精确的值。再者，每次对Cardinality值的统计，都是通过随机取8个叶子节点得到的，这同时有暗示了另外一个Cardinality现象，即每次得到的Cardinality值可能不同的，如
`SHOW INDEX FROM OrderDetails`
上述SQL语句会触发MySQL数据库对于Cardinality值的统计，第一次运行得到的结果如图5-20
在上述测试过程中，并没有通过INSERT、UPDATE这类的操作来改变OrderDetails中的内容，但是当第二次运行SHOW INDEX FROM OrderDetails语句是，发生了变化，如图5-21
可以看到，当第二次运行SHOW INDEX FROM OrderDetails语句时，表OrderDetails索引中的Cardinality值发生了变化，虽然表OrderDetails本身并没有发生任何变化，但是由于Cardinality是随机取8个叶子节点进行分析，所以即使表没有发生变化，用户观察到索引Cardinality值还是会发生变化，这本身不是Bug,而是随机采样而导致的结果
当然，有一种情况可以使得用户每次观察到的索引Cardinality值是一样的。那就是表足够小，表的叶子节点树小于或者等于8个。这时即使随机采样，也总是会采取倒这些页，因此每次得到的Cardinality值是相同的
在InnoDB1.2版本之前，可以通过innodb_stats_sample_pages用来设置统计Cardinality时每次采样页的数量，默认为8.同时，参数innodb_stats_method用来判断如何对待索引中出现NULL值记录。该参数默认值为nulls_equal,表示将NULL值记录为相等的记录。其有效值还nulls_unequal,nulls_ignored,分别表示将NULL值记录视为不同的记录和忽略NULL值记录。例如某夜中索引记录为NULL、NULL、1、2、2、3、3、3,在参数innodb_stats_method默认设置下，该页的Cardinality为4；若参数innodb_stats_method为nulls_unequal,则该页的Cardinality为5，若参数innodb_stats_method为nulls_ignored，则Cardinality值为3
当执行ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX 以及访问INFORMATION_SCHEMA架构下的表TABLES和STATISTICS时会导致InnoDB存储引擎会重新计算索引Cardinality值，若表中的数据量非常大，并且表中存在多个辅助索引时，执行上述操作可能会非常慢，虽然用户可能并不希望去更新Cardinality值
InnoDB1.2版本提供了更多参数对Cardinality进行设置。如表
*****
## B+树索引的使用
并不是在所有的查询条件下出现的列都需要添加索引。对于什么时候添加B+树索引，我的经验是访问表中很少一部分行时，使用B+树索引才有意义。对于性别字段、地区字段、类型字段，它们可取值的范围很小，即低选择性。
对于性别，可取值的范围只有'M'、'F'。对上述SQL语句得到的结果可能是该表50%的数据（我们假设男女比例1：1），这时添加B+树索引是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即高选择性，则此时使用B+树索引是最适合的，例如姓名字段，基本上在一个应用中都不允许重名的出现。
因此，当访问高选择性字段并从表中取出很少一部分行时，对这个字段添加B+树索引是非常有必要的。但是如果出现了访问字段是高选择性的，但是取出的行数据占表中大部分的数据时，这时MySQL数据库就不会使用B+树索引了。
## 联合索引
联合索引 运用的是多个索引列。 创建方法跟单个索引一样。
这么做的好处就是
第一：是使用了B+树索引
第二：已经对第二个键值进行排序了
**注意：但是对于单个列查询是不引起联合索引。**
关联查询的查询语句: select * from 表名 where id = *** and user= ***
```~
create table buy_log(
userid int unsigned not null,
buy_date date
)engine=InnoDB;
insert into buy_log values(1,'2009-01-01');
insert into buy_log values(2,'2009-01-01');
insert into buy_log values(3,'2009-01-01');
insert into buy_log values(1,'2009-02-01');
insert into buy_log values(3,'2009-02-01');
insert into buy_log values(1,'2009-03-01');
insert into buy_log values(1,'2009-04-01');
insert into buy_log values(1,'2009-05-01');
alter table buy_log add key (userid);
alter table buy_log add key (userid,buy_date);
```~
只对userid查询
`explain select * from buy_log where userid=2`
possible_keys 说明有两个索引可以用 userid,userid_2 但是优化器选择了userid
`explain select * from buy_log where userid=1 order by buy_date limit 3`
这里运用到了两个字段 所以优化器会选择userid_2 因为联合索引userid_2 已经排序好 buy_date
也可以 (a,b,c)当做联合索引但是如:
`select * from buy_log where a=*** order by c`
这个情况就运行不了联合索引 因为c并不需要排序
### 覆盖索引
InnoDB在1.0之后 或者 MySQL 在5.0或者以下的不支持覆盖索引。 就是从辅助索引中查询的记录，而不需要查询聚集索引中的记录。 好处就是辅助索引不包含整个行记录的所有信息，骨气大小远小于聚集索引。因此可以减少大量的IO操作。
`explain select count(*) from buy_log;`
**Using index：表示使用索引，如果只有 Using index，说明他没有查询到数据表，只用索引表就完成了这个查询，这个叫覆盖索引。**
`explain select count(*) from buy_log where buy_date >= '2011-01-01' and buy_date <'2011-02-01'`
**如果同时出现Using where，代表使用索引来查找读取记录， 也是可以用到索引的，但是需要查询到数据表。**
### 优化器选择不使用索引的情况
当执行 explain命令进行sql语句分析时,就会发现优化器并没有选择索引去查找数据,而是通过扫描聚集索引,也就是直接进行全表的扫描来得到的数据。 这种情况多发生与范围查找、JOIN链接操作等情况下。
可以通过`show index from 表名`查询索引
可以看出该表是有使用(OrderID,ProductID)的联合主键,此外还有OrderID的单个索引.
`select * from 表名 where orderid > 10000 and orderid<10200;`
选择的是聚集索引而非辅助索引,原因是:OrderID索引不能覆盖到我们要查询的信息。虽然OrderID索引数据是顺序存放，但是再次进行书签查找数据是无序的，因此变为磁盘上离散读操作。如果要求访问的数据量小，则优化器还是会选择辅助索引，但是数据大的时候（一般20%左右），优化器会选择通过聚集索引来查找数据。因为顺序读比离散读快，但是如果是固态硬盘，随机读猜中非常快，同时自信确定使用辅助索引可以带来更好的性能 可以使用关键词 `FORCE INDEX` 来强制使用摸个索引,如:`select * from 表名 force index(OrderID) where orderid > 10000 and orderid<10200;`
**`USE INDEX`:这个指令只是建议优化器使用这个索引 而 `FORCE INDEX` 来强制使用摸个索引**
### Multi-Range Read 优化
MySQL5.6版本开始 支持 Multi-Range Read (MRR)优化。其目的是为了减少磁盘的随机访问，并且将随机访问转化为顺序的数据访问 这对 IO-bound类型的SQL查询语句可带来性能极大的提升。MRR适用于range，ref，eq_ref类型的查询。
MRR优化有以下几个好处：
（1）MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。
（2）减少缓冲池中页被替换的次数。
（3）批量处理对键值的查询操作。
对InnoDB和MyISAM存储引擎的范围查询和JOIN查询操作MRR工作方式如下：
（1）讲查询得到的辅助索引键值存放在一个缓存中，这时缓存重点数据是根据辅助索引键值排序的。
（2）将缓存中的键值根据RowID进行排序。
（3）根据RowID的排序顺序来访问实际的数据文件。
此外 混吃次不是足够大，不能放下一张表中的所有数据，此时离散读操作会导致缓存中的页被替换出缓冲池，然后又不断读入换冲池。若是安装主键访问，则可以将此重复行为降为最低。
`select * from t where key_part1 >=1000 and key_part1 <2000 and key_part2 =10000`
表中 ( key_part1,key_part2)的联合索引,因此索引根据key_part1,key_part2的位置关系排序 没有 MRR查询类型为Range,sql优化器会先将key_part1大于1000 且小于2000的数据都取出,即使key_part2不等于10000。取出后进行过滤。这导致无用数据被取出。 如果启用MRR 会使其性能大大的提升。
优化器会将查询条件拆分为（1000,10000）（1001,10000），....，（1999,10000），最后进行数据的查询。
速度也是相差很大的。
启动方法:optimizer_switch 中的标记(flag)来控制。 总是开启MRR。
`SET @@optimizer_switch = 'mrr=on,mrr_cost_based=off';`
read_rnd_buffer_size 用来控制键值的缓冲区大小,默认为256k;
查看命令: `select @@read_rnd_buffer_size\G`;
### Index Condition Pushdown( ICP )优化
需要在MySQL5.6版本支持这种根据索引进行查询的优化方式.之前的MySQL版本不支持Index Condition Pushdown, 首先是根据索引来查找记录,然后在根据where条件来过滤记录。 在支持Index Condition Pushdown后，MySQL数据库会取出索引的同时，判断是否进行where条件的过滤，也就是将where的部分过滤操作放在存储引擎层。在某些查询下，可以大大减少上层SQL层对记录的索取（fetch），从而提高数据库的整体性能。
Index Condition Pushdown( ICP )优化支持range，ref，eq_ref，ref_or_null类型的查询。当前支持MyISAM和InnoDB存储引擎。
****
Extra表示附加信息，常见的有如下几种（也按查询效率从高到低排列）：
Using index：表示使用索引，如果只有 Using index，说明他没有查询到数据表，只用索引表就完成了这个查询，这个叫覆盖索引。如果同时出现Using where，代表使用索引来查找读取记录， 也是可以用到索引的，但是需要查询到数据表。
Using where：表示条件查询，如果不读取表的所有数据，或不是仅仅通过索引就可以获取所有需要的数据，则会出现 Using where。如果type列是ALL或index，而没有出现该信息，则你有可能在执行错误的查询：返回所有数据。
Using filesort：不是“使用文件索引”的含义！filesort是MySQL所实现的一种排序策略，通常在使用到排序语句ORDER BY的时候，会出现该信息。
Using temporary：表示为了得到结果，使用了临时表，这通常是出现在多表联合查询，结果排序的场合。
**如果EXPLAIN出现后面两个信息（Using filesort，Using temporary），而rows又比较大，通常意味着你需要调整查询语句，或者需要添加索引，总之需要尽量消除这两个信息。**
## 哈希算法
### 哈希表
哈希表 也称为散列表,用一个数组(即直接寻址表)T[0..m-1]表示动态集合,其中每个位置(或称槽或者桶)对应全域U中的一个关键字。图说明了这个方法k指向集合中的一个关键字为K的元素。如果集合中没有关键词k的元素 则T[k]=NULL;
元素h（k）利用哈希函数h，根据关键字k计算出槽位置。函数h将关键词域U映射到哈希T[0..m-1]的槽位上。但是两个关键词可能映射到同一个槽上。这种情况称为碰撞。链接法解决碰撞问题。
:-:
一般使用除法散列法：哈希函数：h（k）=k mod m；
### 哈希索引
哈希索引只能通过 等值条件查找如:`select * from 表名 where id_x=1;`
通过 `show engine innodb status\G;`
通过参数 innodb_adaptive_hash_index来禁用和启动特性,默认为开启。
## 全文检索
全文检索(full_test search)是将存储于数据库中的整本书或者整篇文章中的任意内容信息查找出来的技术。它可以根据需要获取全文中有关的章、节、段、句等信息，也可以进行各种统计和分析。
InnoDB在1.2.X开始之前支持全文检索，其支持MyISAM存储引擎的全部功能，并且还支持其他的一些特性。
如：`select * from 表名 where title like '中午%';` 这个语句是可以通过 B+树索引进行查询
如：`select * from 表名 where title like '%中午%';` 这个就不能用B+树能够更好的工作了
### 倒排索引
全文检索通常使用倒排索引（inverted index）来实现。倒排索引在辅助表（auxiliary table） 中存储了单词与单词自身在一个或者多个文档中所在位置之间的映射。利用相关数组实现，其拥有两种表现形式：
（1） inverted file index，其表现形式为{ 单词,单词所在的文档的ID}
（2）full inverted index,其表现形式为{ 单词,( 单词,单词所在的文档的位置)}
对 inverted file index 其仅存文档id,而full inverted index存储的是对(pair),即(DocumentId,Position),因此存储的倒排索引如下图：
full inverted index存储了单词所在的位置信息,但是同时也暂用了更多的空间,但是能更好的的定位数据。
### InnoDB全文检索
将(DocumentId,Position)视为一个“ilist”。因此全文检索的表中，有一个是word 字，另一个是ilist字段，并且word字段上设有索引。
由于Innodb 存储引擎在ilist 字段中存放了Position信息，故可以进行Proximity Search（邻近搜索），而MyISAM存储不支持改特性。
在InnoDB存储引擎中，为了提高全文检索的并行性能，共有6张Auxiliary Table（辅助表），目前每张表根据word的Latin编码进行分区
Auxiliary Table（辅助表）是持久表，存放磁盘上。在全文索引中，还有另一个重要的概念FTS Index Cache（全文索引索引缓存）来听全文检索的性能。
FTS Index Cache是一个红黑树结构，其中根据（word，ilist）进行排序。意味着插入的数据已经更新到对应的表，但是全文索引更新可能在分词操作后还在FTS Index Cache中，Auxiliary Table 可能没有更新。 InnoDB存储索引会批量对Auxiliary Table 进行更新，而不是每次插入就更新一次Auxiliary Table。当对全文检索进行查询时，Auxiliary Table首先会对FTS Index Cache 中对应的word 字段合并到Auxiliary Table中在查询. 这种合并提高了InnoDB存储引擎的性能,并且由于红黑树排序后进行批量插入,其产生Auxiliary Table相对较小。
Innodb运行用户查看置顶倒排索引的Auxiliary Table种的分词信息，可以通过参数设置innodb_ft_aux_table 来观察倒排索引的Auxiliary Table。
test 架构下表fts_a的Auxiliary Table;
`set global innodb_ft_aux_table = 'test/fts_a';`
查询test架构下的表fts_a的分词信息`select * from information_schema.INNODB_FT_INDEX_TABLE;`
参数innodb_ft_cache_size 控制FTS Index Cache的大小,默认值为32M。当该缓存满时，会将掐中的（word，ilist）分词信息同步到磁盘的Auxiliary Table中。增大参该参数可以提高全文检索的性能，但是在宕机时，未同步到磁盘重点索引信息可能需要更长的时间恢复。
FTS Document ID 是另一种概念。Innodb存储引擎中，为了支持全文检索，必须有一个列与word进行映射，这个列为FTS_DOS_ID，类型必须是 BIGINT UNSIGNED NOT NULL,并且Innodb引擎会加入名为FTS_DOC_ID_INDEX 的Unique Index. 上述操作是有Innodb引擎自己完成的。 用户也可以自己在建表时自动添加FTS_DOC_ID，已经对应的Unique Index。但是类型必须是 BIGINT UNSIGNED NOT NULL
文档分词的插入是事务提交时完成的，而对于删除操作，其在事务提交时，不删除磁盘Auxiliary Table重点记录,而只是删除FTS Cache index中的记录,对于Auxiliary Table中被删除的记录,FTS Document ID,并将其保存在DELETED auxiliary table中.在 innodb_ft_aux_table设置之后,可以访问information_schema价格下的表innodb_ft_deleted 中观察删除的FTS Document ID。文档的DML操作并不能删除索引中的数据，相反还会在对应的DELETED表中插入记录，因此随着应用程序的允许，索引会变得非常大，用户可以手工将已经删除的记录从索引中彻底删除，改命令是OPTIMIZE TABLE。该命令可以做其他的操作 所以可以通过参数innodb_optimize_
_onle进行设置。如:
set global innodb_optimize_fulltext_onlt=1;
optimize tablefts_a;
可以通过innodb_ft_num_wird_optimize 进行限制分词数量。默认为2000。
当InnoDB存储引擎的全文检索还存在以下的限制：
**（1）一个表只能有一个全文检索的索引。
（2）有多列组成的全文检索的索引列必须使用相同的字符集与排序规则。
（3）不支持没有单词界定符（delimiter） 的语言。如中文、日语、韩语等。**
#### 全文检索
MySQL 5.6.4里才添加了InnoDB引擎的Full-Text索引支持。
设置全文搜索:
```~
ALTER TABLE `表名` ADD FULLTEXT (
`字段名`
)
```~
MySQL数据库之前全文检索(Full-Text Search)的查询，其语法为：
```~
MATCH (col1,col2,....) AGAINST (expr [search_modifier])
search_modifier:
{
IN NATURAL LANGUAGE MODE
| IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION
| IN BOOLEAN MODE
|WITH QUERY EXPANSION
}
```~
MySQL 数据库通过MATCH()...AGAINST()语法支持全文检索的查询,MATCH指定了需要被查询的列,AGAINST指定了使用何种方法去进行查询。下面将对各种查询模式进行详细的介绍。
1.Natural Language
全文检索沟通过MATCH函数进行查询，默认采用Natural Language模式，其表示查询带有指定word的文档。对于创建的表fts_a，查询body 字段中带有pease的文档，若不使用全文索引技术，则允许使用下述sql语句：
`select * from fts_a where body like '%Pease%’;`
显然上述sql语句不能使用B+树索引.若采用全文检索技术,可以用下面的sql语句进行查询:
```~
select * from fts_a
where match(body)
against ('Pottidge' in natural language mode);
```~
默认是in natural languagemode 所以可以省略:`select * from cco_images where match(label) against ('Romanesco');`
查询计划`explain select * from cco_images where match(label) against ('Romanesco');`:
可以看到 type这列显示的是fulltext,即表示使用全文检索技术。同时，若表没有创建倒排索引，则只需match 函数会抛出类错误：**Can't find FULLTEXT index matching the column list** 意思是:"找不到与列列表匹配的FULLTEXT索引"。
如果使用innodb搜索引擎里的mysql版本低于3.6.4时回报：**the used table type doesn't support fulltest indexes**
翻译是：“使用的表类型不支持完整索引”
查询的范围结果是根据相关性（relevance）进行降序排序的，即相关性最高的结果放在第一位。相关性的值是一个非负的浮点数字，0表示没有任何的相关性。根据mysql官方文档可知，相关性计算根据以下四个条件：
（1）word是否在文档中出现。
（2）word在文档中出现的次数。
（3）word在索引列中的数量。
（4）多少个文档包含该word。
该查询没有经过相关性的排序 所以该查询的速度比常规的 match查询速度要快。
对于InnoDB存储引擎的全文检索，还需要考虑以下的因素：
（1）查询的word在stopword列中。忽略该字符串的查询。
（2）查询的word的字符串长度是否在区间【innodb_ft_min_token_size,innodb_ft_max_token_size】内 InnoDB存储引擎中，参数innodb_ft_min_token_size默认是3，innodb_ft_max_token_size默认是84 **如果不在范围内 这会忽略**
#### Boolean
MySQL数据库允许使用IN BOOLEAN MODE修饰符来进行全文检索。当使用该修饰符时，查询字符串的前后字符会有特殊的含义，例如下面的语句要求查询有字符串Vitaminhaltig但没有Romanesco的文档，其中+和-分别表示这个单词必须出现，或者一定不存在。
`select * fromselect * from cco_images where match(label) against ('-Romanesco +Vitaminhaltig ' in boolean mode);`
Boolean 全文检索支持一下几种操作符:
（1）+表示该word必须存在。
（2）-表示该word必须被排除
（3）（no operator）表示该word是可选的，但是如果出现，其相关性会更高
（4）@distance 表示查询的多个单词之间的距离是否在distance之内，distance的单位是字节。这种全文检索的查询也称为Proximity Search。 如MATCH(label) AGAINST ('"Pease pot"@30' IN BOOLEAN MODE) 表示字符串Peace和pot之间的距离需在30字节以内。
（5）>表示出现该单词时增加相关性。
（6）<表示出现该单词时降低相关性。
（7）~表示允许出现该单词，但是出现是相关性为负（全文检索查询运行负相关性）。
（8）* 表示以该单词开头的单词，如lik*，表示可以是lik、like，又或者likes。
（9） " 表示短语。
如果在against（里面添加上“”这表示该两个单词是一个短语） 如下：
#### query Expansion
mysql数据库支持扩展查询。 这种查询在查询的关键词太短，用户需要implied knowledge（隐含知识）时进行。
通过查询短句中添加with query expansion 或 in natural languange mode with query expansion 可以开启blind query expamsoin（又称 automaticrelevance feedback）。该查询分为两个阶段。
（1）第一阶段 根据单词进行全文索引查询。
（2）第二阶段：根据第一阶段产生的分词再进行一次全文检索的查询。内容来源于网络，如有侵权，请联系作者删除！
