【笔记】MySQL 是怎样运行的【3】B+树索引原理及使用方法

发布于:2019-07-16 21:22,阅读数:123,点赞数:0


[toc] # B+ 树索引 ## 没有索引的查找 在查找记录的时候,分为两种情况: - 以主键为搜索条件:这个过程就是之前讲的,在页目录中用二分法找到对应槽然后再在槽里找。 - 以其他列为搜索条件:其他列是没有所谓的页目录的,因此没法二分查找,只能逐条比较,效率很低。 ## 索引 举个例子,先建一张表并插入三条记录。 ![](//cdn.blog.yuusann.com/img/corpus/19080_1.png) 现在插入第四条记录,由于主键遵循一定的顺序,因此这次插入记录需要更换位置。 ![](//cdn.blog.yuusann.com/img/corpus/19080_2.png) 由于新分配的页不是挨着的,因此插入很多条记录以后,会变成这样。 ![](//cdn.blog.yuusann.com/img/corpus/19080_3.png) 为了快速能找到这些页,就会简历一个索引。 ![](//cdn.blog.yuusann.com/img/corpus/19080_4.png) ## InnoDB 中的索引方案 在`InnoDB`中,复用了之前存储记录的页来存储目录,页头里的`record_type`字段可以用来区分是数据页还是目录页。 - 0:普通的用户记录 - 1:目录项记录 - 2:最小记录 - 3:最大记录 所以现在,当要查找一条记录,分为以下三步: - 先到目录项页中用二分查找快速定位是哪个页。 - 到对应的页中用二分查找快速定位是哪个槽。 - 最后到槽里逐条找。 当目录页一页不够用时,就会分配多页。 ![](//cdn.blog.yuusann.com/img/corpus/19080_5.png) 所以在以上的流程中增加一步:二分查找快速定位是哪个目录页,然后再进行以上步骤。 那么问题是这些目录页也是分散的,如何快速找到这些目录页呢?答案是`多级目录`。 ![](//cdn.blog.yuusann.com/img/corpus/19080_6.png) 这个结构其实就是个`B+树`。 ![](//cdn.blog.yuusann.com/img/corpus/19080_7.png) 用于存放用户数据的节点在最底下,称为第0层。假设一个数据页能存放100条记录,一个目录页能存放1000条索引,那么1层B+树能够存放`100条`记录,2层能够存放`100×1000条`即十万条,3层能存放`100×1000×1000条`即一亿条,4层能存放`100×1000×1000×1000条`即一千亿条。所以理论上不会超过四层,只要通过四个页面的查找,就可以快速定位记录了。 ### 聚簇索引 上面提到的B+树本身就是个目录,具有两个特点: - 记录根据主键值大小进行排序了 - 页内的记录是按照主键大小排成的单向链表 - 存放记录的各个页也根据主键大小排成了双向链表 - 存放索引的页,同一层也按主键大小排成了双向链表 - 叶子节点存放的是完整的记录数据 我们把满足以上两个特性的B+树称为聚簇索引,所有完整的记录数据都存放在叶子节点。这种索引并不需要使用`INDEX`语句去创建,InnoDB 引擎会自动帮我们创建。 ### 二级索引 聚簇索引只有根据主键查找才会发挥作用,但只要根据各个列都建立一棵B+树,就可以针对所有列都进行二分查找了。 这样建立的B+树有以下特点: - 记录根据特定列大小进行排序了 - 叶子节点存放的是特定列值和主键值这两个值 在查找时,首先要在这棵B+树种找到这个特定列值所对应的主键值,然后再用这个主键值去聚簇索引查找才能最终找到完整的记录数据。 这种需要`回表`才能最终找到记录数据的索引称为二级索引。 ### 联合索引 不但可以给单个字段创建索引,还可以给多个字段创建联合索引。 我们想要B+树先按`c2`排序,`c2`相同的情况下按照`c3`排序。这样的索引,每个目录项都由`c2`、`c3`和页号三部分组成,叶子节点是`c2`、`c3`和`主键`三个值。 ## InnoDB 的B+树的注意事项 ### 根节点万年不动 由于聚簇索引是默认就有的,所以B+树真正的生成过程是先生成根节点,而不是先存放用户数据再建立索引。真正建立的过程: - 建表时,表中没有数据,只会创建一个根节点,既没有数据也有没目录,这个根节点万能不动。 - 插入数据时,先把数据存储到这个根节点里。 - 根节点的空间用完时,再插入记录,就会把根节点所有记录复制到一个新的页,然后对这个新页再进行`页分裂`,得到两个数据页,这时候根节点升级为目录页。 这个根节点从创建之日起就不会移动,这个节点会被记录在一个地方,当 InnoDB 需要用到这个索引时都会从这个固定的地方取根节点的页号来访问这个索引。关于根节点会被储存在哪,后面会详细提到,这个地方为`数据字典`。 ### 节点中目录项记录的唯一性 节点内的记录必须是唯一的,比如如下情况: ![](//cdn.blog.yuusann.com/img/corpus/19080_8.png) 页3是索引节点,两条记录指向不同的页,由于c2的值都一样,这种情况下两条记录就重复了。当新插入一条c2值仍然是1的时候就会发生不知道插到哪一页的情况。 因此需要把主键也加上。 ![](//cdn.blog.yuusann.com/img/corpus/19080_9.png) 这样当c2列相同时,就可以根据主键进行判断了。 ### MyISAM 中的索引方案 以上介绍的都是`InnoDB`的索引,下面简单看一下`MyISAM`存储引擎的索引方案。 `InnoDB`中记录数据存储在聚簇索引的根节点,数据和索引是在一起的,而`MyISAM`把数据和索引分开存储了。 - 把表里的记录按插入顺序存在一个文件里,这个文件叫`数据文件`。不划分页,所有记录都往里塞,可以根据行号快速找到。 - 索引存储在另一个`索引文件`中,`MyISAM`单独为表的主键创建一个索引,叶子节点是`主键+行号`的组合。查找时候先从索引找到行号,然后去数据文件找记录。这意味着就算用主键查找也需要`回表`,意味着`MyISAM`的索引全部都相当于二级索引。(读者注:用行号找记录是 O(1) 的,直接计算偏移量就能拿到,非常快,所以本质上算不上查找。而 InnoDB 中的二级索引回表的时候也是二分查找,所以才能算二次查找) - 给其他列建立索引时使用的也是行号,找到后再根据行号去数据文件找记录。 ### MySQL 中创建和删除索引 创建表时候创建索引: ``` CREATE TALBE 表名 ( 各种列的信息 ··· , [KEY|INDEX] 索引名 (需要被索引的单个列或多个列) ) ``` 后期加索引: ``` ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列); ``` 后期删索引: ``` ALTER TABLE 表名 DROP [INDEX|KEY] 索引名; ``` 例如,创建表时创建`c2`和`c3`的联合索引: ``` CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1), INDEX idx_c2_c3 (c2, c3) ); ``` 后期要删除时: ``` ALTER TABLE index_demo DROP INDEX idx_c2_c3; ``` # B+树索引的使用 ## 索引的代价 - 空间成本:索引也是页,每一个页占`16KB`空间,太多索引会占用很大磁盘空间。 - 时间成本:插入、删除记录的时候都需要去各个索引操作B+树,这些索引维护成本耗时。 ## B+树索引适用的条件 举个例子。 ``` 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) ); ``` 建了张表,以及按照`name`、`birthday`、`phone_number`三个字段建立了一个联合索引。联合索引的顺序非常重要。 ![](//cdn.blog.yuusann.com/img/corpus/19080_10.png) ### 全值匹配 如果查找时搜索条件和索引列一致的话,称为全值匹配。 ``` SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239'; ``` 这种情况是可以利用我们创建的索引的。查找时候三个字段顺序不一样也没有关系,在查询优化阶段会调整过来,后面会讲这个阶段。 ### 匹配左边的列 匹配索引左边的列也可以使用索引。 ``` SELECT * FROM person_info WHERE name = 'Ashburn'; ``` 多个也可以。 ``` SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27'; ``` 但是如果没有从最左边的字段开始查询,是不可以使用索引的,比如这种情况。 ``` SELECT * FROM person_info WHERE birthday = '1990-09-27'; ``` 如果查询时中间跳过了一个,那么只能用到一部分索引,比如下面这个情况。 ``` SELECT * FROM person_info WHERE name = 'Ashburn' AND phone_number = '15123983239'; ``` 这种情况只能使用`name`的索引,后面的就没法用了。 ### 匹配列前缀 如果是字符串字段,字符串比较大小时候是先比较第一个字符,排序,然后看第二字符,依次对比下去排序的。因此在匹配前缀的时候也是可以利用索引的。 ``` SELECT * FROM person_info WHERE name LIKE 'As%'; ``` 但是匹配中间字段就不能用索引了,只能靠全表扫描。 ``` SELECT * FROM person_info WHERE name LIKE '%As%'; ``` 一个显著的例子是`域名表`。 ``` +----------------+ | url | +----------------+ | www.baidu.com | | www.google.com | | www.gov.cn | | ... | | www.wto.org | +----------------+ ``` 如果需要查找所有`com`域名,匹配`%.com`,此时无法使用索引。但是如果倒过来: ``` +----------------+ | url | +----------------+ | moc.udiab.www | | moc.elgoog.www | | nc.vog.www | | ... | | gro.otw.www | +----------------+ ``` 查找`moc.%`就可以利用索引轻松找到了。 ### 匹配范围值 匹配范围的语句: ``` SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow'; ``` 由于建立了索引的是个现以`name`字段排序的链表,其过程是: - 找到`Asa`的目录项 - 找到`Barlow`的目录项 - 这两个节点之间的链表节点都是结果 - 拿着这些目录项回表查到具体的记录 如果是多个范围匹配,只有最左边的条件可以用到索引。 ``` SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000'; ``` 这个查询分为三步: - `name = 'Ashburn'`,这一步可以利用索引。 - `birthday > '1980-01-01' AND birthday < '2000-12-31'`,由于`name`和`birthday`是联合索引的最左边的两个字段,找完`name`后,`birthday`是个有序的链表,因此还是可以利用索引进行二分查找。 - `phone_number > '15100000000'`这一步就只能遍历了,无法使用索引。 ### 用于排序 使用`ORDER BY`时候,一般情况下需要把查出来的结果放在内存中然后进行排序。如果查出来的结果集太大不能放在内存中排序的情况下,可能会暂时需要借助磁盘进行排序。如果涉及到磁盘操作,这个过程会非常慢,但如果借助索引,就能够避免这个问题。 ``` SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10; ``` 由于我们建立的索引本身就是按照这个顺序排序的,所以查询结束直接就是排序好的结果了,就可以避免这个问题了。 以下情况,无法使用索引: - 字段顺序和索引一样,或索引的最左边几个字段,否则无法使用。 - 而且排列顺序要么全部正序,要么全部逆序,否则无法使用。 - WHERE 中出现了别的列。 - 排序里包含了不是同一个索引里的列。 - 排序里使用了复杂表达式 ### 用于分组 字段顺序和索引一样,或索引的最左边几个字段,否则无法使用。 ## 回表的代价 例如以下这个查询: ``` SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow'; ``` 这个查询步骤如下: - 从索引里取出`name`在`Asa`和`Barlow`之间的节点。 - 由于索引里只包含`name`、`age`、`birthday`、`id`这四个字段,而查询要求的是`*`,所以需要回表把其他字段都查出来,把完整结果返回去。 第一步中,取出的数据是连续的链表,所以能够很快一次性取出来,叫`顺序I/O`。而第一步结束拿到了各个记录的`id`,拿着这些`id`去聚簇索引里找记录的时候是`随机I/O`,所以性能会差很多。如果第一步的结果占了全表的90%,那这种情况还不如直接去聚簇索引里全表扫描。 查询结果越少,则越倾向于`二级索引+回表`的方式,否则更倾向于全表扫描。查询优化阶段会做这个评估。 如果添加`LIMIT`,则会让查询优化倾向于走`二级索引+回表`的方式。 ## 覆盖索引 为了彻底告别`回表`带来的损耗,建议:最好在查询列表里只包含索引字段。 如: ``` SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow' ``` 只用到索引的列,把这种查询方式称为`索引覆盖`。排序操作也优先使用`索引覆盖`的方式进行查询。 另外,很不鼓励用`*`的方式查询,最好按照顺序把要查的列标明。 ## 如何挑选索引 ### 只为用于搜索、排序或分组的列创建索引 比如: ``` SELECT birthday, country FROM person_name WHERE name = 'Ashburn'; ``` 这句中,只需要给`name`创建就可以了,其他就不用了。 ### 考虑列的基数 `列的基数`指的是某一列中不重复数据的个数,比方说某个列包含值`2, 5, 8, 2, 5, 8, 2, 5, 8`,虽然有`9`条记录,但该列的基数却是`3`。 记录行数一定的情况下,列基数越大代表值越分散,反之越几种。如果一个列的基数是`1`,代表所有值都一样,那么就算建了索引也是完全没用的。 所以,列基数越大,效果越好。 ### 索引列的类型尽量小 以整数类型为例,有`TINYINT`、`MEDIUMINT`、`INT`、`BIGINT`这么几种。能使用`INT`就不要使用`BIGINT`,能使用`MEDIUMINT`就不要使用`INT`。越小的类型,CPU 在比较的时候更快,磁盘 I/O 也会越小。 ### 索引字符串的前缀 索引时,字符串可以不必用全部内容来进行索引,而是只用前几个字符进行索引。 创建表时,这样写,可以只用`name`的前十个字符建立索引。 ``` 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) ); ``` 不过这种索引方式无法支持排序。 ### 让索引单独在表达式里出现 以下两个表达式虽然语义一样但是性能上有区别: - `WHERE my_col * 2 < 4` - `WHERE my_col < 4 / 2` `my_col * 2`这种形式会导致无法使用索引。 ### 主键插入的顺序 聚簇索引里数据都存在叶子节点。如果主键忽大忽小,当页面满的时候插入记录会导致页面分裂,带来性能损耗。 ![](//cdn.blog.yuusann.com/img/corpus/19080_11.png) 因此主键自增是最佳实践。 ### 冗余和重复索引 过多的索引会带来维护成本,尽量减少重复索引。


评论:0条


返回列表

返回主页