数据库——MySQL的索引
索引
通过MySQL简介 我们了解到InnoDB各个数据页可以组成一个双向链表,而每个数据⻚中的记录会按照主键值从⼩到⼤的顺序组成⼀个单向链表,每个数据⻚都会为存储在它⾥面的记录⽣成⼀个⻚⽬录,在通过主键查找某条记录的时候可以在⻚⽬录中使⽤⼆分法快速定位到对应的槽,然后再遍历该槽 对应分组中的记录即可快速找到指定的记录。
页和记录的关系大致如下图所示,其中页a,页b,页c...页n这些页可以不在物理结构上相邻,只要通过双向链表关联即可。
没有索引的查找
在介绍索引前,我们需要了解没有索引的时候是怎么查找记录的。此处我们以搜索条件为对某个列的精确匹配为例子,所谓精确匹配,就是搜索条件中⽤等于=连接起的表达式。
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
在一个页的查找
假设当前表中的记录较少,所有记录都可以被存放到一个页中,查找目录可分为如下情况:
- 以主键为搜索条件:在页目录中使用二分法快速定位到对应的槽,然后遍历该槽对应分组中的记录。
- 以其他列为搜索条件:由于数据页没有对非主键建立页目录,无法通过二分法定位相应的槽。此时只能从最小记录开始依次遍历单链表中的每条记录,对比是否符合条件。这种查找效率很低。
在很多页中查找
大部分情况下我们存放在表中的记录是非常多的,需要很多数据页来存储这些记录。查找记录主要分为:
- 定位到记录所在的页
- 在所在的业内查找相应记录。
在没有索引的情况下,无论是根据主键列还是其他列进行查找,由于不能快速定位到记录所在页,只能从第一个页沿着双向链表一直往下查找,这种方式极其耗时。因此便有了索引。
B+树索引
就像之前我们为根据主键值快速定位一条记录而设立的页目录,我们也可以为快速定位记录所在数据页而建立一个别的目录。在建立目录时,我们需要两条限制:
- 下一个数据页中记录的主键值必须大于上一个页中记录的主键值。
我们先来看页里面的记录:
假设每个数据页最多存放3条记录(实际不止如此),我们向表中添加3条记录。
INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
当我们想插入第4条数据时,需要分配一个新页
INSERT INTO index_demo VALUES(4, 4, 'a');
需要强调的是,新分配的数据页编号可能不是连续的,即这些页在存储空间里可能并不是挨着的。 页10中记录最大的主键为5,页28的为4,5>4,因此不符合前面提到的限制。因此在插入主键为4的记录时,需要一次记录移动,把主键值5移动到页28,再把主键值4插入页10。这个过程我们可以称为页分裂。
- 所有的页都会建立一个目录项
每个页都对应一个目录项,每个目录项包括:页中记录的最小主键值key;页号page_no
当我们想找主键值20的记录时,查找过程为:
- 从目录项中二分查找确定主键值20的记录在目录项30,对应页为9
- 再根据之前讲的在页中查找记录的方式在页9中定位具体记录。
这个目录的别名就是索引。索引是一种数据结构,它分为B类树索引,哈希索引和全文索引。常见的是B+树索引
从应用的种类来区分,索引还分为普通索引,唯一索引,复合索引:
- 如果可以确定某个数据列的值是不会出现重复的,则可以使用UNIQUE来把他定义为一个唯一索引。
- 若一个索引中包含多个列,则它是复合索引。
- 若一个索引中只包含单个列,则它是普通索引。
主键和索引的区别
- 主键一定是唯一索引,唯一索引不一定就是主键。
- 一个表中可以有多个唯一性索引,但只能有一个主键
- 主键列不允许空值,而唯一性索引列允许空值
- 主键可以被其他字段作外键引用,而索引不能作为外键引用
B-树索引与B+树索引
索引本身很大,不可能全部存储在内存中,往往是以索引文件的形式存储于磁盘中。每次索引查找都会产生磁盘I/O消耗。因此索引的结构要尽量减少I/O存取次数。
B-树
B-树种每个节点是一个磁盘块,把每个节点包含很多关键字,这样树的层级就比普通的二叉树少了,从而减少数据查找的次数。
B+树
B+树是B-树的变种,它的记录只存储在叶子节点种。这样在B-树的基础上每个非叶子节点存储的关键字更多,树的层级更少,查询速度更快。并且相比于B-树,它的各个叶子节点按索引列的值的大小排列构成了一个双向链表,因此更擅长范围查询。
InnoDB的索引方案
目录项其实和用户记录差不多,因此可以用数据页来存储目录项,为了和用户记录区分开,记录头信息的record_type属性的值为1时,表明这一条记录是目录项记录。而普通用户记录的record_type值为0。
一个页能存放目录项记录的数量是有限的,当数量不足以存放时,同样用一个新页来存放。如下图所示,假设一个页最多存放4个目录项记录。
当我们通过主键值20查找一条记录时:
- 确定目录项页:页30里的目录项记录的主键值范围为[1,320),因此到页30中查找
- 通过目录项记录确定记录所在页。
- 在页中定位具体的记录
为了定位到存储目录项记录的页,我们需要为这些页再生成一个更高级的目录。如下图所示,页33存放目录项纪录页。
可以看出,这是一个B+树。存放用户记录的是0层。
聚簇索引
具有下面两种特性的B+树称为聚簇索引:
(1)通过记录中主键值的大小来进行记录和页的记录。即页的记录是按主键大小排成一个单向链表;存放记录的页是根据记录中主键大小排成一个双向链表;同一层次的页是根据页中目录项记录的主键大小排成一个双向链表。
(2)B+树的叶子节点存储的是完整用户记录。
InnoDB存储引擎会⾃动为主键(如果没有它会⾃动帮我们添加)建⽴聚簇索引。
⼆级索引
上面介绍的聚簇索引只有在搜索条件是主键值时才能发挥作用,因为B+树中的数据都是按主键排序的。若是以其他列c2作为搜索条件,可以建立多颗B+树:
- 通过记录中c2的大小来进行记录和页的记录。即页的记录是按c2大小排成一个单向链表;存放记录的页是根据记录中c2大小排成一个双向链表;同一层次的页是根据页中目录项记录的c2大小排成一个双向链表。
- B+树的叶子节点只存储c2列+主键的值,而不是存储完整的用户记录。
- 目录项记录中的字段为c2列+页号。
我们将这种按非主键值建立的B+树称为二级索引。当我们通过这种B+树搜索时,最后可以到达某一叶子节点,但由于叶子节点并没有存储用户记录,我们只能通过叶子节点中的主键值去聚簇索引中查找⼀遍完整的⽤户记录。这个过程称为回表。
把完整的用户记录放到叶子节点虽然可以不用回表,但会很占空间。
联合索引
同样我们可以以多个列的大小作为排序规则,比如以c2,c3作为排序标准:
- 每条目录项记录由c2、c3、⻚号组成,各条记录先按c2排序,若c2相同再按c3排序。
- B+树叶子节点处的用户记录由c2、c3和主键组成。
这种B+树称为联合索引。需要注意的是,如果是将c2,c3分别作为索引,则会分别建立以c2,c3列为排序标准的两颗B+树。
注意事项
(1)一个B+树索引的根节点在诞生之后,是不会移动的。
(2)同一层节点的目录项记录除页号外是唯一的。
假设我们以c2作为索引列,表中的记录如下:
对于c2建立的二级索引的B+数应该如下图所示,可以看出,页3中存储的目录项纪录应该是c2列+页号,c2值都是1。这样如果要新插入一条新纪录,而这个记录的c2项值也为1时,我们就无法知道是该放在页4还是页5.
因此为了能让新插入记录能找到自己在哪一页,我们需要保证在B+树种同一层节点的目录项记录除了页号字段以外,都是唯一的。因此对于二级索引的目录项纪录而言,实际是由三部分组成:
- 索引列的值
- 主键值
- ⻚号
这样通过主键值就可以保证每一层节点的唯一性:当我们新插入一条c2列值同为1时,接着比较主键值。
MyISAM中的索引⽅案
MyISAM中的索引虽然也使用树形结构,但是将索引和数据分开存储:
- 将表中的记录按照记录的插入顺序单独存储在一个文件中,称为数据文件。这个文件不会划分为若干数据页,有多少记录就往文件中加记录。我们可以通过行号来快速访问一条记录。
由于插入的数据不是按主键大小排序,因此不能使用二分法来查找数据。使用MyISAM的表会把索引信息存储到一个称为索引文件的文件中,MyISAM单独为表的主键创建一个索引,只不过索引的叶子节点不是存储完整的用户记录,而是主键+行号。通过索引找到行号,再通过行号找到对应记录。这类似于在InnoDB的回表操作。
我们同样可以为其他列分别建立索引或联合索引,原理和InnoDB的索引差不多,不过在叶子节点中存储的是相应列+行号。
MySQL中创建和删除索引的语句
InnoDB和MyISAM会⾃动为主键或者声明为UNIQUE的列去⾃动建⽴B+树索引。由于每建立一个索引都需要维护各个记录,数据页的排序,因此若我们想为其他列建立索引,则需要显示指明。
创建表时指定需要建立索引的某一列语句如下,其中KEY和INDEX是同义词,任选⼀个就可以。
CREATE TALBE 表名 (
各种列的信息 ··· ,
[KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
)
CREATE TABLE index_demo(
c1 INT,
c2 INT,
c3 CHAR(1),
PRIMARY KEY(c1),
INDEX idx_c2_c3 (c2, c3)
);
同样我们可以在修改表结构时添加索引:
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);
或在修改表结构时删除索引
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;
ALTER TABLE index_demo DROP INDEX idx_c2_c3;
B+ 树索引的使⽤
索引的代价
(1)每建⽴⼀个索引都要为它建⽴⼀棵B+树,每⼀棵B+树的每⼀个节点都是⼀个数据⻚,⼀个⻚默认会占⽤16KB的存储空间。
(2)每次对表中的数据进⾏增、删、改操作时,都需要去修改各个B+树索引。
B+ 树索引适用的条件
先建立一个表person_info,并定义二级索引引idx_name_birthday_phone_number,它由3个列组成的联合索引。
CREATE TABLE person_info(
id INT NOT NULL auto_increment,
name VARCHAR(100) NOT NULL,
birthday DATE NOT NULL,
phone_number CHAR(11) NOT NULL,
country varchar(100) NOT NULL,
PRIMARY KEY (id),
KEY idx_name_birthday_phone_number (name, birthday, phone_number)
);
全值匹配
搜索条件中的列和索引列一致。如下面的查询语句
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '151239';
where字句中的几个搜索条件的顺序不会对查询结果有影响,因为MySQL有查询优化器,会分析搜索条件并按可以使用的索引列的顺序来决定先使用哪个搜索条件。
匹配左边的列
搜索语句中可以不用包含全部索引列,只包含左边的就行
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';
而如果是只包含右边的列,如下所示,是用不到B+树索引。因为B+树是按name,birthday来进行排序比较的,直接跳过name列是不行的。
SELECT * FROM person_info WHERE birthday = '1990-09-27';
而如果搜索条件只有name和phone_number,没有中间的索引列,则只能用到name列索引。
SELECT * FROM person_info WHERE name = 'Ashburn' AND phone_number = '15123983239';
匹配列前缀
对于字符串类型的索引列name来说,我们只匹配它的前缀也是可以快速定位到记录的,例如找出以'As'开头的记录:
SELECT * FROM person_info WHERE name LIKE 'As%';
但如果只给出后缀或中间的某个字符串,就无法快速定位了。因为中间有'As'的字符串没有排好序,只能全表扫描。
SELECT * FROM person_info WHERE name LIKE '%As%';
假设有一个url列,且已为url列创建索引。如果我们希望查询以com为后缀的网站,而又希望使用到url索引。
+------------------------+
| url |
+-----------------------+
| www.baidu.com |
| www.google.com |
| www.gov.cn |
| ... |
| www.wto.org |
+----------------------+
则可以把表中的数据全部逆序存储,然后搜索条件写为:WHERE url LIKE 'moc%',这样就可以用到索引了。
+------------------------+
| url |
+-----------------------+
| moc.udiab.www |
| moc.elgoog.www |
| nc.vog.www |
| ... |
| gro.otw.www |
+----------------------+
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' AND birthday > '1980-01-01';
匹配范围值
所有记录都是按索引列从小到大排好序的,因此如果我们查找索引列早某个范围的记录是非常方便的。
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';
不过如果我们是对多个列同时进行范围查找的话,则只有对索引最左边的列进行范围查找的时候才能用到B+树索引。
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' AND birthday > '1980-01-01';
上面的查询只用到了name索引列部分,因为只有name值相同才能用到birthday列的值进行排序。而这个查询中通过name进行范围查找的记录可能并不是按birthday列进行排列的。
回表的代价
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';
上面的查询过程分为:
- 在索引idx_name_birthday_phone_number对应的B+树中取出name值在Asa~Barlow之间的⽤户记录。
- 由于索引idx_name_birthday_phone_number对应的B+树中叶子节点的用户记录只包含含name、birthday、phone_number、id,而查询要求还需要country字段。因此还需要一次回表。
由于idx_name_birthday_phone_number对应的B+树中的记录会先按name列值进行排序,因此Asa~Barlow之间的记录在磁盘中的存储是连续的集中分布在一个或几个数据页中,我们可以很快将这些连着的记录从磁盘中读出来,这种读取方式称为顺序I/O。
而从第1步中获取到的记录的主键值id的值可能不是相连的,而在聚簇索引中的记录是按id排序的,所以这些不连续的id值在聚簇索引中访问到的用户记录可能分布在不同的数据页中,这样的读取需要访问更多的数据页,这种读取方式称为随机I/O。
一般情况下顺序I/O要比随机I/O的性能高很多,因此步骤1要比步骤快。需要回表的记录越多,使用二级索引的性能就越低。甚至我们会更希望某些查询使用全表查询而非二级索引。而何时采用全表扫描,何时采用二级索引+回表取执行查询,这个工作是由查询优化器来做。
查询优化器会事先对表中的记录计算一些统计数据,利用这些统计数据根据查询条件来计算需要回表的记录数,需要回表的记录数越多,就月倾向于全表扫描。一般情况下,限制查询获取较少的记录数会让优化器更倾向于使用二级索引+回表的方式进行查询。比如上例可以改写为如下,添加了LIMIT 10。
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' LIMIT 10;
覆盖索引
为了彻底不需要回表,我们最好在返回的查询结果中只包含索引列,如下。
SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'
上面的查询中只查询了三个索引列的值,因此不需要聚簇索引。我们将只需要用到索引的查询方式称为索引覆盖。排序操作也优先使用覆盖索引的方式进行查询:
SELECT name, birthday, phone_number FROM person_info ORDER BY name, birthday, phone_number;
如何挑选索引
(1)只为出现在WHERE子句中的列,连接子句中的连接列,或者出现在ORDER BY或GROUP BY⼦句中的列创建索引。出现在查询列表中的列就没必要建立索引。
比如下面的查询列表中的birthday、country就不需要建立索引,只需为name列创建索引即可。
SELECT birthday, country FROM person_name WHERE name = 'Ashburn';
(2)考虑列的基数
列的技术是指某一列中不重复数据的个数,比如某个列的值分别为2,5, 8, 2, 5, 8, 2, 5, 8,则该列基数为3。列的基数影响我们是否能有效利用索引:假设某个列的基数为1,即所有记录的列值都相同,那么为该列建立索引是没有用的,因为值一样,无法进行快速查找。如果以某列作为二级索引且该列的重复值很多,则可能还有做多次回表操作,性能消耗更大。因此,最好为那些列的基数大的列建立索引。
(3)索引列的类型尽量小
以整数类型为例,有TINYINT、MEDIUMINT、INT、BIGINT几种,它们占用的存储空间依次递增,能表示的整数范围也依次递增。标题所说的类型大小是指该类型表示的数据范围的大小,若我们想对某个整数列建立索引,在表示的整数范围运行的情况下,尽量让索引列使用较小的类型:数据类型越小,索引占用的存储空间越少,一个数据页内就可以存放更多的记录。同时在查询时进行比较的操作越快。
(4)索引字符串的前缀
MySQL中使用utf8字符集去存储字符串时,编码一个字符需要占用1~3个字节,如果字符串很长,则占用存储空间更多。当我们为这个字符串列建立索引时:
- B+树索引中的记录需要存储该列的完整字符串,且字符串越长,索引中占有的空间越大
- 同时进行比较时会占用更多的时间
因此,当对一个列建立索引时,我们可以只对字符串的前几个字符进行索引。在二级索引的记录只保留字符串的前几个字符,这样查找记录时虽然不能精确定位到记录的位置,但是能定位到相应前缀所在的位置,然后根据前缀相同的记录的主键值去回表查询完整的字符串,再对比即可。这样不仅节省空间,且较少了字符串的比较时间。
比如说在创建表时只对name列的值的前10个字符进行索引:
CREATE TABLE person_info(
name VARCHAR(100) NOT NULL,
birthday DATE NOT NULL,
phone_number CHAR(11) NOT NULL,
country varchar(100) NOT NULL,
KEY idx_name_birthday_phone_number (name(10), birthday, phone_number)
);
(5)冗余和重复索引
有时我们可能无意或有意的对同一个列创建了多个索引
KEY idx_name_birthday_phone_number (name(10), birthday, phone_number),
KEY idx_name (name(10))
此处的idx_name就属于一个冗余索引,它不会对搜索有好处,只会增加维护成本。
另外我们可能会对某个列重复建立索引:
CREATE TABLE repeat_index_demo (
c1 INT PRIMARY KEY,
c2 INT,
UNIQUE uidx_c1 (c1),
INDEX idx_c1 (c1)
);
可以看出:c1既是主键,又被定义了一个唯一索引和普通索引。后两者是重复的,我们需要避免这种情况
(6)最好让主键拥有AUTO_INCREMENT属性
对于使用了InnoDB的存储引擎的表而言,如果我们没有显示创建索引,表中的数据都是存储在聚簇索引的叶子节点中,而记录是存储在数据页中,数据页和记录又是按照主键值从小到大进行排序,如果我们插入的记录的主键值是依次增大的话,那么每插满一个数据页,就要插入到另一个数据页。而如果我们插入的主键值忽大忽小,就会造成麻烦。
比如说某个数据页存储的记录已满,此时如果我们要插入一条主键值为9的记录,则需要把当前页面分裂成两个页面,把本页中某些记录移动到新创建的页中,这意味着会有性能损耗。为了避免这种情况,我们最好让插入的记录的主键值依次递增:让主键具有AUTO_INCREMENT,让存储引擎⾃⼰为表⽣成主键,⽽不是我们⼿动插⼊。
Hash索引
对于每一行数据,存储引擎会对所有索引列计算一个哈希码,不同键值的行计算出来的哈希码不一样。哈希索引将所有的哈希码存储在所有中,在哈希表中保存指向每个记录的指针。MySQL中,只有Memory存储引擎显示支持hash索引,是Memory表的默认索引类型。不过Memory表也可以使用B-Tree索引。
假设创建一个表testhash,对fname列建立hash索引。
在对该列的值使用hash函数后,就有如下所示的哈希表:哈希值+数据行指针。
哈希索引能以 O(1) 时间进行查找,但无法用于排序和分组;且不能用于部分查找和范围查找。
全文索引
有时我们需要通过关键字的匹配来进行查询过滤,即需要基于相似度的查询,
倘若数据较少,可以用like + %来实现模糊匹配,但是在数据多的情况下,不推荐用like子句。因为在一些情况下,like查询使用不到索引,会扫描全表。(详情见 https://blog.csdn.net/weixin_38750084/article/details/88693872)
而全文索引能比like + %快很多,虽然可能存在精度问题。
- MySQL 5.6 以前的版本,只有 MyISAM 存储引擎支持全文索引;
- MySQL 5.6 及以后的版本,MyISAM 和 InnoDB 存储引擎均支持全文索引;
- 只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。
示例
-
create table test (
-
id int(11) unsigned not null auto_increment,
-
content text not null,
-
primary key(id),
-
fulltext key content_index(content) --创建全文索引
-
) engine=MyISAM default charset=utf8;
-
insert into test (content) values ('a'),('b'),('c');
-
insert into test (content) values ('aa'),('bb'),('cc');
-
insert into test (content) values ('aaa'),('bbb'),('ccc');
-
insert into test (content) values ('aaaa'),('bbbb'),('cccc');
使用全文索引
-
select * from test where match(content) against('a');
-
select * from test where match(content) against('aa');
-
select * from test where match(content) against('aaa');
-
select * from test where match(content) against('aaaa');
前三句搜索得不到结果,而第4句只能得到aaaa这一结果。
造成这一结果的原因之一是最小搜索长度。MySQL 中的全文索引,有两个变量,最小搜索长度和最大搜索长度,对于长度小于最小搜索长度和大于最大搜索长度的词语,都不会被索引。
这两个默认值可通过命令查看:
show variables like '%ft%';
// MyISAM
ft_min_word_len = 4;
ft_max_word_len = 84;// InnoDB
innodb_ft_min_token_size = 3;
innodb_ft_max_token_size = 84;
而插入的数据的只有aaaa长度符合。
因此我们需要重新配置最小搜索长度:
(1)打开 MySQL 的配置文件 /etc/my.cnf,在 [mysqld] 的下面追加以下内容
(2)
-
[mysqld]
-
innodb_ft_min_token_size = 1
-
ft_min_word_len = 1
(3)重启mysql服务器,修复全文索引
repair table test quick;
重新执行上述查询即可。但在搜索关键字a时,aa,aaa,aaaa都没有出现。因此我们需要加上通配符*,并标上布尔标识。
select * from test where match(content) against('a*' in boolean mode);
全文索引又分自然语言的全文索引和布尔全文索引。
(1)自然语言的全文索引
默认情况下,或者使用 in natural language mode 修饰符时,match() 函数对文本集合执行自然语言搜索。自然语言搜索引擎将计算每一个文档对象和查询的相关度。这里,相关度是基于匹配的关键词的个数,以及关键词在文档中出现的次数。在整个索引中出现次数越少的词语,匹配时的相关度就越高。相反,非常常见的单词将不会被搜索,如果一个词语的在超过 50% 的记录中都出现了,那么自然语言的搜索将不会搜索这类词语。因此在测试表中必须有 4 条以上的记录。
(2)布尔全文索引
在布尔搜索中,我们可以在查询中自定义某个被搜索的词语的相关性,当编写一个布尔搜索查询时,可以通过一些前缀修饰符来定制搜索。
MySQL 内置的修饰符,上面查询最小搜索长度时,搜索结果 ft_boolean_syntax 变量的值就是内置的修饰符。而上例所加的(*)就是其中之一。
参考博客
https://juejin.im/book/5bffcbc9f265da614b11b731 《MySQL是怎样运行的:从根儿上理解MySQL》
上一篇: mysql数据库(SQL语句)
下一篇: Java怎么在运行期间鉴定数据类型