赞
踩
简介: 索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。
高效获取数据
的数据结构
,通俗点的说,数据库索引好比是一本书的目录,可以直接根据页码找到对应的内容,目的就是为了加快数据库的查询速度
。索引的存储原理大致可以概括为一句话:以空间换时间。
一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往是存储在磁盘上的文件中的
(可能存储在单独的索引文件中,也可能和数据一起存储在数据文件中)。
数据库在未添加索引进行查询的时候默认是进行全文搜索,也就是说有多少数据就进行多少次查询,然后找到相应的数据就把它们放到结果集中,直到全文扫描完毕。
主键索引:primary key
唯一索引:
复合索引:
全文索引:
空间索引:
前缀索引:
优点:
缺点:
综合索引的优缺点:
数据库表中不是索引越多越好,而是仅为那些常用的搜索字段建立索引效果最佳!
创建主键索引:
- #建表时,主键默认为索引
- create table user(
- id varchar(11) primary key,
- name varchar(20),
- age int
- )
-
- #查看user表中的索引
- show index from user;
创建单列索引:
- #创建单列索引,只能包含一个字段
- create index name_index on user(name);
创建唯一索引:
- #创建唯一索引,只能有一个列
- create unique index age_index on user(age);
创建符合索引:
- #复合索引
- create index name_age_index on user(name,age);
满足复合索引的查询的两大原则:
**假如创建的复合索引为三个字段,按顺序分别是(name,age,sex)
在查询时能利用复合索引的查询条件如下:**
1、最左前缀原则(如下四种都满足条件)
- select * from user where name = ?
- select * from user where name = ? and age = ?
- select * from user where name = ? and sex = ?
- select * from user where name = ? and age = ? and sex = ?
1.1、如下是不满足最前左缀的条件(但是不是全部都不生效,如下第2原则解释)
- select * from user where name = ? and sex = ? and age = ?
- select * from user where age = ? and sex = ? and name = ?
- select * from user where sex = ? and age = ? and name = ?
- select * from user where age = ? and sex = ?
- …………等等
2.MySQL 引擎在执行查询时,为了更好地利用索引,在查询过程中会动态调整查询字段的顺序!(也就是说,当条件中的字段全部达到复合索引中的字段时,可以动态调整字段顺序,使其满足最前左缀)
- #可以使用复合索引:索引中包含的字段数都有,只是顺序不正确,在执行的时候可以动态调整为最前左缀
- select * from user where sex = ? and age = ? and name = ?
- select * from user where age = ? and sex = ? and name = ?
-
- #不可以使用复合索引:因为缺少字段,并且顺序不正确
- select * from user where sex = ? and age = ?
- select * from user where age = ? and name = ?
- select * from user where age = ?
- select * from user where sex = ?
本文借鉴丙哥文章: 一文搞懂MySQL索引所有知识点
MySQL索引使用的数据结构主要有BTree索引
和hash索引
。
对于hash索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景建议选择BTree索引。
MySQL的索引数据结构最常使用的是B树中的B+Tree
,但对于主要的两种存储引擎的实现方式是不同的。
== InnoDB中data阈存储的是行数据,而MyISAM中存储的是磁盘地址。==
MyISAM:
B+Tree叶节点的data域存放的是数据记录的地址。在索引检索的时候,首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则根据data域中磁盘地址到磁盘中寻址定位到对应的磁盘块,然后读取相应的数据记录,这被称为“非聚簇索引”。
InnoDB:
==其数据文件本身就是索引文件==。相比MyISAM,索引文件和数据文件是分离的,其表数据文件本身就是按照B+Tree组织的一个索引结构,树的叶节点data域保存了完整的数据记录。这个索引的Key是数据表的主键,因此InnoDB表数据文件本身就是主索引。这被称为“ 聚簇索引(聚集索引)”。而其余的索引都作为辅助索引,辅助索引的data域存储相应记录主键的值而不是地址,这也是和MyISAM不同的地方。
Hash表,在Java中的HashMap,TreeMap就是Hash表结构,以键值对的形式存储数据。我们使用hash表存储表数据结构,Key可以存储索引列,Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高,时间复杂度为O(1);但是不支持范围快速查找,范围查找时只能通过扫描全表的方式,筛选出符合条件的数据。
显然这种方式,不适合我们经常需要查找和范围查找的数据库索引使用。
上面这个图就是我们常说的二叉树:每个节点最多有两个分叉节点,左子树和右子树数据按顺序左小右大。
二叉树的特点就是为了保证每次查找都可以进行折半查找,从而减少IO次数。
但是二叉树不是一直保持二叉平衡,因为二叉树很考验根节点的取值,因为很容易在某个节点下不分叉了,这样的话二叉树就不平衡了,也就没有了所谓的能进行折半查找了,如下图:
显然这种不稳定的情况,我们在选择存储数据结构的时候就会尽量避免这种的情况发生。
平衡二叉树采用的是二分法思维
,平衡二叉查找树除了具备二叉树的特点,最主要的特征是树的左右两个子树的层级最多差1。在插入删除数据时通过左旋/右旋
操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。
使用平衡二叉查找树查询的性能接近与二分查找,时间复杂度为O(log2n),查询id=6,只需要两次IO。
就上述平衡二叉树的特点来看,其实是我们理想的状态下,然而其实内部还是存在一些问题:
1百万的数据量,log2n约等于20次磁盘IO读写,时间消耗约等于:20*10=0.2S
)。MySQL的数据是存储在磁盘文件中的,查询处理数据时,需要先把磁盘中的数据加载到内存中,磁盘IO操作非常耗时,所以我们优化的重点就是尽量减少磁盘的IO操作
。访问二叉树的每个节点都会发生一次IO,如果想要减少磁盘IO操作,就需要尽量降低树的高度
。
那如何降低树的高度呢?
假如key为bigint=8字节,每个节点有两个指针,每个指针为4个字节,一个节点占用的空间为(8+4*2=16)。
因为在MySQL的InnoDB引擎的一次IO操作会读取一页的数据量(默认一页大小为16K),而二叉树一次IO操作的有效数据量只有16字节,空间利用率极低。为了最大化的利用一次IO操作空间,一个解决方法就是在一个节点处存储多个元素,在每个节点尽可能多的存储数据。每个节点可以存储1000个索引(16k/16=1000),这样就将二叉树改造成了多叉树,通过增加树的分叉树,将树的体型从高瘦变成了矮胖
。构建1百万条数据,树的高度需要2层就可以(1000*1000=1百万),也就是说只需要两次磁盘IO操作就可以查询到数据,磁盘IO操作次数变少了,查询数据的效率整体也就提高了。
这种数据结构我们称之为B树,==B树是一种多叉平衡查找树==,如下图主要特点:
B树数据结构大致如下:
举个简单的例子,在B树中查询数据的情况:
假如我们要查询key等于10对应的数据data,根据上图我们可知在磁盘中的查询路径是: 磁盘块1->磁盘块2->磁盘块6
相比较二叉平衡查找树,在整个查找过程中,虽然数据的比较次数并没有明显减少,但是对于磁盘IO的次数会大大减少,同时,由于我们是在内存中进行的数据比较,所以比较数据所消耗的时间可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树构建索引可以很好的提升查询的效率。
过程如下图所示:
看到上面的情况,觉得B树已经很理想了,但是其中还是存在可以优化的地方:
B+树,作为B树的升级版,MySQL在B树的基础上继续进行改造,使用B+树构建索引。B+树和B树最主要的区别在于==非叶子节点是否存储数据==的问题。
B+树的大致数据结构:
B+树的最底层叶子节点包含了所有的索引项。从上图可以看出,B+树在查找数据的时候,由于数据都存放在最底层的叶子节点上,所以每次查找都需要检索到叶子节点才能查询到数据。所以在查询数据的情况下每次的磁盘IO次数跟树的高度有直接的关系;但是从另一方面来说,由于数据都被存放到了叶子节点,所以存放索引的磁盘块,所存放的的索引数量会随之增加,所以相对于B树来说,B+树的树高理论情况下是比B树树高要矮的。
但是也存在索引覆盖查询的情况,在索引中数据满足了查询语句所需要的全部数据,此时只需要找到索引即可立刻返回,不需要检索到最底层的叶子节点。
等值查询实例:
假如我们要查询key为9对应的数据data,查询路径为:磁盘块1->磁盘块2->磁盘块6。
范围查询实例:
假如我们想要查找9和26之间的数据,查找路径为:磁盘块1->磁盘块2->磁盘块6->磁盘块7
== 由上述实例可知:B+树可以保证等值和范围查询的快速查找,MySQL的索引采用的就是B+树的结构。==
暂时分析MySQL的两种存储引擎的索引实现:==MyISAM引擎和InnoDB引擎==。
以一个简单的user表为例,user表存在两个索引,id列为主键索引,age列为普通索引。
- CREATE TABLE `user`
- (
- `id` int(11) NOT NULL AUTO_INCREMENT,
- `username` varchar(20) DEFAULT NULL,
- `age` int(11) DEFAULT NULL,
- PRIMARY KEY (`id`) USING BTREE,
- KEY `idx_age` (`age`) USING BTREE
- ) ENGINE = MyISAM
- AUTO_INCREMENT = 1
- DEFAULT CHARSET = utf8;
MyISAM的数据文件和索引文件是分开存储的,MyISAM使用B+树构建索引树时,叶子节点中键值key存储的是索引列的值,数据data存储的是索引所在行的磁盘地址。
主键ID列索引:
表user的索引存储在索引文件user.MYI
中,数据存储在数据文件user.MYD
中。
select * from user where id = 28
user.MYD
中获取对应整行记录。磁盘IO次数:3次索引检索+1次记录数据检索:
select * from user where id between 28 and 47;
磁盘IO次数:4次索引检索+1次记录数据检索。
提示:
以上分析仅供参考,如果使用MyISAM存储引擎在查询时,会将索引节点缓存在MySQL缓存中, 而数据缓存依赖于操作系统自身的缓存, 这里只是为了演示分析索引的使用过程。
每个InnoDB表都有一个聚簇索引,聚簇索引使用B+树构建,叶子节点的data阈存储的是整行记录。一般情况下,聚簇索引等同于主键索引,当一个表没有创建主键索引时,InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下:
除聚簇索引之外的所有索引都被称为辅助索引。在InnoDB中,辅助索引中的叶子节点键值存储的是该行的主键值。在检索时,InnoDB使用此主键在聚餐索引中搜索行记录。
这里以user_innodb表为例,user_innodb的id列为主键,age列为普通索引。
- CREATE TABLE `user_innodb`
- (
- `id` int(11) NOT NULL AUTO_INCREMENT,
- `username` varchar(20) DEFAULT NULL,
- `age` int(11) DEFAULT NULL,
- PRIMARY KEY (`id`) USING BTREE,
- KEY `idx_age` (`age`) USING BTREE
- ) ENGINE = InnoDB;
t_user_innodb.ibd
文件中,InnoDB的数据组织方式,是聚簇索引。
等值查询数据:
select * from user_innodb where id = 28;
发生三次磁盘IO:
辅助索引等值查询的情况:
select * from t_user_innodb where age=19;
在辅助索引树中获取到主键id,再根据主键id到主键索引数中检索数据的的过程称为回表查询
。
磁盘IO数(从根节点开始):辅助索引3次 + 回表过程3次。
idx_abc(a,b,c)
。- CREATE TABLE `abc_innodb`
- (
- `id` int(11) NOT NULL AUTO_INCREMENT,
- `a` int(11) DEFAULT NULL,
- `b` int(11) DEFAULT NULL,
- `c` varchar(10) DEFAULT NULL,
- `d` varchar(10) DEFAULT NULL,
- PRIMARY KEY (`id`) USING BTREE,
- KEY `idx_abc` (`a`, `b`, `c`)
- ) ENGINE = InnoDB;
组合索引的数据结构:
组合索引的查询过程:
select * from abc_innodb where a = 13 and b = 16 and c = 4;
最左前缀匹配原则和联合索引的索引存储结构和检索方式
是有关系的。
在组合索引树中,最底层的叶子节点按照第一列a列从左到右递增排序,但是b列和c列是无序的,b列只有在a列值相等的情况下小范围内有序递增;而clie只能在a和b两列值相等的情况下小范围内有序递增。
就像上面的查询,B+ 树会先比较a列来确定下一步应该检索的方向,往左还是往右。如果a列相同再比较b列,但是如果查询条件中没有a列,B+树就不知道第一步应该从那个节点开始查起。
可以说创建的idx_(a,b,c)索引,相当于创建了(a)、(a,b)、(a,b,c)三个索引。
组合索引的最左前缀匹配原则:
使用组合索引查询时,mysql会一直向右匹配直至遇到范围查询(>、<、between、like)等就会停止匹配。
==覆盖索引并不是一种索引结构,覆盖索引是一种很常用的优化手段==。因为在使用辅助索引的时候,我们只可以拿到相应的主键值,想要获取最终的数据记录,还需要根据主键通过主键索引再去检索,最终获取到符合条件的数据记录。在上面的abc_innodb表中的组合索引查询时,如果我们查询的结果只需要a、b、c这三个字段,那我们使用这个idx_index(a,b,c)组合索引查询到叶子节点时就可以直接返回了,而不需要再次回表查询,这种情况就是==覆盖索引==。
在InnoDB的存储引擎中,使用辅助索引查询的时候,因为辅助索引叶子节点保存的数据不是当前数据记录,而是当前数据记录的主键索引。如果需要获取当前记录完整的数据,就必须要再次根据主键从主键索引中继续检索查询,这个过程我们称之为回表查询。
由此可见,在数据量比较大的时候,回表必然会消耗很多的时间影响性能,所以我们要尽量避免回表的发生。
使用覆盖索引,举个例子:现有User表
- CREATE TABLE `user`
- (
- `id` int(11) NOT NULL AUTO_INCREMENT,
- `name` int(11) DEFAULT NULL,
- `sex` char(3) DEFAULT NULL,
- `address` varchar(10) DEFAULT NULL,
- `hobby` varchar(10) DEFAULT NULL,
- PRIMARY KEY (`id`) USING BTREE,
- KEY `i_name` (`name`)
- ) ENGINE = InnoDB;
如果有一个场景:
select id,name,sex from user where name = 'zhangsan';
这个语句在业务上频繁使用到,而user表中的其他字段使用频率远低于这几个字段,在这个情况下,如果我们在建立name字段的索引时,不是使用单一索引,而是使用联合索引(name,sex)
,这样的话再执行这个查询语句,根据这个辅助索引(name,sex)
查询到的结果就包括了我们所需要的查询结果的所有字段的完整数据,这样就不需要再次回表查询去检索sex字段的数据了。
以上就是一个典型的使用覆盖索引的优化策略减少了回表查询的情况。
联合索引:
在建立索引的时候,尽量在多个单列索引上判断是否可以使用联合索引。联合索引的使用不仅可以节省空间,还可以更容易的使用到覆盖索引。
节省空间:
试想一下,索引的字段越多,是不是更容易满足查询需要返回的数据呢?比如联合索引(a,b,c)
是不是等于有了:a
、(a,b)
、(a,b,c)
三个索引,这样是不是节省了空间,当然节省的空间并不是三倍于a
、(a,b)
、(a,b,c)
三个索引所占用的空间,但是联合索引中data字段数据所占用的空间确实节省了不少。
联合索引的创建原则:
在创建联合索引的时候应该把频繁使用的列、区分度高的列放在前面,频繁使用代表索引利用率高,区分度高代表筛选力度大,这些都是在创建索引的时候需要考虑到的优化场景,也可以将常需要作为查询返回的字段增加到联合索引中。如果在联合索引上增加了一个字段,而恰好满足了使用覆盖索引的情况,这种情况建议使用联合索引。
联合索引的使用:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。