1. 索引介绍
索引 : 是排序的快速查找的特殊数据结构 , 定义作为查找条件的字段上 , 又称为键key , 索引通过存储引擎实现
索引的存储原理大致可以概括为一句话 : 以空间换时间。
一般来说索引本身也很大 , 不可能全部存储在内存中 , 因此索引往往是存储在磁盘上的文件中的(可能存储在单独的索引文件中 , 也可能和数据一起存储在数据文件中)。
数据库在未添加索引进行查询的时候默认是进行全文搜索 , 也就是说有多少数据就进行多少次查询 , 然后找到相应的数据就把它们放到结果集中 , 直到全文扫描完毕。
建立索引时 , 需要确保该索引应用在SQL查询语句的条件(一般作为WHERE子句的条件)。索引也是一张表 , 该表保存了主键与索引字段 , 并指向实体表的记录。然而 , 过多的使用索引将会造成滥用。虽然索引大大提高了查询速度 , 同时却会降低更新表的速度, 如对表进行INSERT、UPDATE和DELETE。因为更新表时 , MySQL不仅要保存数据 , 还要保存一下索引文件。建立索引会占用磁盘空间的索引文件。
MySQL查询优化器会优化and连接 , 将组合索引列规则排号。在MySQL建立联合索引时会遵守最左前缀匹配原则,即最左优先(查询条件精确匹配索引的左边连续一列或几列 , 则构建对应列的组合索引树) , 在检索数据时也从联合索引的最左边开始匹配。
MySQL 5.6以前的版本 , 只有MyISAM存储引擎支持全文索引 ; MySQL 5.6及以后的版本 , MyISAM和InnoDB存储引擎均支持全文索引 ; 只有字段的数据类型为char、varchar、text及其系列才可以建全文索引。InnoDB内部并不支持中文、日文等 , 因为这些语言没有分隔符。可以使用插件辅助实现中文、日文等的全文索引。
优点
索引大大减小了服务器需要扫描的数据量 , 从而大大加快数据的检索速度 , 这也是创建索引的最主要的原因。
通过索引列对数据进行排序 , 降低数据的排序成本降低了
CPU的消耗。被索引的列会自动进行排序 , 包括单例索引和组合索引 , 只是组合索引的排序需要复杂一些。
索引可以将随机
IO变成顺序IO索引对于
InnoDB(对索引支持行级锁)非常重要 , 因为它可以让查询锁更少的元组 , 提高了表访问并发性关于
InnoDB、索引和锁 :InnoDB在二级索引上使用共享锁(读锁) , 但访问主键索引需要排他锁(写锁)通过创建唯一性索引 , 可以保证数据库表中每一行数据的唯一性。
可以加速表和表之间的连接 , 特别是在实现数据的参考完整性方面特别有意义。
在使用分组和排序子句进行数据检索时 , 同样可以显著减少查询中分组和排序的时间。
通过使用索引 , 可以在查询的过程中 , 使用优化隐藏器 , 提高系统的性能。
缺点
创建索引和维护索引要耗费时间 , 这种时间随着数据量的增加而增加
索引需要占物理空间 ,除了数据表占用数据空间之外 , 每一个索引还要占用一定的物理空间 , 如果需要建立聚簇索引 , 那么需要占用的空间会更大
对表中的数据进行增、删、改的时候 , 索引也要动态的维护 , 这就降低了整数的维护速度
如果某个数据列包含许多重复的内容 , 为它建立索引就没有太大的实际效果。
对于非常小的表 , 大部分情况下简单的全表扫描更高效；
2. 索引分类
索引类型 :
B+ TREE、HASH、R TREE、FULL TEXT聚簇(集)索引、非聚簇索引 : 数据和索引是否存储在一起
主键索引、二级(辅助)索引
稠密索引、稀疏索引 : 是否索引了每一个数据项
简单索引、组合索引
左前缀索引 : 取前面的字符做索引
覆盖索引 : 从索引中即可取出要查询的数据 , 性能高
MySQL索引是对数据库表中一列或多列的值进行排序的一种结构 , 可以大大提高MySQL的检索速度。索引分为单列索引和组合索引 , 其中单列索引只包含单个列 , 一个表可以有多个单列索引, 但这不是组合索引。组合索引是一个索引包含多个列。
MySQL的索引有两种分类方式 : 逻辑分类和物理分类。逻辑分类是根据索引的数据结构分类 , 如B-TREE、HASH等。物理分类是根据索引的存储方式分类 , 如聚簇索引、非聚簇索引等。聚簇索引是将数据存储与索引一起,它的叶子节点存储的是整行数据 , 因此它只能有一个 , 而且必须是主键索引。非聚簇索引是将数据存储与索引分开 , 索引的叶子节点存储的是指向数据行的指针, 可以有多个。
逻辑分类 : 有多种逻辑划分的方式 , 比如按功能划分 , 按组成索引的列数划分等
按功能划分
主键索引(
primary key) : 一张表只能有一个主键索引 , 不允许重复、不允许为NULL;ALTER TABLE TableName ADD PRIMARY KEY(column_list);唯一索引 : 数据列不允许重复 , 允许为
NULL值 , 一张表可有多个唯一索引 , 索引列的值必须唯一 ,但允许有空值。如果是组合索引 , 则列值的组合必须唯一。CREATE UNIQUE INDEX IndexName ON `TableName`(`字段名`(length)); # 或者 ALTER TABLE TableName ADD UNIQUE (column_list);普通索引 : 一张表可以创建多个普通索引 , 一个普通索引可以包含多个字段 , 允许数据重复 , 允许
NULL值插入 ;CREATE INDEX IndexName ON `TableName`(`字段名`(length)); # 或者 ALTER TABLE TableName ADD INDEX IndexName(`字段名`(length));全文索引(
fulltext) : 它查找的是文本中的关键词 , 主要用于全文检索。
按列个数分类
单列索引 : 一个索引只包含一个列 , 一个表可以有多个单例索引。
组合索引 : 一个组合索引包含两个或两个以上的列。查询的时候遵循
mysql组合索引的"最左前缀"原则 , 即使用where时条件要按照建立索引的时候字段的排列方式放置索引才会生效。
其他类型
空间索引 :
MySQL在5.7之后的版本支持了空间索引 , 而且支持OpenGIS几何数据模型 ,MySQL在空间索引这方年遵循OpenGIS几何数据模型规则。前缀索引 : 在文本类型为
char、varchar、text类列上创建索引时 , 可以指定索引列的长度 , 但是数值类型不能指定。
物理分类 :分为聚簇索引和非聚簇索引 ( 有时也称辅助索引或二级索引 )
聚簇是为了提高某个属性(或属性组)的查询速度 , 把这个或这些属性(称为聚簇码)上具有相同值的元组集中存放在连续的物理块。
聚簇索引 : 聚簇索引(
clustered index)不是单独的一种索引类型 , 而是一种数据存储方式。这种存储方式是依靠B+树来实现的 , 根据表的主键构造一棵B+树且B+树叶子节点存放的都是表的行记录数据时 ,方可称该主键索引为聚簇索引。聚簇索引也可理解为将数据存储与索引放到了一块 , 找到索引也就找到了数据。非聚簇索引 : 数据和索引是分开的 ,
B+树叶子节点存放的不是数据表的行记录。
虽然
InnoDB和MyISAM存储引擎都默认使用B+树结构存储索引 , 但是只有InnoDB的主键索引才是聚簇索引 ,InnoDB中的辅助索引以及MyISAM使用的都是非聚簇索引。每张表最多只能拥有一个聚簇索引。数据结构分类 :
B-Tree索引、B+tree索引、Hash索引、Full-text索引
2.1 Hash索引
Hash索引 : 基于哈希表实现 , 只有精确匹配索引中的所有列的查询才有效 , 索引自身只存储索引列对 应的哈希值和数据指针 , 索引结构紧凑 , 查询性能好
Memory存储引擎支持显式hash索引 , InnoDB和MyISAM存储引擎不支持
适用场景 : 只支持等值比较查询 , 包括=,<=>,IN()
不适合使用hash索引的场景
不适用于顺序查询 : 索引存储顺序的不是值的顺序
不支持模糊匹配 不支持范围查询
不支持部分索引列匹配查找 : 如
A,B列索引 , 只查询A列索引无效
2.2 空间数据索引
R-Tree(Geospatial indexing ) MyISAM支持地理空间索引 , 可使用任意维度组合查询 , 使用特有的函数访问 ,常用于做地理数据存储 , 使用不多InnoDB从MySQL5.7之后也开始支持。
R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子吧 : 查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中 , 一个字段记录经度 , 另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息 , 然后计算是否满足要求。如果一个地区有100家餐厅的话 , 我们就要进行100次位置计算操作了 , 如果应用到谷歌地图这种超大数据库中 , 我想这种方法肯定不可行吧。
R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间 , 采用了B树分割空间的思想 , 并在添加、删除操作时采用合并、分解结点的方法 , 保证树的平衡性。因此 , R树就是一棵用来存储高维数据的平衡树。
2.3 全文索引
全文索引(FULLTEXT) 在文本中查找关键词 , 而不是直接比较索引中的值 , 类似搜索引擎InnoDB从MySQL 5.6之后也开始支持。
在当我们进行模糊查询的时候, 一般都是使用 like 关键字来实现 , 在数据量小的情况下效率确实可以。有的人会说了 ,数据量大的时候我加索引啊。确实可以加索引 , 而且 like name% 是可以使用到索引的, 但是当你要 like %name% 这样使用就会导致索引无效。在某些情况下就造成了局限性。
在数据量大的情况下 , 全文索引的效率会比like高 , 在MySql5.6版本以前 , 只有MyISAM索引支持全文索引 , 在这之后Innodb也支持。
2.3.1 全文索引创建和使用
//创建全文索引
CREATE FULLTEXT INDEX <index_name> on tableName(字段名)
ALTER TABLE tableName ADD FULLTEXT[index_name](字段名);
CREATE TABLE tableName([....],FULLTEXT KEY[index_name](字段名))和常用的like不同 , 全文索引有自己的格式 , 使用match和against关键字 , 如下 :
select * from user where match(name) against('aaa');2.3.2 全文索引实战
创建一张用户表people , 主键ID和用户名name
//插入四条记录
insert into people (`name`) VALUES ('a');
insert into people (`name`) VALUES ('aa');
insert into people (`name`) VALUES ('aaa');
insert into people (`name`) VALUES ('aaaa');
//在字段name上建立全文索引
create fulltext index name_index_ft on people(name);
//开始查询
// 分别执行下面这4条SQL
select * from people where match(name) against('a'); // 没记录
select * from people where match(name) against('aa'); // 没记录
select * from people where match(name) against('aaa'); // 1条记录
select * from people where match(name) against('aaaa'); // 1条记录很多人可能会问 , 为什么我数据库有name = a 和name = aa的记录 , 为什么会找不到 , 而且全文索引不是跟like一样可以模糊查询的吗？？当我执行 select * from people where match(name) against('aaa'); 应该有二条记录啊 , 为什么只有一条??,接下来就要去了解全文的原理了
2.3.3 全文索引原理
在MySql客户端执行 show variables like '%ft%'; 查看全文索引的信息
为什么在查询 a 和 aa的时候会没有记录
先解释下其中几个参数
ft_min_word_len: 针对MyISAM引擎的 , 也就是在你创建的全文索引的字段的内容最小长度ft_max_word_len: 针对MyISAM引擎的 , 也就是在你创建的全文索引的字段的内容最大长度 也就是说 , 只有在内容长度为4 ~ 84(图中数值)的时候 , 你的全文索引才会有效,但是我们使用的Innodb存储引擎 , 所以你要看的是这二项。innodb_ft_min_token_size: 针对Innodb引擎的 , 也就是在你创建的全文索引的字段的内容最小长度innodb_ft_max_token_size: 针对Innodb引擎的 , 也就是在你创建的全文索引的字段的内容最大长度
也就是说你的全文索引字段的内容长度必须在3 ~ 84之间才会有效 , 现在能明白为什么在查 a 和aa的时候找不到记录 , 但是在查aaa 的时候就会有记录了吧 , 因为aaa长度刚好等于3
为什么在查询aaa的时候 , name = aaaa的记录找不到
在全文索引底层是有一个切词的概念的 , 比如 祝中国越来越强大 全文索引按照一个规则切词 , 有可能会被切成 祝 、 中国、 越来越强大。那么切词的依据是什么呢? 全文索引又是怎么切词的呢??
在这里有个很重要的参数 : ft_boolean_syntax , 就是第一项 , 改变IN BOOLEAN MODE的查询字符 , 不用重新启动MySQL也不用重建索引。 后面有很多内容 , 全文索引就是按照这些来切词的。现在表的记录如下:
将记录更新如下:
现在我们再来执行
select * from people where match(name) against('aaa');
现在就能把所有的记录都找出来了吧,但是细心的你会发现 , id = 6的这条记录还是没找出来 , 这是为什么？？
全文索引为什么默认不支持模糊查询
为什么是默认呢 , 因为至少到现在我们发现全文索引都是 等值查询 的 , 这是因为全文索引默认支持的就是等值查询 , 如果要支持模糊查询需要改写SQL如下 :
select * from people where match(name) against('aaa*' in boolean mode);
现在就可以把所有符合的数据都查出来了 , *表示一个或多个字符
2.4 聚簇索引, 非聚簇索引 , 主键和二级索引
聚簇索引 :
聚簇索引就是按照每张表的主键构造一颗B+树 , 同时叶子节点中存放的就是整张表的行记录数据 , 也将聚簇索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分 , 每张表只能拥有一个聚簇索引
InnoDB通过主键聚集数据 , 如果没有定义主键 ,InnoDB会选择非空的唯一索引代替。如果没有这样的索引 ,InnoDB会隐式定义一个主键来作为聚簇索引。将数据存储和索引放到了一块 , 找到了索引也就找到了数据
一般情况下主键会默认创建聚簇索引。
辅助索引(非聚簇索引)
在聚集索引之上创建的索引叫做辅助索引
辅助索引访问数据总是需要二次查找第一次找到主键值 , 第二次根据主键值找到行数据。
辅助索引叶子节点存储的不再是行的物理位置 , 而是主键值。
通过辅助索引首先找到的是主键值 , 再通过主键值找到数据行的数据页 , 再通过数据页中的
Page Directory找到数据行。
辅助索引的存储不影响数据在聚簇索引中的组织 , 所以一张表可以由多个辅助索引。在
innodb中有时也称辅助索引为二级索引。将数据存储于索引分开结构 , 索引结构的叶子节点指向了数据的对应行。
MyISAM通过key_buffer把索引先缓存到了内存中 , 当需要访问数据时(通过索引访问数据) , 在内存中直接查找索引 , 然后通过索引找到磁盘相应数据。这也就是为什么索引不在key buffer命中时 , 速度慢的原因。
聚集索引⼀个表只能有⼀个 , 而非聚集索引⼀个表可以存在多个。聚集索引存储记录是物理上连续存在 ,而非聚集索引是逻辑上的连续 , 物理存储并不连续。
澄清一个概念 :
InnoDB中 , 在聚集索引上创建的索引叫做辅助索引辅助索引访问数据总是需要二次查找 , 非聚簇索引都是辅助索引 , 像复合索引、前缀索引、唯一索引、辅助引擎叶子节点存储的不再是行的物理位置 , 而是主键值。
聚簇索引默认是主键 , 如果表中没有定义主键 , InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引 , InnoDB会隐式定义一个主键来作为聚簇索引。InnoDB只聚集在同一个页面中的记录。包含相邻键值的页面可能相距甚远。如果你已经设置了主键为聚簇索引 , 必须先删除主键 , 然后添加我们想要的聚簇索引 , 最后恢复设置主键即可。
此时其他索引只能被定义为非聚簇索引。这个是最大的误区。有的主键还是无意义的自动增量字段 , 那样的话Clustered index对效率的帮助 , 完全被浪费了。
刚才说到了 , 聚簇索引性能最好而且具有唯一性 , 所以非常珍贵 , 必须慎重设置。一般要根据这个表最常用的SQL查询方式来进行选择 , 某个字段作为聚簇索引 , 或组合聚簇索引 , 这个要看实际情况。
记住我们的最终目的就是在相同结果集情况下 , 尽可能减少逻辑IO。
结合图再仔细点看
InnoDB使用的是聚簇索引 , 将主键组织到一棵B+树中 , 而行数据就储存在叶子节点上 , 若使用"where id = 14"这样的条件查找主键 , 则按照B+树的检索算法即可查找到对应的叶节点 , 之后获得行数据。若对
Name列进行条件搜索 , 则需要两个步骤 :第一步在辅助索引
B+树中检索Name, 到达其叶子节点获取对应的主键。第二步使用主键在主索引
B+树种再执行一次B+树检索操作 , 最终到达叶子节点即可获取整行数据。(重点在于通过其他键需要建立辅助索引)
MyISM使用的是非聚簇索引 , 非聚簇索引的两棵B+树看上去没什么不同 , 节点的结构完全一致只是存储的内容不同而已 , 主键索引B+树的节点存储了主键 , 辅助键索引B+树存储了辅助键。表数据存储在独立的地方 , 这两颗B+树的叶子节点都使用一个地址指向真正的表数据 , 对于表数据来说 , 这两个键没有任何差别。由于索引树是独立的 , 通过辅助键检索无需访问主键的索引树。
聚簇索引的优势
看上去聚簇索引的效率明显要低于非聚簇索引 , 因为每次使用辅助索引检索都要经过两次B+树查找 , 这不是多此一举吗 ? 聚簇索引的优势在哪？
由于行数据和叶子节点存储在一起 , 同一页中会有多条行数据 , 访问同一数据页不同行记录时 , 已经把页加载到了
Buffer中 , 再次访问的时候 , 会在内存中完成访问 , 不必访问磁盘。这样主键和行数据是一起被载入内存的 , 找到叶子节点就可以立刻将行数据返回了, 如果按照主键Id来组织数据 , 获得数据更快。辅助索引使用主键作为"指针"而不是使用地址值作为指针的好处是 , 减少了当出现行移动或者数据页分裂时辅助索引的维护工作 , 使用主键值当作指针会让辅助索引占用更多的空间 , 换来的好处是
InnoDB在移动行时无须更新辅助索引中的这个"指针"。也就是说行的位置 ( 实现中通过16K的Page来定位 ) 会随着数据库里数据的修改而发生变化 ( 前面的B+树节点分裂以及Page的分裂 ) , 使用聚簇索引就可以保证不管这个主键B+树的节点如何变化 , 辅助索引树都不受影响。聚簇索引适合用在排序的场合, 非聚簇索引不适合
取出一定范围数据的时候 , 使用聚簇索引
二级索引需要两次索引查找 , 而不是一次才能取到数据 , 因为存储引擎第一次需要通过二级索引找到索引的叶子节点 , 从而找到数据的主键 , 然后在聚簇索引中用主键再次查找索引 , 再找到数据
可以把相关数据保存在一起。例如实现电子邮箱时 , 可以根据用户 ID 来聚集数据 , 这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如果没有使用聚簇索引 , 则每封邮件都可能导致一次磁盘 I/O。
聚簇索引的劣势
维护索引很昂贵 , 特别是插入新行或者主键被更新导至要分页(page split)的时候。建议在大量插入新行后 , 选在负载较低的时间段 , 通过
OPTIMIZE TABLE优化表 , 因为必须被移动的行数据可能造成碎片。使用独享表空间可以弱化碎片表因为使用
UUID(随机ID)作为主键 , 使数据存储稀疏 , 这就会出现聚簇索引有可能有比全表扫面更慢。
所以建议使用
int的auto_increment作为主键
主键的值是顺序的 , 所以
InnoDB把每一条记录都存储在上一条记录的后面。当达到页的最大填充因子时(InnoDB默认的最大填充因子是页大小的15/16, 留出部分空间用于以后修改) , 下一条记录就会写入新的页中。一旦数据按照这种顺序的方式加载 , 主键页就会近似于被顺序的记录填满(二级索引页可能是不一样的)。如果主键比较大的话 , 那辅助索引将会变的更大 , 因为辅助索引的叶子存储的是主键值；过长的主键值 , 会导致非叶子节点占用占用更多的物理空间
为什么主键通常建议使用自增id
聚簇索引的数据的物理存放顺序与索引顺序是一致的 , 即 : 只要索引是相邻的 , 那么对应的数据一定也是相邻地存放在磁盘上的。如果主键不是自增id , 那么可以想象它会干些什么 , 不断地调整数据的物理地址、分页 , 当然也有其他一些措施来减少这些操作 , 但却无法彻底避免。但如果是自增的那就简单了 , 它只需要一页一页地写 , 索引结构相对紧凑 , 磁盘碎片少 , 效率也高。
因为MyISAM的主索引并非聚簇索引 , 那么他的数据的物理地址必然是凌乱的 , 拿到这些物理地址 , 按照合适的算法进行I/O读取 , 于是开始不停的寻道不停的旋转。聚簇索引则只需一次I/O。 ( 强烈的对比 )
不过 , 如果涉及到大数据量的排序、全表扫描、count之类的操作的话 , 还是MyISAM占优势些 , 因为索引所占空间小 , 这些操作是需要在内存中完成的。
mysql中聚簇索引的设定
聚簇索引默认是主键 , 如果表中没有定义主键 , InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引 , InnoDB会隐式定义一个主键来作为聚簇索引。InnoDB只聚集在同一个页面中的记录。包含相邻健值的页面可能相距甚远。
2.5 冗余索引,重复索引
MySQL是允许在相同列上创建多个索引 , 无论你创建的时候是有意的还是无意的。MySQL需要单独维护重复的索引 , 并且优化器在优化查询的时候也需要进行逐个考虑 , 这回影响性能。
重复索引 : 就是指在相同的列上按照相同的顺序创建的相同类型的索引。应该避免这样的创建 , 发现之后也应该立即移除。已经有索引 , 再次建立索引。
冗余索引和重复索引其实又有一些不同。如果创建了索引(A,B) , 再创建索引(A)那就是冗余索引了 , 因为这只是前一个索引的前缀索引。但是你要是创建的是(B,A)那可就不是冗余索引了。当然不同的索引类型肯定也不会涉及到冗余索引的事情。
还有一种情况 , 将索引(A)扩展为了索引(A , ID) , 其中ID是主键 , 这在innodb中来说 , 主键列已经包含到二级索引中去了 , 所以这也是冗余索引。
大多数情况下 , 我们不应该是创建新索引 , 而是扩展已有的索引。但你话也不能说死 , 有时候出于性能的考虑 , 也会考虑冗余索引 , 因为你扩展索引会导致其变得太大 , 从而影响其他使用该索引的查询的性能。
3 索引结构
3.1 二叉树
二叉查找树(BST , Binary Search Tree) , 也叫二叉排序树。在二叉树的基础上需要满足 :任意节点的左子树上所有节点值不大于根节点的值 , 任意节点的右子树上所有节点值不小于根节点的值。
如果先查二叉树的话 , 由于我们的数据量庞大 , 二叉树的深度会变得非常大 , 我们的索引树会变成参天大树 , 每次查询会导致很多磁盘IO。
对于二叉树而言 , 每个节点只能有两个子节点 , 如果是一颗单边二叉树 , 查询某个节点的次数与节点所处的高度相同 , 时间复杂度为O(n) ; 如果是一颗平衡二叉树 , 查找效率高出一半 , 时间复杂度为O(Log2n)。
并且二叉树还有另一个坏处 , 二叉树上的每一个节点都是数据节点 , 那么对于一个比较高的数如果要获取最下面的数据遍历的节点数将会很消耗性能。
3.2 红黑树
红黑树 : 当单边的节点大于3时候 , 就会自动调整 , 这样可以解决二叉树的弊端 ;
平衡二叉查找树 : 简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis在 1962 年提出的高度平衡的二叉树 , 根据科学家的英文名也称为 AVL 树。它具有如下几个性质 :
可以是空树。
假如不是空树 , 任何一个结点的左子树与右子树都是平衡二叉树 , 并且高度之差的绝对值不超过 1。
平衡之意 , 如天平 , 即两边的分量大约相同。
平衡因子 : 某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子(BF,Balance Factor) , ,平衡二叉树中不存在平衡因子大于 1 的节点。
当然 , 红黑树也有弊端的 , 当数据量特别大的时候 , 红黑树的高度特别大 ; 假如有500W条数据 ,则红黑树高度为 23 , 若我们要查找的刚好是红黑树的叶子节点 , 则需要查找23次才可以 , 即要发生23次的磁盘I/O操作 , 性能就太差了 ;
红黑树首先肯定是一个排序二叉树 , 它在每个节点上增加了一个存储位来表示节点的颜色 , 可以是RED或BLACK 。
性质1 : 每个节点要么是红色 , 要么是黑色。
性质2 : 根节点永远是黑色的。
性质3 : 所有的叶子节点都是空节点(即
null) , 并且是黑色的。性质4 : 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点。)
性质5 : 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
3.3 B-Tree索引
B树是一种自平衡树数据结构 , 它维护有序数据并允许以O(lgn)时间进行搜索 , 顺序访问、插入和删除。B树是二叉搜索树的一般化 , 因为节点可以有两个以上的子节点 , 并且每个节点可以有多个键值 , 这些属性减少了定位记录时所经历的中间过程 , 加快了存取速度。与其他自平衡二进制搜索树不同 , B树非常适合读取和写入相对较大的数据块(如光盘)的存储系统。它通常用于数据库和文件系统。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树 , 或者是满足下列性质的树 :
根结点至少有两个子女;
根结点的儿子数为
[2, M]；除根结点以外的其他非叶子结点的儿子数为
[M/2, M]；每个结点中的关键字都按照从小到大的顺序排列 , 每个关键字的左子树中的所有关键字都小于它 , 而右子树中的所有关键字都大于它。
有
j个孩子的非叶子节点恰好有j-1个关键字,关键字按递增次序排序每个非根节点所包含的关键字个数
j满足 :Math.ceil(m/2) <= j <= m-1;所有叶子结点都位于同一层 , 或者说根结点到每个叶子结点的长度都相同。B树的叶子节点可以看成一种外部节点, 不包含任何信息。
注 :
Math.ceil(m/2):表示向上取整 ,Math.ceil(5/2)=3。
如 : ( M=3 )
B-树的搜索 , 从根结点开始 , 对结点内的关键字(有序)序列进行二分查找 , 如果命中则结束 , 否则进入查询关键字所属范围的儿子结点；重复 , 直到所对应的儿子指针为空 , 或已经是叶子结点 ;
B-树的特性 :
关键字集合分布在整颗树中 ;
任何一个关键字出现且只出现在一个结点中 ;
搜索有可能在非叶子结点结束；
其搜索性能等价于在关键字全集内做一次二分查找；
自动层次控制;
由于限制了除根结点以外的非叶子结点 , 至少含有M/2个儿子 , 确保了结点的至少利用率 , 其最底搜索性能为 : O(logN)
所以B-树的性能总是等价于二分查找(与M值无关) , 也就没有B树平衡的问题;
由于M/2的限制 , 在插入结点时 , 如果结点已满 , 需要将结点分裂为两个各占M/2的结点 ; 删除结点时 , 需将两个不足M/2的兄弟结点合并 ;
B树数据结构大致如下 :
举个简单的例子 , 在B树中查询数据的情况 :
假如我们要查询
key等于10对应的数据data, 根据上图我们可知在磁盘中的查询路径是 : 磁盘块1->磁盘块2->磁盘块6
第一次磁盘
IO: 将磁盘块1加载到内存中 , 在内存中从头遍历比较 ,10<15, 走左子树 , 到磁盘中寻址到磁盘块2。第二次磁盘
IO: 将磁盘块2加载到内存中 , 在内存中从头遍历比较 ,10>7, 走右子树 , 到磁盘中寻址到磁盘块6。第三次磁盘
IO: 讲磁盘块6加载到内存中 , 在内存中从头遍历比较 ,10=10, 找到key=10的位置 , 取出对应的数据data, 如果data存储的是行记录 , 直接取出数据 , 查询结束 ; 如果data存储的是行磁盘地址 , 还需要根据磁盘地址到对应的磁盘中取出数据 , 查询结束。
相比较二叉平衡查找树 , 在整个查找过程中 , 虽然数据的比较次数并没有明显减少 , 但是对于磁盘
IO的次数会大大减少。同时由于我们是在内存中进行的数据比较 , 所以比较数据所消耗的时间可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景 , 所以使用B树构建索引可以很好的提升查询的效率。
过程如下图所示:
看到上面的情况 , 觉得B树已经很理想了 , 但是其中还是存在可以优化的地方 :
B树不支持范围查询的快速查找 , 例如 : 仍然根据上图 , 我们想要查询10到35之间的数据 , 查找到10之后 , 需要回到根节点重新遍历查找 , 需要从根节点进行多次遍历 , 查询效率有待提高。如果
data存储的是行记录 , 行的大小随着列数的增加 , 所占空间会变大 , 这时一页中可存储的数据量就会减少 , 树相应就会变高 , 磁盘IO次数就会随之增加 , 有待优化。
3.4 B+Tree索引
为了实现动态多层索引 , 通常采用 B-树 和 B+树。但是 , 用于索引的 B-树存在缺陷 , 它的所有中间结点均存储的是数据指针(指向包含键值的磁盘文件块的指针) , 与该键值一起存储在B-树的结点中。这就会导致可以存储在 B-树中的结点目数极大地减少了 , 从而增加 B-树的层数 , 进而增加了记录的搜索时间。
B+Tree是在B-Tree基础上的一种优化 , 使其更适合实现外存储索引结构 , InnoDB存储引擎就是用B+Tree实现其索引结构。
B+树通过仅在树的叶子结点中存储数据指针而消除了上述缺陷。因此 , B+树的叶结点的结构与 B-树的内部结点的结构完全不同。在这里应该注意 , 由于数据指针仅存在于叶子结点中 , 因此叶子结点必须将所有键值及其对应的数据指针存储到磁盘文件块以便访问。此外 , 叶子结点被链接磁盘的某个位置 , 以提供对记录的有序访问。因此 , 叶子结点形成第一级索引 , 而内部结点形成多层索引的其他层。叶子结点的某些关键字key也出现在内部结点中 , 充当控制搜索记录的媒介。
B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于:
有
n棵子树的结点中含有n个关键字 , 每个关键字不保存数据 , 只用来索引 , 所有数据都保存在叶子节点。所有的叶子结点中包含了全部关键字的信息 , 及指向含这些关键字记录的指针 , 且叶子结点本身依关键字的大小自小而大顺序链接。
所有的非终端结点可以看成是索引部分 , 结点中仅含其子树(根结点)中的最大(或最小)关键字。
一棵m阶的B+树主要有这些特点:
每个结点至多有
m个子女;非根节点关键值个数范围 :
Math.ceil(m/2) <= j <= m-1相邻叶子节点是通过指针连起来的 , 并且是关键字大小排序的。
可以使用B+Tree索引的查询类型 :
全值匹配 : 精确所有索引列 , 如 : 姓
wang, 名xiaochun, 年龄30匹配最左前缀 : 即只使用索引的第一列 , 如 : 姓
wang匹配列前缀 : 只匹配一列值开头部分 , 如 : 姓以
w开头的匹配范围值 : 如 , 姓
ma和姓wang之间精确匹配某一列并范围匹配另一列 : 如 , 姓
wang,名以x开头的, 只访问索引的查询
B+Tree索引的限制 :
如不从最左列开始 , 则无法使用索引 , 如 : 查找名为
xiaochun, 或姓为g结尾不能跳过索引中的列 , 如 : 查找姓
wang, 年龄30的 , 只能使用索引第一列
特别提示 : 索引列的顺序和查询语句的写法应相匹配 ,才能更好的利用索引 为优化性能 , 可能需要针对相同的列但顺序不同创建不同的索引来满足不同类型的查询需求。
B+树的大致数据结构:
B+树的最底层叶子节点包含了所有的索引项。从上图可以看出 ,B+树在查找数据的时候 , 由于数据都存放在最底层的叶子节点上 , 所以每次查找都需要检索到叶子节点才能查询到数据。所以在查询数据的情况下每次的磁盘IO次数跟树的高度有直接的关系 ; 但是从另一方面来说 , 由于数据都被存放到了叶子节点 , 所以存放索引的磁盘块 , 所存放的的索引数量会随之增加 , 所以相对于B树来说 ,B+树的树高理论情况下是比B树树高要矮的。 但是也存在索引覆盖查询的情况 , 在索引中数据满足了查询语句所需要的全部数据, 此时只需要找到索引即可立刻返回 , 不需要检索到最底层的叶子节点。
等值查询实例 :
假如我们要查询key为9对应的数据data , 查询路径为 : 磁盘块1->磁盘块2->磁盘块6。
第一次磁盘
IO: 将磁盘块1加载到内存中 , 在内存中从头遍历比较 ,9<15, 走左子树 , 到磁盘寻址定位到磁盘块2。第二次磁盘
IO: 将磁盘块2加载到内存中 , 在内存中从头遍历比较 ,7<9<12, 到磁盘中寻址定位到磁盘块6。第三次磁盘
IO: 将磁盘块6加载到内存中 , 在内存中从头遍历比较 , 在第三个索引中找到9, 取出对应的数据data, 如果data存储的是行记录 , 直接取出data, 查询结束 ; 如果存储的是磁盘地址 , 还需要根据磁盘地址再次寻址定位到指定磁盘取出数据 , 查询终止。
范围查询实例 :
假如我们想要查找9和26之间的数据 , 查找路径为 : 磁盘块1->磁盘块2->磁盘块6->磁盘块7
前三次磁盘
IO: 首先查找到键值为9对应的数据(定位到磁盘块6) , 然后缓存大结果集中。这一步和前面等值查询流程一样 , 发生了三次磁盘IO。继续查询 , 查找到节点
15之后 , 底层的所有叶子节点是一个有序列表 , 我们从磁盘块6中的键值9开始向后遍历筛选出所有符合条件的数据。第四次磁盘
IO: 根据磁盘块6的后继指针到磁盘中寻址定位到磁盘块7, 将磁盘块7加载到内存中 , 在内存中从头遍历比较,9<25<26,9<26<=26, 将数据data缓存到结果集中。逐渐具备唯一性(后面不会再有
<=26的数据) , 不需要再向后查找 , 查询结束 , 将结果集返回给用户。
由上述实例可知 : B+树可以保证等值和范围查询的快速查找 , MySQL的索引采用的就是B+树的结构。
4 索引优化
独立地使用列 : 尽量避免其参与运算 , 独立的列指索引列不能是表达式的一部分 , 也不能是函数的参数 , 在
where条件中 , 始终将索引列单独放在比较符号的一侧 , 尽量不要在列上进行运算(函数操作和表达式操作)左前缀索引 : 构建指定索引字段的左侧的字符数 , 要通过索引选择性( 不重复的索引值和数据表的记录总数的比值 )来评估 , 尽量使用短索引 , 如果可以 , 应该制定一个前缀长度
多列索引 :
AND操作时更适合使用多列索引 , 而非为每个列创建单独的索引选择合适的索引列顺序 : 无排序和分组时 ,将选择性最高放左侧
只要列中含有
NULL值 , 就最好不要在此列设置索引 , 复合索引如果有NULL值 , 此列在使用时也 不会使用索引对于经常在
where子句使用的列 , 最好设置索引对于有多个列
where或者order by子句 , 应该建立复合索引对于
like语句 , 以%或者_开头的不会使用索引 , 以%结尾会使用索引尽量不要使用
not in和<>操作, 虽然可能使用索引 , 但性能不高不要使用
RLIKE正则表达式会导致索引失效查询时 , 能不要
*就不用*,尽量写全字段名 , 比如:select id,name,age from students;大部分情况连接效率远大于子查询
在有大量记录的表分页时使用limit
对于经常使用的查询 , 可以开启查询缓存
多使用
explain和profile分析查询语句查看慢查询日志 , 找出执行时间长的
sql语句优化
5 管理索引
5.1 基础用法
创建索引 :
创建数据库时创建索引
CREATE TABLE table_name[col_name data type] [unique|fulltext][index|key][index_name](col_name[length])[asc|desc] create table 表名( 字段名1 字段类型1, 字段名2 字段类型2, ....., spatial [index|key] [索引名] [索引类型] (字段名[(长度)][asc | desc]) );
直接创建索引
CREATE [UNIQUE] INDEX index_name ON tbl_name (index_col_name[(length)],...); create [unique|fulltext|spatial] index 索引名称 [索引的类型] on 表名(字段名1[(长度)][asc|desc],字段名2[(长度)][asc|desc]....);
UNIQUE: 可选参数 , 表示索引为唯一索引。FULLTEXT: 可选参数 , 表示索引为全文索引。SPATIAL: 可选参数 , 表示索引为空间索引。INDEX | KEY: 用于指定字段为索引的 , 用户在选择时 , 只需要二选一即可。[索引名] : 可选参数 , 其作用是给创建的索引取新名称。(起到方便使用的目的)
被选定的字段名 : 必选参数 , 被用作索引的对应的字段名称 , 该字段必须被预先定义。
长度 : 可选参数 , 其指索引的长度 , 必须是字符串类型才可以使用。(比如 : 电话号码)
[ASC | DESC]: 可选参数 ,ASC表示升序排列 ,DESC表示降序排列。
通过修改表结构创建索引
ALTER TABLE tbl_name ADD INDEX index_name(index_col_name[(length)]); alter table 表名 add index|key [索引名] [索引类型] (字段名[长度][asc|desc]);查看创建索引帮助
MariaDB [(none)]> help create index Name: 'CREATE INDEX' Description: Syntax: CREATE [ONLINE|OFFLINE] [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name [index_type] ON tbl_name (index_col_name,...) [index_option] ... index_col_name: col_name [(length)] [ASC | DESC] index_type: USING {BTREE | HASH} index_option: KEY_BLOCK_SIZE [=] value | index_type | WITH PARSER parser_name | COMMENT 'string'
删除索引
使用
alter table删除alter table 表名 drop index|key 索引名称; ALTER TABLE tbl_name DROP INDEX index_name(index_col_name);使用
drop index删除drop index 索引名称 on 表名; DROP INDEX index_name ON tbl_name;
查看索引
SHOW INDEXES FROM [db_name.]tbl_name;优化表结构
OPTIMIZE TABLE tb_name;查看索引统计信息
SET GLOBAL userstat=1; SHOW INDEX_STATISTICS;
范例
#创建表
CREATE TABLE user (
id int(11) NOT NULL AUTO_INCREMENT COMMENT 'id 自增,主键',
name varchar(12) NOT NULL DEFAULT '' COMMENT '用户姓名',
score int(3) NOT NULL COMMENT '分数',
class varchar(12) NOT NULL COMMENT '班级',
school_id int(11) NOT NULL COMMENT '学校id',
PRIMARY KEY (id)
) ENGINE=InnoDB AUTO_INCREMENT=192904 DEFAULT CHARSET=utf8;
MariaDB [db]> CREATE TABLE user (
-> id int(11) NOT NULL AUTO_INCREMENT COMMENT 'id 自增,主键',
-> name varchar(12) NOT NULL DEFAULT '' COMMENT '用户姓名',
-> score int(3) NOT NULL COMMENT '分数',
-> class varchar(12) NOT NULL COMMENT '班级',
-> school_id int(11) NOT NULL COMMENT '学校id',
-> PRIMARY KEY (id)
-> ) ENGINE=InnoDB AUTO_INCREMENT=192904 DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.050 sec)
MariaDB [db]> desc user;
+-----------+-------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+-----------+-------------+------+-----+---------+----------------+
| id | int(11) | NO | PRI | NULL | auto_increment |
| name | varchar(12) | NO | | | |
| score | int(3) | NO | | NULL | |
| class | varchar(12) | NO | | NULL | |
| school_id | int(11) | NO | | NULL | |
+-----------+-------------+------+-----+---------+----------------+
5 rows in set (0.002 sec)
MariaDB [db]> CREATE INDEX name_Index ON `user`(`name`(5));
Query OK, 0 rows affected (0.039 sec)
Records: 0 Duplicates: 0 Warnings: 0
MariaDB [db]> CREATE INDEX school_Index ON `user`(`school_id`);
Query OK, 0 rows affected (0.037 sec)
Records: 0 Duplicates: 0 Warnings: 0
MariaDB [db]> CREATE INDEX class_score_Index ON `user`(`class`, `score`);
Query OK, 0 rows affected (0.066 sec)
Records: 0 Duplicates: 0 Warnings: 0
MariaDB [db]> desc user;
+-----------+-------------+------+-----+---------+----------------+
| Field | Type | Null | Key | Default | Extra |
+-----------+-------------+------+-----+---------+----------------+
| id | int(11) | NO | PRI | NULL | auto_increment |
| name | varchar(12) | NO | MUL | | |
| score | int(3) | NO | | NULL | |
| class | varchar(12) | NO | MUL | NULL | |
| school_id | int(11) | NO | MUL | NULL | |
+-----------+-------------+------+-----+---------+----------------+
5 rows in set (0.001 sec)注 : 查看表结构(
desc user)中 ,key列对应三个类型:PRI, 主键约束 ;UNI, 唯一约束 ;MUL, 可以重复
范例: 查看index内容
MariaDB [db]> SHOW INDEX FROM user;
+-------+------------+-------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+-------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| user | 0 | PRIMARY | 1 | id | A | 0 | NULL | NULL | | BTREE | | |
| user | 1 | name_Index | 1 | name | A | 0 | 5 | NULL | | BTREE | | |
| user | 1 | class_score_Index | 1 | class | A | 0 | NULL | NULL | | BTREE | | |
| user | 1 | class_score_Index | 2 | score | A | 0 | NULL | NULL | | BTREE | | |
| user | 1 | school_Index | 1 | school_id | A | 0 | NULL | NULL | | BTREE | | |
+-------+------------+-------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
5 rows in set (0.001 sec)
范例: 查看索引统计信息
MariaDB [db]> SET GLOBAL userstat=1;
Query OK, 0 rows affected (0.000 sec)
MariaDB [hellodb]> SHOW INDEX_STATISTICS;
Empty set (0.000 sec)
MariaDB [hellodb]> select * from students where stuid=10;
+-------+--------------+-----+--------+---------+-----------+
| StuID | Name | Age | Gender | ClassID | TeacherID |
+-------+--------------+-----+--------+---------+-----------+
| 10 | Yue Lingshan | 19 | F | 3 | NULL |
+-------+--------------+-----+--------+---------+-----------+
1 row in set (0.000 sec)
MariaDB [hellodb]> SHOW INDEX_STATISTICS;
+--------------+------------+------------+-----------+
| Table_schema | Table_name | Index_name | Rows_read |
+--------------+------------+------------+-----------+
| hellodb | students | PRIMARY | 1 |
+--------------+------------+------------+-----------+
MariaDB [hellodb]> select * from students where stuid=10;
+-------+--------------+-----+--------+---------+-----------+
| StuID | Name | Age | Gender | ClassID | TeacherID |
+-------+--------------+-----+--------+---------+-----------+
| 10 | Yue Lingshan | 19 | F | 3 | NULL |
+-------+--------------+-----+--------+---------+-----------+
1 row in set (0.000 sec)
MariaDB [hellodb]> SHOW INDEX_STATISTICS;
+--------------+------------+------------+-----------+
| Table_schema | Table_name | Index_name | Rows_read |
+--------------+------------+------------+-----------+
| hellodb | students | PRIMARY | 2 |
+--------------+------------+------------+-----------+
1 row in set (0.000 sec)5.2 ANALYZE TABLE
语法 :
ANALYZE TABLE table;作用 : 执行
ANALYZE TABLE,MySQL会分析指定表的键的值(主键、唯一键、外键等 , 也可以看成就是索引列的值)分布情况 , 并会记录分布情况。限制 : 执行此语句需要具有
SELECT、DELETE权限 , 且只对存储引擎为InnoDB、MyISAM、NDB的表有作用 , 不能用于视图。如下图所示 ,actor_info是视图 , 执行失败。
执行输出结果 :
在对表的键分布进行分析时 , ANALYZE TABLE操作会将指定的表从表定义缓存中移除 , 并且会对于InnoDB、MyISAM表会加上读锁 , 即其他会话只能对表数据进行查询 , 无法对表数据进行修改 , 直到执行分析的会话释放了锁。
默认的 , MySQL服务会将ANALYZE TABLE语句写到binlog中 , 以便在主从架构中 , 从服务能够同步数据。(从服务通过binlog与主服务完成数据同步) 。可以添加参数取消将语句写到binlog中:
ANALYZE NO_WRITE_TO_BINLOG TABLE 表名或者
ANALYZE LOCAL TABLE 表名
ANALYZE TABLE分析后的统计结果会反应到cardinality的值 , 该值统计了表中某一键所在的列 , 不重复的值的个数。该值越接近表中的总行数 , 则在表连接查询或者索引查询时 , 就越优先被优化器选择使用。也就是索引列的cardinality的值与表中数据的总条数差距越大 , 即使查询的时候使用了该索引作为查询条件 , 实际存储引擎实际查询的时候使用的概率就越小。我们都知道 , 索引尽量建立在重复值很少的列上就是基于这个原因。下面通过例子来验证下。cardinality可以通过SHOW INDEX FROM 表名查看 : 
film表中的数据总条数是1000 。由上图可知 , film表建立了四个索引 , 前两个的索引的cardinality就等于表的数据总条数 , 表示很优秀。下面两个的值才是1 , 就很差了。查看select * from film where film_id = 1;的执行计划 , 其中film_id是索引列 , cardinality=1000。 
从执行计划的结果可以看出 , 上面的语句是使用了索引的。再来查看select * from film where language_id = 1;的执行计划 , 其中language_id也是索引列 , 但是cardinality=1。
由上面执行计划的结果可以看出 , 虽然语句中使用了索引 , 但是存储引擎在实际执行查询的时候并没有使用索引。因为cardinality的值与表中的数据总条数差距太大了。
analyze table的作用analyze table会统计索引分布信息。对于
MyISAM表 , 相当于执行了一次myisamchk --analyze支持
InnoDB、NDB、MyISAM等存储引擎 , 但不支持视图(view)执行
analyze table时 , 会对表加上读锁(read lock)该操作会记录
binlog
生产上操作的风险
analyze table的需要扫描的page代价粗略估算公式 :sample_pages * 索引数 * 表分区数。因此 , 索引数量较多 , 或者表分区数量较多时 , 执行
analyze table可能会比较费时 , 要自己评估代价 , 并默认只在负载低谷时执行。特别提醒 , 如果某个表上当前有慢
SQL, 此时该表又执行analyze table。则该表后续的查询均会处于waiting for table flush的状态 , 严重的话会影响业务 , 因此执行前必须先检查有无慢查询。
注 : 上面多次提到
MyISAM, 仅是本次总结所需 , 并不推荐大家使用MyISAM引擎 , 使用InnoDB才是正道。
6. MySQL的索引实现
分析MySQL的两种存储引擎的索引实现 : MyISAM引擎和InnoDB引擎。
6.1 MyISAM索存储引擎索引
以一个简单的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中。
6.1.1 根据主键等值查询数据
select * from user where id = 28第一次磁盘
IO: 先在主键索引树中从根节点开始检索 , 将根节点加载到内存中 , 比较28<75, 所以走左子树。第二次磁盘
IO: 将左子树节点加载到内存中 , 比较16<28<47, 向下检索。第三次磁盘
IO: 检索到叶子节点 , 将节点加载到内存中遍历 , 从16<28、18<28、28=28, 查找到键值等于28的索引项。第四次磁盘
IO: 从索引项中获取磁盘地址 , 然后到数据文件user.MYD中获取对应整行记录。将记录返回给客户端。
磁盘IO次数 : 3次索引检索+1次记录数据检索 :
6.1.2 根据主键范围查询数据
select * from user where id between 28 and 47;第一次磁盘
IO: 先在主键索引树中从根节点开始检索 , 将根节点加载到内存中 , 比较28<75, 所以走左子树。第二次磁盘
IO: 将左子树节点加载到内存中 , 比较16<28<47, 向下检索。第三次磁盘
IO: 检索到叶子节点 , 将节点加载到内存中遍历 , 从16<28、18<28、28=28, 查找到键值等于28的索引项 , 根据次磁盘地址从数据文件中获取行记录缓存到结果集中。第四次磁盘
IO:我们在查询时时根据范围查找 , 将下一个节点加载到内存中 , 遍历比较 ,28<47=47, 根据磁盘地址从数据文件中获取地址缓存到结果集中。根据上图可知 , 最后得到两条符合筛选条件的结果集 , 将结果返回给客户端。
磁盘IO次数 : 4次索引检索+1次记录数据检索。
提示 :
以上分析仅供参考 , 如果使用
MyISAM存储引擎在查询时 , 会将索引节点缓存在MySQL缓存中 , 而数据缓存依赖于操作系统自身的缓存 , 这里只是为了演示分析索引的使用过程。
6.1.3 辅助索引
在
MyISAM存储引擎中 , 辅助索引和主键索引的结构是一样的 , 没有任何区别 , 叶子节点中data阈存储的都是行记录的磁盘地址。主键列索引的键值是唯一的 , 而辅助索引的键值是可以重复的。
查询数据时 , 由于辅助索引的键值不唯一 , 可能存在多个拥有相同的记录 , 所以即使是等值查询 , 也需要按照范围查询的方式在辅助索引树中检索数据。
6.2 InnoDB存储引擎索引
6.2.1 主键索引(聚簇索引)
每个InnoDB表都有一个聚簇索引 , 聚簇索引使用B+树构建 , 叶子节点的data阈存储的是整行记录。一般情况下 , 聚簇索引等同于主键索引 , 当一个表没有创建主键索引时 , InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下:
在创建表时 , 定义主键
PRIMARY KEY,InnoDB会自动将主键索引用作聚簇索引。如果表没有定义主键 ,
InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。如果以上两个都没有 ,
InnoDB会自动使用一个长度为6字节的ROWID字段来构建聚簇索引 , 该ROWID字段会在插入新的行记录时自动递增。
除聚簇索引之外的所有索引都被称为辅助索引。在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;InnoDB的数据和索引存储在t_user_innodb.ibd文件中 ,InnoDB的数据组织方式 , 是聚簇索引。主键索引的叶子节点会存储数据行 , 辅助索引的叶子节点只会存储主键值。
等值查询数据 :
select * from user_innodb where id = 28;发生三次磁盘IO :
6.2.2 辅助索引
除聚簇索引之外的所有索引都被称为辅助索引 ,
InnoDB的辅助索引只会存储值而不存储磁盘地址。以
user_innodb的age列为例 ,age列的辅助索引结构如下图:
辅助索引的底层叶子节点是按照(
age,id) 的顺序排序 , 先按照age列从小到大排序 ,age相同时按照id列从小到大排序。使用辅助索引需要检索两遍索引 : 首先检索辅助索引获得主键 , 然后根据主键到主键索引中检索获得数据记录。
辅助索引等值查询的情况 :
select * from t_user_innodb where age=19;
在辅助索引树中获取到主键id , 再根据主键id到主键索引数中检索数据的的过程称为回表查询。
磁盘IO数(从根节点开始) : 辅助索引3次 + 回表过程3次。
6.2.3 组合索引
以表
abc_innodb为例 ,id列为主键索引 , 创建一个联合索引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;
6.2.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)三个索引。
组合索引的最左前缀匹配原则 : 使用组合索引查询时 , mysql会一直向右匹配直至遇到范围查询(>、<、between、like)等就会停止匹配。
6.2.5 覆盖索引
覆盖索引并不是一种索引结构 , 覆盖索引是一种很常用的优化手段。因为在使用辅助索引的时候 , 我们只可以拿到相应的主键值 , 想要获取最终的数据记录 , 还需要根据主键通过主键索引再去检索 , 最终获取到符合条件的数据记录。
在上面的abc_innodb表中的组合索引查询时 , 如果我们查询的结果只需要a、b、c这三个字段 , 那我们使用这个idx_index(a , b , c)组合索引查询到叶子节点时就可以直接返回了 , 而不需要再次回表查询 , 这种情况就是覆盖索引。
7 回表和联合索引的应用
7.1 回表查询
在InnoDB的存储引擎中 , 使用辅助索引查询的时候, 因为辅助索引叶子节点保存的数据不是当前数据记录, 而是当前数据记录的主键索引。如果需要获取当前记录完整的数据 , 就必须要再次根据主键从主键索引中继续检索查询 , 这个过程我们称之为回表查询。
由此可见 , 在数据量比较大的时候 , 回表必然会消耗很多的时间影响性能 , 所以我们要尽量避免回表的发生。
7.2 如何避免回表
使用覆盖索引 , 举个例子: 现有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字段的数据了。
以上就是一个典型的使用覆盖索引的优化策略减少了回表查询的情况。
7.3 联合索引的使用
联合索引 : 在建立索引的时候 , 尽量在多个单列索引上判断是否可以使用联合索引。联合索引的使用不仅可以节省空间 , 还可以更容易的使用到覆盖索引。
节省空间 :
试想一下 , 索引的字段越多 , 是不是更容易满足查询需要返回的数据呢？比如联合索引(a , b , c)是不是等于有了 : a、(a , b)、(a , b , c)三个索引 , 这样是不是节省了空间 , 当然节省的空间并不是三倍于a、(a , b)、(a , b , c)三个索引所占用的空间 , 但是联合索引中data字段数据所占用的空间确实节省了不少。
联合索引的创建原则 :
在创建联合索引的时候应该把频繁使用的列、区分度高的列放在前面。频繁使用代表索引利用率高 , 区分度高代表筛选力度大 ,这些都是在创建索引的时候需要考虑到的优化场景 , 也可以将常需要作为查询返回的字段增加到联合索引中。
如果在联合索引上增加了一个字段 , 而恰好满足了使用覆盖索引的情况 , 这种情况建议使用联合索引。
联合索引的使用:
考虑到当前是否已经存在多个可以合并的单列索引。如果有 , 那么推荐将当前的多个单列索引创建为一个联合索引。
当前索引存在频繁使用 , 在结果中有一个列也被频繁查询 , 而这个列不在当前频繁使用的索引中 , 那么这个时候就可以考虑这个列是否可以加入到当前频繁使用的索引中 , 使其查询语句可以使用到覆盖索引。
8 EXPLAIN 工具
可以通过EXPLAIN来分析索引的有效性,获取查询执行计划信息 , 用来查看查询优化器如何执行查询
参考资料 : https://dev.mysql.com/doc/refman/5.7/en/explain-output.html
语法 :
EXPLAIN SELECT clause
EXPLAIN输出信息说明:
说明 : type显示的是访问类型 , 是较为重要的一个指标 , 结果值从好到坏依次是 : system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL 。一般来说得保证查询至少达到range级别 , 最好能达到ref
system: 表只有一行记录(等于系统表) ,这是const类型的特列 , 平时不会出现 , 这个也可以忽略不计const: 表示通过索引一次就找到了 ,const用于比较primary key或者unique索引。因为只匹配一行数据 , 所以很快。如将主键置于where列表中 ,MySQL就能将该查询转换为一个常量。
首先进行子查询得到一个结果的
d1临时表 , 子查询条件为id = 1是常量 , 所以type是const,id为1的相当于只查询一条记录 , 所以type为system。eq_ref: 唯一性索引扫描 , 对于每个索引键 , 表中只有一条记录与之匹配。常见于主键或唯一索引扫描ref: 非唯一性索引扫描 , 返回匹配某个单独值的所有行 。 本质上也是一种索引访问 , 它返回所有匹配某个单独值的行 。然而 , 它可能会找到多个符合条件的行 , 所以他应该属于查找和扫描的混合体。
range: 只检索给定范围的行 , 使用一个索引来选择行 ,key列显示使用了哪个索引 。一般就是在你的where语句中出现between、<、>、in等的查询 。这种范围扫描索引比全表扫描要好 。因为它只需要开始于索引的某一点 , 而结束于另一点 , 不用扫描全部索引。
index:Full Index Scan,Index与All区别为index类型只遍历索引树。这通常比ALL快 , 因为索引文件通常比数据文件小。(也就是说虽然all和Index都是读全表 , 但index是从索引中读取的 , 而all是从硬盘读取的)
id是主键 ,所以存在主键索引all:Full Table Scan将遍历全表以找到匹配的行
范例:
MariaDB [hellodb]> explain select * from students where stuid not in (5,10,20);
MariaDB [hellodb]> explain select * from students where stuid <> 10 ;
MariaDB [hellodb]> explain select * from students where age > (select avg(age) from teachers);
范例 : 创建索引和使用索引
MariaDB [hellodb]> create index idx_name on students(name(10));
Query OK, 0 rows affected (0.009 sec)
Records: 0 Duplicates: 0 Warnings: 0
MariaDB [hellodb]> show indexes from students\G;
*************************** 1. row ***************************
Table: students
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 1
Column_name: StuID
Collation: A
Cardinality: 25
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
*************************** 2. row ***************************
Table: students
Non_unique: 1
Key_name: idx_name
Seq_in_index: 1
Column_name: Name
Collation: A
Cardinality: 25
Sub_part: 10
Packed: NULL
Null:
Index_type: BTREE
Comment:
Index_comment:
2 rows in set (0.001 sec)MariaDB [hellodb]> explain select * from students where name like 'w%'; 
MariaDB [hellodb]> explain select * from students where name like 'x%';
MariaDB [hellodb]> SHOW INDEX_STATISTICS;
+--------------+------------+------------+-----------+
| Table_schema | Table_name | Index_name | Rows_read |
+--------------+------------+------------+-----------+
| hellodb | students | idx_name | 2 |
| mysql | help_topic | name | 1 |
+--------------+------------+------------+-----------+
2 rows in set (0.000 sec)范例 : 查询中若使用覆盖索引 (select后要查询的字段刚好和创建的索引字段完全相同) , possible_keys会直接显示NULL 。则该索引仅出现在key列表中
范例 : key_len显示的值为索引字段的最大可能长度 , 并非实际使用长度 。即key_len是根据表定义计算而得 , 不是通过表内检索出的。
范例 :
执行顺序1 :
select_type为UNION, 说明第四个select是UNION里的第二个select, 最先执行【select name,id from t2】执行顺序2 :
id为3, 是整个查询中第三个select的一部分。因查询包含在from中 , 所以为DERIVED, 【select id,name from t1 where other_column=’’】执行顺序3 :
select列表中的子查询select_type为subquery,为整个查询中的第二个select, 【select id from t3】执行顺序4 :
id列为1, 表示是UNION里的第一个select,select_type列的primary表示该查询为外层查询 ,table列被标记为<derived3>,表示查询结果来自一个衍生表 , 其中derived3中的3代表该查询衍生自第三个select查询 , 即id为3的select。【select d1.name …】执行顺序5 : 代表从
UNION的临时表中读取行的阶段 ,table列的<union1,4>表示用第一个和第四个select的结果进行UNION操作。【两个结果union操作】