正确的创建合适的索引,是提升数据库查询性能的基础。在正式讲解之前,对后面举例中使用的表结构先简单看一下:
create table user
(
id bigint not null comment 'id' primary key,
name varchar(200) null comment 'name',
age bigint null comment 'age',
gender int null comment 'gender',
key (name)
);
索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。其工作机制如下图:
img
上图中,如果现在有一条sql语句 select * from user where id = 40
,如果没有索引的条件下,我们要找到这条记录,我们就需要在数据中进行全表扫描,匹配id = 13的数据。
如果有了索引,我们就可以通过索引进行快速查找,如上图中,可以先在索引中通过id = 40进行二分查找,再根据定位到的地址取出对应的行数据。
对数据的加速检索,首先想到的就是二叉树,二叉树的查找时间复杂度可以达到O(log2(n))。下面看一下二叉树的存储结构:
img
二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率,但是它有一个问题:二叉树以第一个插入的数据作为根节点,如上图中,如果只看右侧,就会发现,就是一个线性链表结构。如果我们现在的数据只包含1, 2, 3, 4,就会出现
img
以下情况:
如果我们要查询的数据为4,则需要遍历所有的节点才能找到4,即,相当于全表扫描,就是由于存在这种问题,所以二叉查找树不适合用于作为索引的数据结构。
为了解决二叉树存在线性链表的问题,会想到用平衡二叉查找树来解决。下面看看平衡二叉树是怎样的:
img
平衡二叉查找树定义为:节点的子节点高度差不能超过1,如上图中的节点20,左节点高度为1,右节点高度0,差为1,所以上图没有违反定义,它就是一个平衡二叉树。保证二叉树平衡的方式为左旋,右旋等操作,至于如何左旋右旋,可以自行去搜索相关的知识。
如果上图中平衡二叉树保存的是id索引,现在要查找id = 8的数据,过程如下:
索引保存数据的方式一般有两种:
到这里,平衡二叉树解决了存在线性链表的问题,数据查询的效率好像也还可以,基本能达到O(log2(n)), 那为什么mysql不选择平衡二叉树作为索引存储结构,他又存在什么样的问题呢?
那有没有一种结构能够解决二叉树的这种问题呢?有,那就是多路平衡查找树。
B Tree 是一个绝对平衡树,所有的叶子节点在同一高度,如下图所示:
img
上图为一个2-3树(每个节点存储2个关键字,有3路),多路平衡查找树也就是多叉的意思,从上图中可以看出,每个节点保存的关键字的个数和路数关系为:关键字个数 = 路数 – 1。
假设要从上图中查找id = X的数据,B TREE 搜索过程如下:
为什么说这种结构能够解决平衡二叉树存在的问题呢?
B Tree 能够很好的利用操作系统和磁盘的交互特性, MySQL为了很好的利用磁盘的预读能力,将页大小设置为16K,即将一个节点(磁盘块)的大小设置为16K,一次IO将一个节点(16K)内容加载进内存。这里,假设关键字类型为 int,即4字节,若每个关键字对应的数据区也为4字节,不考虑子节点引用的情况下,则上图中的每个节点大约能够存储(16 * 1000)/ 8 = 2000个关键字,共2001个路数。对于二叉树,三层高度,最多可以保存7个关键字,而对于这种有2001路的B树,三层高度能够搜索的关键字个数远远的大于二叉树。
这里顺便说一下:在B Tree保证树的平衡的过程中,每次关键字的变化,都会导致结构发生很大的变化,这个过程是特别浪费时间的,所以创建索引一定要创建合适的索引,而不是把所有的字段都创建索引,创建冗余索引只会在对数据进行新增,删除,修改时增加性能消耗。
B树确实已经很好的解决了问题,我先这里先继续看一下B+Tree结构,再来讨论BTree和B+Tree的区别。
先看看B+Tree是怎样的,B+Tree是B Tree的一个变种,在B+Tree中,B树的路数和关键字的个数的关系不再成立了,数据检索规则采用的是左闭合区间,路数和关键个数关系为1比1,具体如下图所示:
img
如果上图中是用ID做的索引,如果是搜索X = 1的数据,搜索规则如下:
这里主要讲解的是MySQL根据B+Tree索引结构不同的两种存储引擎(MYISAM 和 INNODB)的实现。
首先找到MySQL保存数据的文件夹,看看MySQL是如何保存数据的:
mysql> show variables like '%datadir%';
+---------------+------------------------+
| Variable_name | Value |
+---------------+------------------------+
| datadir | /usr/local/mysql/data/ |
+---------------+------------------------+
进入到这个目录下,这个目录下保存的是所有数据库,再进入到具体的一个数据库目录下。就能够看到MySQL存储数据和索引的文件了。
这里我创建了两张表,user_innod和user_myisam,分别指定索引为innodb和myisam。对于每张表,MySQL会创建相应的文件保存数据和索引,具体如下:
-rw-rw----. 1 mysql mysql 8652 May 3 21:11 user_innodb.frm
-rw-rw----. 1 mysql mysql 109051904 May 7 21:26 user_innodb.ibd
-rw-rw----. 1 mysql mysql 8682 May 16 18:27 user_myisam.frm
-rw-rw----. 1 mysql mysql 0 May 16 18:27 user_myisam.MYD
-rw-rw----. 1 mysql mysql 1024 May 16 18:27 user_myisam.MYI
从图中可以看出:
说明:为了画图简便,下面部分图使用在线数据结构工具进行组织数据,组织的B+Tree为右闭合区间,但不影响理解存储引擎数据存储结构。
在MYISAM存储引擎中,数据和索引的关系如下:
img
如何查找数据的呢?
如果要查询id = 40的数据:先根据MyISAM索引文件(如上图左)去找id = 40的节点,通过这个节点的数据区拿到真正保存数据的磁盘地址,再通过这个地址从MYD数据文件(如上图右)中加载对应的记录。
如果有多个索引,表现形式如下:
img
所以在MYISAM存储引擎中,主键索引和辅助索引是同级别的,没有主次之分。
Innodb主键索引为聚集索引,首先简单理解一下聚集索引的概念:数据库表行中数据的物理顺序和键值的逻辑顺序相同。
Innodb以主键索引来聚集组织数据的存储,下面看看Innodb是如何组织数据的。
img
如上图中,叶子节点的数据区保存的就是真实的数据,在通过索引进行检索的时候,命中叶子节点,就可以直接从叶子节点中取出行数据。mysql5.5版本之前默认采用的是MyISAM引擎,5.5之后默认采用的是innodb引擎。
在innodb中,辅助索引的格式如下图所示?
img
如上图,主键索引的叶子节点保存的是真正的数据。而辅助索引叶子节点的数据区保存的是主键索引关键字的值。
假如要查询name = C 的数据,其搜索过程如下:
所以通过辅助索引进行检索,需要检索两次索引。
之所以这样设计,一个原因就是:如果和MyISAM一样在主键索引和辅助索引的叶子节点中都存放数据行指针,一旦数据发生迁移,则需要去重新组织维护所有的索引。
把Innodb 和 MYISAM区别放在一张图中看,就如下所示:
img
离散型的计算公式:count(distinct column_name):count(*)
,就是用去重后的列值个数比个数。值在 (0,1] 范围内。离散型越高,选择型越好。
如下表中各个字段,明显能看出Id的选择性比gender更高。
mysql> select * from user;
+----+--------------+------+--------+
| id | name | age | gender |
+----+--------------+------+--------+
| 20 | 君莫笑 | 15 | 1 |
| 40 | 苏沐橙 | 12 | 0 |
| 50 | 张楚岚 | 25 | 1 |
| 60 | 诸葛青 | 27 | 1 |
| 61 | 若有人兮 | 38 | 0 |
| 64 | 冯宝宝 | 18 | 0 |
+----+--------------+------+--------+
为什么说离散型越高,选择型越好?
因为离散度越高,通过索引最终确定的范围越小,最终扫面的行数也就越少。
对于索引中的关键字进行对比的时候,一定是从左往右以此对比,且不可跳过。之前讲解的id都为int型数据,如果id为字符串的时候,如下图:
img
当进行匹配的时候,会把字符串转换成ascll码,如abc变成97 98 99,然后从左往右一个字符一个字符进行对比。所以在sql查询中使用like %a 时候索引会失效,因为%表示全匹配,如果已经全匹配就不需要索引,还不如直接全表扫描。
前面已经说过,当关键字占用的空间越小,则每个节点保存的关键字个数就越多,每次加载进内存的关键字个数就越多,检索效率就越高。创建索引的关键字要尽可能占用空间小。
可以把单列索引看成特殊的联合索引,联合索引的比较也是根据最左匹配原则。
下面简单举例平时经常会遇到的问题:
如,平时经常使用的查询sql如下:
select * from users where name = ?
select * from users where name = ? and age = ?
为了加快检索速度,为上面的查询sql创建索引如下:
create index idx_name on users(name)
create index idx_name_age on users(name, age)
在上面解决方案中,根据最左匹配原则,idx_name为冗余索引, where name = ?同样可以利用索引idx_name_age进行检索。冗余索引会增加维护B+TREE平衡时的性能消耗,并且占用磁盘空间。
如果查询的列,通过索引项的信息可直接返回,则该索引称之为查询SQL的覆盖索引。覆盖索引可以提高查询的效率。
img
如上图,如果通过name进行数据检索:
select * from users where name = ?
需要需要在name索引中找到name对应的Id,然后通过获取的Id在主键索引中查到对应的行。整个过程需要扫描两次索引,一次name,一次id。
如果我们查询只想查询id的值,就可以改写SQL为:
select id from users where name = ?
因为只需要id的值,通过name查询的时候,扫描完name索引,我们就能够获得id的值了,所以就不需要再去扫面id索引,就会直接返回。
当然,如果你同时需要获取age的值:
select id,age from users where name = ?
这样就无法使用到覆盖索引了。
知道了覆盖索引,就知道了为什么sql中要求尽量不要使用select *
,要写明具体要查询的字段。其中一个原因就是在使用到覆盖索引的情况下,不需要进入到数据区,数据就能直接返回,提升了查询效率。在用不到覆盖索引的情况下,也尽可能的不要使用select *
,如果行数据量特别多的情况下,可以减少数据的网络传输量。当然,这都视具体情况而定,通过select返回所有的字段,通用性会更强,一切有利必有弊。
“ 文章已经收录GitHub:https://github.com/JavaFamily
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。