MySQL 的索引基础知识

用户头像
guoguo 👻
关注
发布于: 6 小时前

索引的类型

索引的使用,可以帮助我们大大的加快数据的检索速度。

MySQL中,主要有以下几种类型索引:FULLTEXT、HASH、BTREE、RTREE。

FULLTEXT

InnoDB引擎,MySQL在5.6版本以上,支持在CHAR、VARCHAR、TEXT类型的列上定义全文索引。但因为无法对中文分词,所以对中文支持很差。从5.7版本,内置了ngram全文检索插件,才支持中文分词。



使用语法 MATCH(col1,col2,…) AGAINST (expr[search_modifier])。其中MATCH中的内容为已建立FULLTEXT索引并要从中查找数据的列,AGAINST中的expr为要查找的文本内容,search_modifier为可选搜索类型。



-- 创建表
mysql> create table t_fulltext_demo(msg varchar(512));
Query OK, 0 rows affected (0.31 sec)
-- 创建全文索引,使用ngram可支持中文分词
mysql> ALTER table t_fulltext_demo add fulltext index idx_fulltext_demo ( msg asc ) with parser ngram;
Query OK, 0 rows affected (1.50 sec)
Records: 0 Duplicates: 0 Warnings: 1
-- 插入中文数据
mysql> insert into t_fulltext_demo values ('今天天气真好,好像出去玩!');
Query OK, 1 row affected (0.04 sec)
-- 匹配单个文字
mysql> select * from t_fulltext_demo where match(msg) against('天' in boolean mode);
Empty set
-- 匹配词语
mysql> select * from t_fulltext_demo where match(msg) against('天气' in boolean mode);
+----------------------------+
| msg |
+----------------------------+
| 今天天气真好,好像出去玩! |
+----------------------------+
1 row in set (0.02 sec)
-- 插入英文数据
mysql> insert into t_fulltext_demo values ('it is a fine day, i want play outside.');
Query OK, 1 row affected (0.04 sec)
-- 匹配英文单词
mysql> select * from t_fulltext_demo where match(msg) against('want' in natural language mode);
+----------------------------------------+
| msg |
+----------------------------------------+
| it is a fine day, i want play outside. |
+----------------------------------------+
1 row in set (0.03 sec)
-- 匹配英文单词
mysql> select * from t_fulltext_demo where match(msg) against('outside' in natural language mode);
+----------------------------------------+
| msg |
+----------------------------------------+
| it is a fine day, i want play outside. |
+----------------------------------------+
1 row in set (0.04 sec)
-- 匹配英文单词(2个字符),根据 “it” 查询不到数据
mysql> select * from t_fulltext_demo where match(msg) against('it' in natural language mode);
Empty set
-- 查询参数
-- ft_min_word_len 最小是4 所以查询不到
mysql> show variables like 'ft%';
+--------------------------+----------------+
| Variable_name | Value |
+--------------------------+----------------+
| ft_boolean_syntax | + -><()~*:""&| |
| ft_max_word_len | 84 |
| ft_min_word_len | 4 |
| ft_query_expansion_limit | 20 |
| ft_stopword_file | (built-in) |
+--------------------------+----------------+
-- 去修改my.cnf,并设置 ft_min_work_len=2后重启
mysql> show variables like 'ft%';
+--------------------------+----------------+
| Variable_name | Value |
+--------------------------+----------------+
| ft_boolean_syntax | + -><()~*:""&| |
| ft_max_word_len | 84 |
| ft_min_word_len | 2 |
| ft_query_expansion_limit | 20 |
| ft_stopword_file | (built-in) |
+--------------------------+----------------+
5 rows in set (0.05 sec)
-- 仍然查询不到,可能是因为 ft_stopword_file 使用了内置的 stopword配置
mysql> select * from t_fulltext_demo where match(msg) against('it' in natural language mode);
Empty set
-- 果然包含了单词 it
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.05 sec)
-- 最后一条记录 没有任何一个单词是out 或 包含 out
mysql> select match(msg) against('out') as score, msg from t_fulltext_demo;
+----------------------------+-------------------------------------------------------------------------------------------------------------------------------------+
| score | msg |
+----------------------------+-------------------------------------------------------------------------------------------------------------------------------------+
| 0 | 今天天气真好,好像出去玩! |
| 0.000000003771856604828372 | it is a fine day, i want play outside. |
| 0.000000003771856604828372 | MySQL, the most popular Open Source SQL database management system, is developed, distributed, and supported by Oracle Corporation. |
+----------------------------+-------------------------------------------------------------------------------------------------------------------------------------+
3 rows in set (0.04 sec)



FULLTEXT索引能够帮助我们解决like '%text%'性能低下的问题。使用时需注意版本,如果需要对中文支持,要使用5.7.6之后的版本。



负面影响:

  1. 占用存储空间更大。

  2. 增删改的代价更大。(数据插入完后创建全文索引比先创建全文索引在插入数据更快)

  3. 不适合大数据量表的应用,由于全文索引占用空间更大,而MySQL加载一页(一般16K)数据包含的索引也就更少,需多次加载。



基于以上,除非用于小数据量的简单实现,否则全文检索的功能往往被ES代替。

HASH

等值检索时,性能非常高,时间复杂度O(1)。

利用哈希函数计算出检索数据的槽位。当发生哈希碰撞,使用链表将数据连接起来。

由于检索的数据通过哈希算法一次定位,所以其查询的效率非常高。

但缺点也很明显:

  1. Hash 索引仅仅能满足等值运算,如"=","IN"和"<=>"查询,不能使用范围查询。

  2. 无法使用Hash索引来加速排序操作。

  3. Hash 索引不能利用部分索引键查询。Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。

  4. 对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。

场景:比如存储一个URL字段的表,对URL进行CRC32运算后,创建哈希索引。(我们使用Snowshake生成的ID主键是否使用哈希索引更好?不过,在Innodb引擎中,是不支持用户显式的使用哈希索引,Innodb存储引擎会自动根据表的情况创建哈希索引)

B+树

为什么用B+树?我们先来看看其他几种常用的查找树。

二叉查找树



假设查找id=12的数据

  1. 根节点10,需要查找的数12大于当前节点,找到当前节点的右子节点。

  2. 当前节点13,需要查找的数12小于当前节点,找到当前节点的左子节点。

  3. 当前节点12,命中,返回(12,becky)。

平衡二叉树

有一种极端情况,当二叉树变成了一个链表。

此时要去查找id=17的数据,则需要遍历所有节点,也就是全表扫描了。

导致这个问题的原因,在于树变得不平衡了,也就是高度太高,为了解决这个问题,可以引入平衡二叉树。(JDK1.8以上的HashMap实现的红黑树就是一种平衡二叉树,解决链表查找性能低的问题)。

平衡二叉树可通过左旋、右旋来调节树的平衡。







于是,之前的那棵树就变成了

此时再查找id=17的节点,则需要查找3次。

看上去似乎解决了问题。但是依然存在问题:

  1. 但是当数据达到了百万级、千万级树的高度是非常可观的。查找的效率并没有质的提升。

  2. 查询不稳定,如果查找的数据正好是根节点则只需要一次查找,如果是叶子节点则需要树的高度次查找。

  3. IO次数太多。MySQL读取数据以页为单位,如果按照平衡查找二叉树来查找,每次只能读取一个节点的数据,会造成IO次数的较多。我们希望通过较少的IO次数完成数据的查找。

多路平衡查找树(B-Tree)

数据库中一个IO操作的基本单位就是页(Page),MySQL在InnoDB引擎默认的页大小是16K(通过 show variables like 'innodb_page_size 命令可查询到)。

而B-Tree则能很好的利用操作系统和磁盘的交互特性,MySQL为更好利用磁盘的预读能力,将页大小默认设置为16K,即将一个节点(磁盘块)的大小设置为16K,一次IO将一个节点(16K)内容加载进内存。



基于以上结构,MySQL从磁盘加载一页数据16K,那么这16K作为一个节点,就可以包含很多路(图中节点10就是1路,节点(5,6)就是2路)。假设一个关键字是int类型4字节,假设数据占用12字节,不考虑子节点应用情况下,16K的页就可存储1000个节点。那么3层高度的树,能够存放的数据将远远大于前面的平衡二叉树。

看上去似乎很完美,二级节点假设1000个,每个二级节点下再有1000个,那么3级树将可存储100万的数据。

B+树



与B-Tree的不同点:

  1. 非叶子节点不存储数据,只存储键值。

其好处是,一次IO读取一页是固定的16K,由于不存储数据,只存储键值,那么一页就可以存储更多的键值,一个节点的路数(阶数)就更多,最终形成的树就更矮,检索时进行IO操作更少,效率更高。

如果一个节点存储1000个键值,3层树,最多就可以存储 1000*1000*1000 = 10亿数据。

  1. 所有的数据均存储在叶子节点。

所有数据都在叶子节点,在同级,所以查询的效率是稳定的。

  1. 叶子节点内数据是有序的,并且每个节点都指向相邻的节点。

节点的有序性非常便于我们进行排序或区间查询。

聚簇索引与非聚簇索引

聚簇索引与非聚簇索引并不是索引的类型,而是数据的存储方式。

聚簇索引

一张表只有一个聚簇索引。根据表的主键(InnoDB中即便没有创建主键,MySQL也会隐式的创建一个主键来作为聚簇索引的键)作为B+树中的键,而表中的具体数据作为叶子节点存储的内容,所以叶子节点在聚簇索引中也称为数据页。

非聚簇索引

非聚簇索引也称为辅助索引(Secondary Index)。与聚簇索引不同在于,叶子节点存储的并非表的行数据,而是存储的主键,在查询时,通过非聚簇索引查找到主键后,还要去聚簇索引根据主键查询具体的完整数据。





优缺点

聚簇索引

优点:

  1. 数据访问更快,因为索引和完整的数据都保存在B+树上,因此从聚簇索引查询比非聚簇索引效率更高。

  2. 对于基于键的排序和范围查找非常快。

缺点:

  1. 如果插入的数据不是按照主键的顺序插入,会造成数据的移动,造成额外的磁盘IO。所以一般建议插入数据按照主键顺序插入最好。

  2. 

MyISAM与InnoDB

在InnoDB引擎中,数据的存储通过表主键,使用的聚簇索引。

与InnoDB引擎不同的是,在MyISAM中,叶子节点存放的是数据的地址。在MyISAM引擎中,MYI文件存放的就是索引数据,MYD文件存放的就是实际数据。索引和数据文件是单独文件分别存储的。



用户头像

guoguo 👻

关注

还未添加个人签名 2017.11.30 加入

还未添加个人简介

评论

发布
暂无评论
MySQL的索引基础知识