索引 - 简书

InnoDB支持B+树索引、全文索引、哈希索引三种索引方式。

B+树的创建和删除操作

B+树的B是平衡（Balance）的意思。
B+ 树索引并不能找到一个给定键值的具体行。 B+ 树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。
在数据库中，B+树的高度一般都在2~4层，也就是说查找某一键值的行记录时，最多只需要2到4次IO。

创建和删除索引

索引的创建和删除可以通过两种方法，一种是alter table ，另一种是create /drop index。用户可以设置对整个列的数据进行索引，也可以只索引一个列的开头部分数据。

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 [unique] index index_name
[index_type]
on tbl_name(index_col_name,...)

drop index index_name on tbl_name;

show index命令和Cardinality值

查看表中索引的信息
show index from table_name

show index from table_name命令输出中，有一个Cardinality值，表示索引中唯一值的估计值，这个值不是实时的，可以使用命令analyze table进行实时更新，该值越大越好，应该尽可能接近表的行数，对于性别、地区这些值，一般Cardinality都比较小，不建议建立索引。
在 InnoDB存储引擎中, Cardinality统计信息的更新发生在两个操作中: INSERT和 UPDATE。根据前面的叙述,不可能在每次发生 INSERT和 UPDATE时就去更新Cardinality信息,这样会增加数据库系统的负荷,同时对于大表的统计,时间上也不允许数据库这样去操作。因此, InnoDB存储引擎内部对更新 Cardinality信息的策略为:

表中116的数据已发生过变化
stat_modified_counter>2000000000

第一种策略为自从上次统计 Cardinality信息后,表中1/16的数据已经发生过变化,这时需要更新 Cardinality信息。第二种情况考虑的是,如果对表中某一行数据频繁地进行更新操作,这时表中的数据实际并没有增加,实际发生变化的还是这一行数据,则第一种更新策略就无法适用这这种情况。故在 InnoDB存储引擎内部有一个计数器stat_modified_counter,用来表示发生变化的次数,当 stat_modified_counter大于2000000000时,则同样需要更新 Cardinality信息。

覆盖索引

即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的 IO 操作。
对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为（primary key1，priamey key2，…,key1，key2，…）。例如，下面语句都可仅使用一次辅助联合索引来完成查询：

SELECT key2 FROM table WHERE key1=xxx;
SELECT primary key2,key2 FROM table key1=xxx;
SELECT primary key1,key2 FROM table key1=xxx;
SELECT primary key1,primary key2,key2 FROM table key1=xxx;

有时进行统计count()操作时，因为覆盖索引树数据量比较小，可以减少IO操作，因此InnoDB会选择覆盖索引。

哈希索引

InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。
InnoDB存储引擎使用哈希算法来对字典进行查找，其冲突机制采用链表方式，哈希函数采用除法散列方式。对于缓冲池页的哈希表来说，在缓冲池中的Page页都有一个chain指针。它指向相同哈希函数值的页。而对于除法散列，m的取值略大于2倍的缓冲池页数量的质数。例如：当前参数innodb_buffer_pool_size的大小为10M,则共有640个16kb的页。对于缓冲池页内存的哈希表来说，需要分配640*2=1280个槽,但是由于1280不是质数,需要取比1280略大的一个质数，应该是1399,所以在启动时会分配1399个槽的哈希表，用来哈希查询所在缓冲池中的页
那么在InnoDB存储引擎的缓冲池对于其中的页是怎么进行查找的呢？上面只是给出了一般的算法，怎么将查找的页转换成自然数呢?
其实很简单,InnoDB存储引擎的表空间都有一个space_id，用户所要查找的应该是某个表空间某个连续16KB的页，即偏移量offset，InnoDB存储引擎将space_id左移20位，然后加上这个space_id和offset，即关键字K=space_id<<20+space_id+offset,然后通过除法散列到各个槽中。

自适应哈希索引

innodb存储引擎有一个特殊的功能叫自适应哈希索引(adaptive hash index),当innodb注意到某些索引值被使用的非常频繁时，它会在内存中基于B+树索引上再创建一个哈希索引。这就让B+树索引也具有一些哈希索引的优点，比如快速的哈希查找。这是一个完全自动，内部的行为，用户无法控制或配置。

全文索引

在InnoDB中，全文索引使用full inverted index实现。

full inverted index，其表现形式为{单词，（单词所在文档的ID，在具体文档中的位置）}，如下例子。