MySQL InnoDB索引原理和算法

小瑶姑娘_4303

小瑶姑娘_4303

2019-11-27

3095人浏览

转载

也许你经常用mysql,也会经常用索引,但是对索引的原理和高级功能却并不知道,我们在这里一起学习下。

InnoDB存储索引

在数据库中,如果索引太多,应用程序的性能可能会受到影响;如果索引太少,又会对查询性能产生影响。所以,我们要追求两者的一个平衡点,足够多的索引带来查询性能提高,又不因为索引过多导致修改数据等操作时负载过高。

InnoDB支持3种常见索引:

 ● 哈希索引

 ● B+ 树索引

 ● 全文索引

我们接下来要详细讲解的就是B+ 树索引和全文索引。

哈希索引

学习哈希索引之前,我们先了解一些基础的知识:哈希算法。哈希算法是一种常用的算法,时间复杂度为O(1)。它不仅应用在索引上,各个数据库应用中也都会使用。

哈希表

哈希表(Hash Table)也称散列表,由直接寻址表改进而来。

1.jpg
在该表中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,然后使用除法散列到各个槽中。

自适应哈希索引

自适应哈希索引采用上面的哈希表实现,属于数据库内部机制,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步:

2.jpg

详细的算法可以参考二分查找算法。

二叉查找树

二叉查找树的定义是在一个二叉树中,左子树的值总是小于根键值,根键值总是小于右子树的值。在我们查找时,每次都从根开始查找,根据比较的结果来判断继续查找左子树还是右子树。其查找的方法非常类似于二分查找法。

3.jpg

平衡二叉树

二叉查找树的定义非常宽泛,可以任意构造,但是在极端情况下查询的效率和顺序查找一样,如只有左子树的二叉查找树。

4.jpg

若想构造一个性能最大的二叉查找树,就需要该树是平衡的,即平衡二叉树(由于其发明者为G. M. Adelson-Velsky 和 Evgenii Landis,又被称为AVL树)。其定义为必须满足任何节点的两个子树的高度最大差为1的二叉查找树。平衡二叉树相对结构较优,而最好的性能需要建立一个最优二叉树,但由于维护该树代价高,因此一般平衡二叉树即可。

平衡二叉树查询速度很快,但在树发生变更时,需要通过一次或多次左旋和右旋来达到树新的平衡。这里不发散讲。

B+ 树

了解了基础的数据结构后,我们来看下B+ 树的实现,其定义十分复杂,简单来说就是在B树上增加规定:

1、叶子结点存数据,非叶子结点存指针

2、所有叶子结点从左到右用双向链表记录

目标是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在该树中,所有的记录都按键值的大小放在同一层的叶子节点上,各叶子节点之间有指针进行连接(非连续存储),形成一个双向链表。索引节点按照平衡树的方式构造,并存在指针指向具体的叶子节点,进行快速查找。

下面的B+ 树为数据较少时,此时高度为2,每页固定存放4条记录,扇出固定为5(图上灰色部分)。叶子节点存放多条数据,是为了降低树的高度,进行快速查找。

5.jpg

当我们插入28、70、95 3条数据后,B+ 树由于数据满了,需要进行页的拆分。此时高度变为3,每页依然是4条记录,双向链表未画出但是依然是存在的,现在可以看出来是一个平衡二叉树的雏形了。

6.jpg

win可用的mysql指令skill
win可用的mysql指令skill

安装、修复、更新或打包一个基于 Python 和 PyMySQL 实现的 Windows `mysql` 命令。适用于用户希望在 PowerShell/CMD 中输入 `mysql` 时重定向到 Python 实现、需要交互式输入 MySQL 连接信息、需要同步到当前用户本地 bin 目录,或需要将该能力封装成可公开复用的 Codex skill。

下载

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<p><strong>辅助索引</strong></p><p>辅助索引又称非聚集索引,其叶子节点不包含行记录的全部数据,而是包含一个书签<code>(bookmark)</code>,该书签指向对应行数据的聚集索引,告诉<code>InnoDB</code>存储引擎去哪里查找具体的行数据。辅助索引与聚集索引的关系就是结构相似、独立存在,但辅助索引查找非索引数据需要依赖于聚集索引来查找。<br></p><p><img src="https://img.php.cn/upload/image/639/959/687/1574846895545347.jpg?x-oss-process=image/resize,p_40" title="1574846895545347.jpg" alt="7.jpg"></p><p><span  style="max-width:90%"><strong>全文索引</strong></span></p><p>我们通过<code>B+</code> 树索引可以进行前缀查找,如:</p><pre class="brush:php;toolbar:false;">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, 文档中的位置)}

对于这样的一个数据表:

8.jpg

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

9.jpg

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

10.jpg

全文检索索引缓存

辅助表是存在与磁盘上的持久化的表,由于磁盘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 |  124124 | 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教程

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

mysql

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

60

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

60

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

60

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

40

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

140

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

160

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程