也许你经常用 MySQL, 也会经常用索引, 但是对索引的原理和高级功能却并不知道, 我们在这里一起学习下.
InnoDB 存储索引
在数据库中, 如果索引太多, 应用程序的性能可能会受到影响; 如果索引太少, 又会对查询性能产生影响. 所以, 我们要追求两者的一个平衡点, 足够多的索引带来查询性能提高, 又不因为索引过多导致修改数据等操作时负载过高.
InnoDB 支持 3 种常见索引:
哈希索引
B+ 树索引
全文索引
我们接下来要详细讲解的就是 B+ 树索引和全文索引.
哈希索引
InnoDB 存储引擎支持的哈希索引是自适应的, 会根据表的使用情况自动为表生成哈希索引, 不能人为干预是否在一张表中生成哈希索引. 这块内容我们先不展开说, 后续补充.
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+ 树为数据较少时, 此时高度为 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);
参考资料
二分查找算法: https://juejin.im/post/5c90ed...
MySQL 乱码的原因和设置 UTF8 数据格式: https://segmentfault.com/a/11...
《MySQL 技术内幕 InnoDB 存储引擎 第 2 版》第 5 章: 索引与算法
来源: https://www.2cto.com/kf/201905/808167.html