MySQL InnoDB索引原理和算法

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，则共有0个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张辅助表。辅助表中存储了单词和单词在各行记录中位置的映射关系。它分为两种：

对于这样的一个数据表：

倒排文件索引类型的辅助表存储为：

详细倒排索引类型的辅助表存储为，占用更多空间，也更好的定位数据，比提供更多的搜索特性：

全文检索索引缓存

辅助表是存在与磁盘上的持久化的表，由于磁盘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也允许用修饰符来进行全文检索，其中特殊字符会有特殊含义：

# 代表必须有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教程

瑞缇养生网还为您提供以下相关内容希望对您有帮助：

InnoDB：表数据按主键构建的B+树存储，叶子节点直接包含完整数据行。若未显式定义主键，InnoDB会选择唯一非空列或生成隐藏的6字节ROWID作为索引。MyISAM：不支持聚簇索引，索引文件（.MYI）与数据文件（.MYD）分离，查询需先定位索引再读取数据，效率低于InnoDB。二级索引（Secondary Index

其原理是对文本进行分词处理，生成单词列表（倒排索引），并为每个单词记录包含该词的数据行位置。例如，查询“数据库”时，系统会快速定位到所有包含该词的行。全文索引的构建成本高，需消耗大量时间和存储空间，且仅适用于大文本场景，常规数值或短字符串查询无需使用。总结MySQL索引的底层设计均围绕“减...

读取数据顺序：.myi -> .myd。索引分为主键索引和非主键索引。（一）主键索引：叶子节点key存储索引值，value存储data数据指针。（二）辅助索引：结构与主键索引基本一致。（三）InnoDB聚簇索引：数据和索引在同一份文件中。主键索引和非主键索引有区别。（四）主键索引：叶子节点key存储索引信息，value存...

三、MySQL InnoDB的索引实现1. 索引组织表（IOT）InnoDB中，表数据按主键顺序存储在聚簇索引（B+树）的叶子节点中，表即索引。若未定义主键，InnoDB会隐式生成一个6字节的ROWID作为聚簇索引。2. B+树索引结构非叶子节点：存储键值和子节点指针，用于快速定位。叶子节点：存储数据记录（聚簇索引）或主...

三、存储引擎优化原理InnoDB核心特性 事务支持：ACID兼容，通过redo log（持久性）和undo log（原子性）实现。行级锁：减少锁冲突，但需注意间隙锁（Gap Lock）导致的死锁风险。MVCC机制：通过ReadView实现读写不阻塞，提升并发性能。缓冲池（Buffer Pool）：缓存数据页和索引页，大小建议设为物理内存的50...

4.1 innodb的索引机制 先以innodb存储引擎为例，说明innodb引擎是如何利用B+树建立索引的 首先创建一张表：zodiac，并插入一些数据 对于innodb来说，只有一个数据文件，这个数据文件本身就是用B+树形式组织，B+树每个节点的关键字就是表的主键，因此innode的数据文件本身就是主索引文件，如下图所示，主...

B+树原理揭秘： 数据结构：B+树是一种平衡树数据结构，所有叶子节点都在同一层，且叶子节点之间通过指针相连，形成一个有序链表。这种结构使得B+树在进行范围查询时非常高效。 InnoDB索引结构：在MySQL的InnoDB存储引擎中，B+树被用作索引结构。叶子节点按主键排序，每个叶子节点存储了一条记录的主键和...

一、索引的核心原理数据结构基础：索引本质是按特定列排序的数据库表副本，通过逻辑分块存储数据指针（如B+树结构）。查询加速机制：执行查询时，MySQL优先扫描索引结构定位数据块指针，避免全表扫描（如无索引时需逐行检查）。二、索引类型与适用场景B树索引（默认类型）适用场景：等值查询（=）、范围查询...

根据数据中物理顺序与键值的逻辑（索引）顺序关系：聚集索引：并不是一种单独的索引类型，而是一种数据存储方式。InnoDB的聚簇索引是在同一个结构中保存了B+Tree索引和数据行。非聚集索引：不是聚簇索引的索引。二、索引的底层实现MySQL默认存储引擎InnoDB只显式支持B-Tree（从技术上来说是B+Tree）索引...

双写机制（doublewrite）确保数据完整，即使部分写操作失败也能恢复。恢复与性能优化重做日志恢复时，InnoDB确保页数据的完整性和一致性。通过内存的双写缓冲区与磁盘上的共享表空间，实现了高效的数据恢复流程。此外，InnoDB还会自动创建哈希索引以加速查询速度。系统配置与文件管理MySQL的配置参数丰富多样，如...