赞
踩
高效获取数据
的数据结构
,通俗点的说,数据库索引好比是一本书的目录,可以直接根据页码找到对应的内容,目的就是为了加快数据库的查询速度
。索引的存储原理可以概括为一句话:以空间换时间
一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往是存储在磁盘上的文件中的(可能存储在单独的索引文件中,也可能和数据一起存储在数据文件中)。
数据库在未添加索引进行查询的时候默认是进行全文搜索,也就是说有多少数据就进行多少次查询,然后找到相应的数据就把它们放到结果集中,直到全文扫描完毕。
xxxxxxxxxx
# (1) 创建表添加主键索引
CREATE TABLE `table_name` (
[...] ,
PRIMARY KEY (`col_name`),
)
# (2) 添加主键索引
ALTER TABLE `table_name` ADD PRIMARY KEY (`col_name`);
xxxxxxxxxx
# (1) 直接创建索引
CREATE INDEX index_name ON table_name(`col_name`);
# (2) 修改表结构的方式添加索引
ALTER TABLE `table_name` ADD INDEX index_name(`col_name`);
# (3) 创建表的时候同时创建索引
CREATE TABLE `table_name` (
[...] ,
PRIMARY KEY (`id`),
INDEX index_name (`col_name`)
)
# (4) 删除索引
DROP INDEX index_name ON table_name;
alter table `表名` drop index 索引名;
xxxxxxxxxx
# (1)创建一个复合索引
create index index_name on table_name(`col_name1`,`col_name2`,...);
# (2)修改表结构的方式添加索引
alter table table_name add index index_name(`col_name1`,`col_name2`,...);
唯一索引:唯一索引和普通索引类似,主要的区别在于,唯一索引限制列的值必须唯一,但允许存在空值(只允许存在一条空值)。
如果在已经有数据的表上添加唯一性索引的话:
xxxxxxxxxx
“空值” 和”NULL”的概念:
1:空值是不占用空间的 .
2: MySQL中的NULL其实是占用空间的.
长度验证:注意空值的之间是没有空格的。
> select length(''),length(null),length(' ');
+------------+--------------+-------------+
| length('') | length(null) | length(' ') |
+------------+--------------+-------------+
| 0 | NULL | 1 |
+------------+--------------+-------------+
xxxxxxxxxx
-- (1)创建唯一索引
# 创建单个索引
CREATE UNIQUE INDEX index_name ON table_name(`col_name`);
# 创建多个索引
CREATE UNIQUE INDEX index_name on table_name(`col_name`,...);
-- (2)修改表结构
# 单个
ALTER TABLE table_name ADD UNIQUE index index_name(`col_name`);
# 多个
ALTER TABLE table_name ADD UNIQUE index index_name(`col_name`,...);
-- (3)创建表的时候直接指定索引
CREATE TABLE `table_name` (
[...] ,
PRIMARY KEY (`id`),
UNIQUE index_name_unique(`col_name`)
)
xxxxxxxxxx
-- (1)创建表的适合添加全文索引
CREATE TABLE `table_name` (
[...] ,
PRIMARY KEY (`id`),
FULLTEXT (`col_name`)
)
-- (2)修改表结构添加全文索引
ALTER TABLE table_name ADD FULLTEXT index_fulltext_content(`col_name`)
-- (3)直接创建索引
CREATE FULLTEXT INDEX index_fulltext_content ON table_name(`col_name`)
注意:
xxxxxxxxxx
#查看:
show indexes from `表名`;
#或
show keys from `表名`;
#删除
alter table `表名` drop index 索引名;
优点:
缺点:
综合索引的优缺点:
数据库表中不是索引越多越好,而是仅为那些常用的搜索字段建立索引效果最佳!
MySQL索引使用的数据结构主要有BTree索引
和hash索引
。
对于hash索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景建议选择BTree索引。
Hash表,在Java中的HashMap,TreeMap就是Hash表结构,以键值对的形式存储数据。我们使用hash表存储表数据结构,Key可以存储索引列,Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高,时间复杂度为O(1);但是不支持范围快速查找,范围查找时只能通过扫描全表的方式,筛选出符合条件的数据。
显然这种方式,不适合我们经常需要查找和范围查找的数据库索引使用。
上面这个图就是我们常说的二叉树:每个节点最多有两个分叉节点,左子树和右子树数据按顺序左小右大。
二叉树的特点就是为了保证每次查找都可以进行折半查找,从而减少IO次数。
但是二叉树不是一直保持二叉平衡,因为二叉树很考验根节点的取值,因为很容易在某个节点下不分叉了,这样的话二叉树就不平衡了,也就没有了所谓的能进行折半查找了,如下图:
显然这种不稳定的情况,我们在选择存储数据结构的时候就会尽量避免这种的情况发生。
平衡二叉树采用的是二分法思维,平衡二叉查找树除了具备二叉树的特点,最主要的特征是树的左右两个子树的层级最多差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。
使用平衡二叉查找树查询的性能接近与二分查找,时间复杂度为O(log2n),查询id=6,只需要两次IO。
就上述平衡二叉树的特点来看,其实是我们理想的状态下,然而其实内部还是存在一些问题:
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树中查询数据的情况:
xxxxxxxxxx
假如我们要查询key等于10对应的数据data,根据上图我们可知在磁盘中的查询路径是:磁盘块1->磁盘块2->磁盘块6
xxxxxxxxxx
相比较二叉平衡查找树,在整个查找过程中,虽然数据的比较次数并没有明显减少,但是对于磁盘IO的次数会大大减少,同时,由于我们是在内存中进行的数据比较,所以比较数据所消耗的时间可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树构建索引可以很好的提升查询的效率。
过程如图:
看到上面的情况,觉得B树已经很理想了,但是其中还是存在可以优化的地方:
B+树,作为B树的升级版,MySQL在B树的基础上继续进行改造,使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。
B+树的大致数据结构:
xxxxxxxxxx
B+树的最底层叶子节点包含了所有的索引项。从图上可以看到,B+树在查找数据的时候,由于数据都存放在最底层的叶子节点上,所以每次查找都需要检索到叶子节点才能查询到数据。所以在需要查询数据的情况下每次的磁盘的IO跟树高有直接的关系,但是从另一方面来说,由于数据都被放到了叶子节点,所以放索引的磁盘块锁存放的索引数量是会跟这增加的,所以相对于B树来说,B+树的树高理论上情况下是比B树要矮的。也存在索引覆盖查询的情况,在索引中数据满足了当前查询语句所需要的全部数据,此时只需要找到索引即可立刻返回,不需要检索到最底层的叶子节点。
举例:等值查询
假如我们查询值等于9的数据。查询路径磁盘块1->磁盘块2->磁盘块6。
过程如图:
举例:范围查询
假如我们想要查找9和26之间的数据,查找路径为:磁盘块1->磁盘块2->磁盘块6->磁盘块7
可以看到B+树可以保证等值和范围查询的快速查找,MySQL的索引就采用了B+树的数据结构。
介绍完了索引数据结构,那肯定是要带入到Mysql里面看看真实的使用场景的,所以这里分析Mysql的两种存储引擎的索引实现:MyISAM索引和InnoDB索引
每个InnoDB表都有一个聚簇索引 ,聚簇索引使用B+树构建,叶子节点存储的数据是整行记录。一般情况下,聚簇索引等同于主键索引,当一个表没有创建主键索引时,InnoDB会自动创建一个ROWID字段来构建聚簇索引。
InnoDB创建索引的具体规则如下:
除聚簇索引之外的所有索引都称为辅助索引。在中InnoDB,辅助索引中的叶子节点存储的数据是该行的主键值都。 在检索时,InnoDB使用此主键值在聚簇索引中搜索行记录。
这里以user_innodb为例,user_innodb的id列为主键,age列为普通索引。
xxxxxxxxxx
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的数据组织方式,是聚簇索引。等值查询数据:
xxxxxxxxxx
select * from user_innodb where id = 28;
磁盘IO数量:3次。
除聚簇索引之外的所有索引都称为辅助索引,InnoDB的辅助索引只会存储主键值而非磁盘地址。
以表user_innodb的age列为例,age索引的索引结果如下图。
辅助索引等值查询的情况:
xxxxxxxxxx
select * from t_user_innodb where age=19;
根据在辅助索引树中获取的主键id,到主键索引树检索数据的过程称为回表查询。
磁盘IO数:辅助索引3次+获取记录回表3次
idx_abc(a,b,c)
。xxxxxxxxxx
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;
组合索引的数据结构:
组合索引的查询过程:
xxxxxxxxxx
select * from abc_innodb where a = 13 and b = 16 and c = 4;
最左前缀匹配原则和联合索引的索引存储结构和检索方式是有关系的。
在组合索引树中,最底层的叶子节点按照第一列a列从左到右递增排序,但是b列和c列是无序的,b列只有在a列值相等的情况下小范围内有序递增;而c列只能在a和b两列值相等的情况下小范围内有序递增。
就像上面的查询,B+ 树会先比较a列来确定下一步应该检索的方向,往左还是往右。如果a列相同再比较b列,但是如果查询条件中没有a列,B+树就不知道第一步应该从那个节点开始查起。
可以说创建的idx_(a,b,c)索引,相当于创建了(a)、(a,b)、(a,b,c)三个索引。
组合索引的最左前缀匹配原则:
xxxxxxxxxx
使用组合索引查询时,mysql会一直向右匹配直至遇到范围查询(>、<、between、like)等就会停止匹配。
覆盖索引并不是一种索引结构,覆盖索引是一种很常用的优化手段。因为在使用辅助索引的时候,我们只可以拿到相应的主键值,想要获取最终的数据记录,还需要根据主键通过主键索引再去检索,最终获取到符合条件的数据记录。
在上面的abc_innodb表中的组合索引查询时,如果我们查询的结果只需要a、b、c这三个字段,那我们使用这个idx_index(a,b,c)组合索引查询到叶子节点时就可以直接返回了,而不需要再次回表查询,这种情况就是覆盖索引。
未使用索引覆盖的情况:
索引覆盖的情况
以一个简单的user表为例。user表存在两个索引,id列为主键索引,age列为普通索引
xxxxxxxxxx
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+树构建索引树时,叶子节点中存储的键值为索引列的值,数据为索引所在行的磁盘地址。
主键ID列索引:
表user的索引存储在索引文件user.MYI
中,数据文件存储在数据文件 user.MYD
中。
简单分析下查询时的磁盘IO情况:
xxxxxxxxxx
select * from user where id = 28
磁盘IO次数:3次索引检索+记录数据检索。
根据主键范围查询数据:
xxxxxxxxxx
select * from user where id between 28 and 47;
磁盘IO次数:4次索引检索+记录数据检索。
在MyISAM存储引擎中,辅助索引和主键索引的结构是一样的,没有任何区别,叶子节点中data阈存储的都是行记录的磁盘地址。 主键列索引的键值是唯一的,而辅助索引的键值是可以重复的。
查询数据时,由于辅助索引的键值不唯一,可能存在多个拥有相同的记录,所以即使是等值查询,也需要按照范围查询的方式在辅助索引树种检索数据。
在InnoDB的存储引擎中,使用辅助索引查询的时候,因为辅助索引叶子节点保存的数据不是当前数据记录,而是当前数据记录的主键索引。如果需要获取当前记录完整的数据,就必须要再次根据主键从主键索引中继续检索查询,这个过程我们称之为回表查询。
由此可见,在数据量比较大的时候,回表必然会消耗很多的时间影响性能,所以我们要尽量避免回表的发生。
举例:
xxxxxxxxxx
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;
如果有一个场景:
xxxxxxxxxx
select id,name,sex from user where name = 'zhangsan';
这个语句在业务上频繁使用到,而user表中的其他字段使用频率远低于这几个字段,在这个情况下,如果我们在建立name字段的索引时,不是使用单一索引,而是使用联合索引(name,sex),这样的话再执行这个查询语句,根据这个辅助索引(name,sex)查询到的结果就包括了我们所需要的查询结果的所有字段的完整数据,这样就不需要再次回表查询去检索sex字段的数据了。
联合索引:
xxxxxxxxxx
在建立索引的时候,尽量在多个单列索引上判断下是否可以使用联合索引。联合索引的使用不仅可以节省空间,还可以更容易的使用到索引覆盖。
节省空间:
xxxxxxxxxx
试想一下,索引的字段越多,是不是更容易满足查询需要返回的数据呢。比如联合索引(a_b_c),是不是等于有了索引:a,a_b,a_b_c三个索引,这样是不是节省了空间,当然节省的空间并不是三倍于(a,a_b,a_b_c)三个索引,因为索引树的数据没变,但是索引data字段的数据确实真实的节省了。
联合索引的创建原则:
xxxxxxxxxx
在创建联合索引的时候因该把频繁使用的列、区分度高的列放在前面,频繁使用代表索引利用率高,区分度高代表筛选粒度大,这些都是在索引创建的需要考虑到的优化场景,也可以在常需要作为查询返回的字段上增加到联合索引中。
xxxxxxxxxx
如果在联合索引上增加一个字段而使用到了覆盖索引,那建议这种情况下使用联合索引。
联合索引的使用:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。