MySQL，也会经经常运用索引，然则对索引的道理和高等功用却并不知道，我们在这里一同进修下。
InnoDB存储索引
在数据库中，假如索引太多，运用程序的机能可能会受到影响；假如索引太少，又会对查询机能产生影响。所以，我们要寻求二者的一个均衡点，足够多的索引带来查询机能进步，又不因为索引过量致使修正数据等操纵时负载太高。
InnoDB支撑3种罕见索引：
● 哈希索引
● B+ 树索引
● 全文索引
我们接下来要细致解说的就是B+ 树索引和全文索引。
哈希索引
进修哈希索引之前，我们先相识一些基本的学问：哈希算法。哈希算法是一种经常运用的算法，时候复杂度为O(1)。它不仅运用在索引上，各个数据库运用中也都邑运用。
哈希表
哈希表（Hash Table）也称散列表，由直接寻址表革新而来。
在该表中U示意关键字全集，K示意现实存在的关键字，右侧的数组（哈希表）示意在内存中可以直接寻址的一连空间，哈希表中每一个插槽关联的单向链表中存储现实数据的实在地点。
假如右侧的数组直接运用直接寻址表，那末关于每一个关键字K都邑存在一个h[K]且不反复，如许存在一些问题，假如U数据量过大，那末关于计算机的可用容量来讲有点不现实。而假如鸠合K占比U的比例太小，则分派的大部份空间都要糟蹋。
因而我们运用哈希表，我们经由过程一些函数h(k)来肯定映照关联，如许让离散的数据尽量均匀分布的应用数组中的插槽，但会有一个问题，多个关键字映照到统一个插槽中，这类状况称为碰撞（collision），数据库中采纳最简朴的解决方案：链接法（chaining）。也就是每一个插槽存储一个单项链表，一切碰撞的元素会顺次构成链表中的一个结点，假如不存在，则链表指向为NULL。
而运用的函数h(k)成为哈希函数，它必需可以很好的举行散列。最好可以防止碰撞或许到达最小碰撞。平常为了更好的处置惩罚哈希的关键字，我们会将其转换为自然数，然后经由过程除法散列、乘法散列或许全域散列来完成。数据库平常运用除法散列，即当有m个插槽时，我们对每一个关键字k举行对m的取模：h(k) = k % m。
InnoDB存储引擎中的哈希算法
InnoDB存储引擎运用哈希算法来查找字典，争执机制采纳链表，哈希函数采纳除法散列。关于缓冲池的哈希表，在缓存池中的每页都有一个chain指针，指向雷同哈希值的页。关于除法散列，m的值为略大于2倍缓冲池页数目的质数。如当前innodb_buffer_pool_size大小为10M，则共有640个16KB的页，须要分派1280个插槽，而略大于的质数为1399，因而会分派1399个槽的哈希表，用来哈希查询缓冲池中的页。
而关于将每一个页转换为自然数，每一个表空间都有一个space_id，用户要查询的是空间中某个一连的16KB的页，即偏移量（offset），InnoDB将space_id左移20位，再加上space_id和offset，即K=space_id<<20+space_id+offset，然后运用除法散列到各个槽中。
自适应哈希索引
自适应哈希索引采纳上面的哈希表完成，属于数据库内部机制，DBA不能干涉干与。它只对字典范例的查找异常疾速，而对局限查找等却无计可施，如：
select * from t where f='100'；
我们可以检察自适应哈希索引的运用状况：
mysql> show engine innodb status\G; *************************** 1. row *************************** Type: InnoDB Name: Status: ===================================== 2019-05-13 23:32:21 7f4875947700 INNODB MONITOR OUTPUT ===================================== Per second averages calculated from the last 32 seconds ... ------------------------------------- INSERT BUFFER AND ADAPTIVE HASH INDEX ------------------------------------- Ibuf: size 1, free list len 1226, seg size 1228, 0 merges merged operations: insert 0, delete mark 0, delete 0 discarded operations: insert 0, delete mark 0, delete 0 Hash table size 276671, node heap has 1288 buffer(s) 0.16 hash searches/s, 16.97 non-hash searches/s
我们可以看到自适应哈希的运用状况，可以经由过程末了一行的hash searches/non-hash searches来推断运用哈希索引的效力。
我们可以运用innodb_adaptive_hash_index参数来禁用或启用此特征，默许开启。
B+ 树索引
B+ 树索引是如今关联型数据库系统中查找最为经常运用和有用的索引，其组织相似于二叉树，依据键值对疾速找到数据。B+ 树（balance+ tree）由B树（banlance tree 均衡二叉树）和索引递次接见要领（ISAM: Index Sequence Access Method）演变而来，这几个都是典范的数据构造。而MyISAM引擎最初也是参考ISAM数据构造设计的。
基本数据构造
想要相识B+ 树数据构造，我们先相识一些基本的学问。
二分查找法
又称为折半查找法，指的是将数据递次排列，经由过程每次和中心值比较，跳跃式查找，每次缩减一半的局限，疾速找到目的的算法。其算法复杂度为log2(n)，比递次查找要快上一些。
如图所示，从有序列表中查找48，只须要3步：
细致的算法可以参考二分查找算法。
二叉查找树
二叉查找树的定义是在一个二叉树中，左子树的值老是小于根键值，根键值老是小于右子树的值。在我们查找时，每次都从根开始查找，依据比较的效果来推断继承查找左子树照样右子树。其查找的要领异常相似于二分查找法。
均衡二叉树
二叉查找树的定义异常广泛，可以恣意组织，然则在极度状况下查询的效力和递次查找一样，如只要左子树的二叉查找树。
若想组织一个机能最大的二叉查找树，就须要该树是均衡的，即均衡二叉树（因为其发明者为G. M. Adelson-Velsky 和 Evgenii Landis，又被称为AVL树）。其定义为必需满足任何节点的两个子树的高度最大差为1的二叉查找树。均衡二叉树相对构造较优，而最好的机能须要竖立一个最优二叉树，但因为保护该树代价高，因而平常均衡二叉树即可。
均衡二叉树查询速率很快，但在树发作变动时，须要经由过程一次或屡次左旋和右旋来到达树新的均衡。这里不发散讲。
B+ 树
相识了基本的数据构造后，我们来看下B+ 树的完成，其定义十分复杂，简朴来讲就是在B树上增添划定：
1、叶子结点存数据，非叶子结点存指针
2、一切叶子结点从左到右用双向链表纪录
目的是为磁盘或其他直接存取辅佐设备设计的一种均衡查找树。在该树中，一切的纪录都按键值的大小放在统一层的叶子节点上，各叶子节点之间有指针举行衔接（非一连存储），构成一个双向链表。索引节点根据均衡树的体式格局组织，并存在指针指向详细的叶子节点，举行疾速查找。
下面的B+ 树为数据较少时，此时高度为2，每页牢固寄存4条纪录，扇出牢固为5（图上灰色部份）。叶子节点寄存多条数据，是为了下降树的高度，举行疾速查找。
当我们插进去28、70、95 3条数据后，B+ 树因为数据满了，须要举行页的拆分。此时高度变成3，每页依然是4条纪录，双向链表未画出然则依然是存在的，如今可以看出来是一个均衡二叉树的雏形了。
InnoDB的B+ 树索引
InnoDB的B+ 树索引的特点是高扇出性，因而平常树的高度为2~4层，如许我们在查找一条纪录时只用I/O 2~4次。当前机器硬盘每秒最少100次I/O/s，因而查询时候只需0.02~0.04s。
数据库中的B+ 树索引分为群集索引（clustered index）和辅佐索引（secondary index）。它们的区别是叶子节点寄存的是不是为一整行的完全数据。
群集索引
群集索引就是根据每张表的主键（唯一）组织一棵B+ 树，同时叶子节点寄存整行的完全数据，因而将叶子节点称为数据页。因为定义了数据的逻辑递次，群集索引也能疾速的举行局限范例的查询。
群集索引的叶子节点根据逻辑递次一连存储，叶子节点内部物理上一连存储，作为最小单位，叶子节点间经由过程双向指针衔接，物理存储上不一连，逻辑存储上一连。
群集索引可以针对主键举行疾速的排序查找和局限查找，因为是双向链表，因而在逆序查找时也异常快。
我们可以经由过程explain敕令来剖析MySQL数据库的执行计划：
# 检察表的定义，可以看到id为主键，name为一般列
mysql> show create table dimensionsConf;
| Table | Create Table
| dimensionsConf | CREATE TABLE `dimensionsConf` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(20) DEFAULT NULL,
`remark` varchar(1024) NOT NULL,
PRIMARY KEY (`id`),
FULLTEXT KEY `fullindex_remark` (`remark`)
) ENGINE=InnoDB AUTO_INCREMENT=178 DEFAULT CHARSET=utf8 |
1 row in set (0.00 sec)
# 先测试一个非主键的name属性排序并查找，可以看到没有运用到任何索引，且须要filesort（文件排序），这里的rows为输出行数的预估值
mysql> explain select * from dimensionsConf order by name limit 10\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: dimensionsConf
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 57
Extra: Using filesort
1 row in set (0.00 sec)
# 再测试主键id的排序并查找，此时运用主键索引，在执行计划中没有了filesort操纵，这就是群集索引带来的优化
mysql> explain select * from dimensionsConf order by id limit 10\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: dimensionsConf
type: index
possible_keys: NULL
key: PRIMARY
key_len: 4
ref: NULL
rows: 10
Extra: NULL
1 row in set (0.00 sec)
# 再查找依据主键id的局限查找，此时直接依据叶子节点的上层节点便可以疾速获得局限，然后读取数据
mysql> explain select * from dimensionsConf where id>10 and id<10000\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: dimensionsConf
type: range
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 56
Extra: Using where
1 row in set (0.00 sec)
辅佐索引
辅佐索引又称非群集索引，其叶子节点不包括行纪录的悉数数据，而是包括一个书签（bookmark），该书签指向对应行数据的群集索引，通知InnoDB存储引擎去那里查找详细的行数据。辅佐索引与群集索引的关联就是构造相似、自力存在，但辅佐索引查找非索引数据须要依赖于群集索引来查找。
全文索引
我们经由过程B+ 树索引可以举行前缀查找，如：
select * from blog where content like 'xxx%';
只要为content列添加了B+ 树索引（群集索引或辅佐索引），便可疾速查询。但在更多状况下，我们在博客或搜刮引擎中须要查询的是某个单词，而不是某个单词开头，如：
select * from blog where content like '%xxx%';
此时假如运用B+ 树索引依然是全表扫描，而全文检索（Full-Text Search）就是将整本书或文章内恣意内容检索出来的手艺。
倒排索引
全文索引一般运用倒排索引（inverted index）来完成，倒排索引和B+ 树索引都是一种索引构造，它须要将分词（word）存储在一个辅佐表（Auxiliary Table）中，为了进步全文检索的并行机能，共有6张辅佐表。辅佐表中存储了单词和单词在各行纪录中位置的映照关联。它分为两种：
inverted file index（倒排文件索引），表现为{单词，单词地点文档ID}full inverted index（细致倒排索引），表现为{单词，(单词地点文档ID, 文档中的位置)}
关于如许的一个数据表：
倒排文件索引范例的辅佐表存储为：
细致倒排索引范例的辅佐表存储为，占用更多空间，也更好的定位数据，比供应更多的搜刮特征：
全文检索索引缓存
辅佐表是存在与磁盘上的耐久化的表，因为磁盘I/O比较慢，因而供应FTS Index Cache（全文检索索引缓存）来进步机能。FTS Index Cache是一个红黑树构造，依据（word, list）排序，在有数据插进去时，索引先更新到缓存中，然后InnoDB存储引擎会批量举行更新到辅佐表中。
当数据库宕机时，还没有落盘的索引缓存数据会自动读取并存储，设置参数innodb_ft_cache_size掌握缓存的大小，默许为32M，进步该值，可以进步全文检索的机能，但在毛病时，须要更久的时候恢复。
在删除数据时，InnoDB不会删除索引数据，而是保存在DELETED辅佐表中，因而一段时候后，索引会变得异常大，可以经由过程optimize table敕令手动删除无效索引纪录。假如须要删除的内容异常多，会影响运用程序的可用性，参数innodb_ft_num_word_optimize掌握每次删除的分词数目，默许为2000，用户可以调解该参数来掌握删除幅度。
全文检索限定
全文检索存在一个黑名单列表（stopword list），该列表中的词不须要举行索引分词，默许共有36个，如the单词。你可以自行调解：
mysql> select * from information_schema.INNODB_FT_DEFAULT_STOPWORD; +-------+ | value | +-------+ | a | | about | | an | | are | | as | | at | | be | | by | | com | | de | | en | | for | | from | | how | | i | | in | | is | | it | | la | | of | | on | | or | | that | | the | | this | | to | | was | | what | | when | | where | | who | | will | | with | | und | | the | | www | +-------+ 36 rows in set (0.00 sec)
其他限定另有：
● 每张表只能有一个全文检索索引
● 多列组合的全文检索索引必需运用雷同的字符集和字符序，不相识的可以参考MySQL乱码的缘由和设置UTF8数据格式
● 不支撑没有单词界定符（delimiter）的言语，如中文、日语、韩语等
全文检索
我们建立一个全文索引：
mysql> create fulltext index fullindex_remark on dimensionsConf(remark); Query OK, 0 rows affected, 1 warning (0.39 sec) Records: 0 Duplicates: 0 Warnings: 1 mysql> show warnings; +---------+------+--------------------------------------------------+ | Level | Code | Message | +---------+------+--------------------------------------------------+ | Warning | 124 | InnoDB rebuilding table to add column FTS_DOC_ID | +---------+------+--------------------------------------------------+ 1 row in set (0.00 sec)
全文检索有两种要领：
● 自然言语（Natural Language），默许要领，可省略：（IN NATURAL LANGUAE MODE）
● 布尔形式（Boolean Mode）：（IN BOOLEAN MODE）
自然言语还支撑一种扩大形式，背面加上：（WITH QUERY EXPANSION）。
其语法为MATCH()...AGAINST()，MATCH指定被查询的列，AGAINST指定何种要领查询。
自然言语检索
mysql> select remark from dimensionsConf where remark like '%baby%';
+-------------------+
| remark |
+-------------------+
| a baby like panda |
| a baby like panda |
+-------------------+
2 rows in set (0.00 sec)
mysql> select remark from dimensionsConf where match(remark) against('baby' IN NATURAL LANGUAGE MODE);
+-------------------+
| remark |
+-------------------+
| a baby like panda |
| a baby like panda |
+-------------------+
2 rows in set (0.00 sec)
# 检察下执行计划，运用了全文索引排序
mysql> explain select * from dimensionsConf where match(remark) against('baby');
+----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+
| 1 | SIMPLE | dimensionsConf | fulltext | fullindex_remark | fullindex_remark | 0 | NULL | 1 | Using where |
+----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+
1 row in set (0.00 sec)
我们也可以检察各行数据的相干性，是一个非负的浮点数，0代表没有相干性：
mysql> select id,remark,match(remark) against('baby') as relevance from dimensionsConf;
+-----+-----------------------+--------------------+
| id | remark | relevance |
+-----+-----------------------+--------------------+
| 106 | c | 0 |
| 111 | 运营商 | 0 |
| 115 | a baby like panda | 2.1165735721588135 |
| 116 | a baby like panda | 2.1165735721588135 |
+-----+-----------------------+--------------------+
4 rows in set (0.01 sec)
布尔形式检索
MySQL也许可用修饰符来举行全文检索，个中特别字符会有特别寄义：
+:该word必需存在-:该word必需消除（no operator）:该word可选，假如涌现，相干性更高@distance:查询的多个单词必需在指定局限以内>:涌现该单词时增添相干性<:涌现该单词时下降相干性~:涌现该单词时相干性为负*:以该单词开头的单词":示意短语
# 代表必需有a baby短语，不能有man，可以有lik开头的单词，可以有panda，
select remark from dimensionsConf where match(remark) against('+"a baby" -man lik* panda' IN BOOLEAN MODE);
扩大查询
当查询的关键字太短或不够清楚时，须要用隐含学问来举行检索，如database关联的MySQL/DB2等。但这个我并没太邃晓怎样运用，后续补充吧。
相似的运用是：
select * from articles where match(title,body) against('database' with query expansion);
引荐进修：MySQL教程
以上就是MySQL InnoDB索引道理和算法的细致内容，更多请关注ki4网别的相干文章！
