MySQL InnoDB索引道理和算法
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索引道理和算法的具体内容，更多请关注百分百源码网其它相关文章！
