hehear

mysql系列-索引,介绍索引的特性,数据结构等。


简介

索引index是帮助mysql高效的获取数据的数据结构,在数据之外,数据库系统还维护者满足特定查找算法的数据结构,这些数据结构以某种方式指向数据,这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。

简单的理解是:索引是排好序的快速查找数据结构。一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往一索引文件的形式存储在磁盘上。

我们平时说的索引,如果没有特别指明,都是指B数(多路搜索树,比一定都是二叉树),其中聚集索引,次要索引,符合索引,前缀索引,唯一索引默认都是使用B+树索引,统称为索引。除B+树外还有哈希索引。

优缺点

优点

  1. 保证唯一性: 通过创建唯一的索引,保证数据库表中每一行数据的唯一性。
  2. 降低数据库IO成本:提高数据检索效率,降低了数据库的IO成本
  3. 降低CPU消耗:通过索引对数据进行排序,降低了数据排序的成本,降低了CPU消耗。
  4. 保证数据参考完整性:加快了表与表的连接速度,对于提高数据的参考完整性有主要意义。

缺点

  1. 占用物理空间:索引需要占用物理空间,除了数据表占用数据空间外,每个索引还要占用一定的物理空间,如果建立聚簇索引,需要的空间更大
  2. 更新数据速度慢:当对表中的数据进行增加、删除、修改的时候,索引也要动态维护,这样降低了数据的维护速度。
  3. 创建维护索引耗费时间:创建索引和维护索引要耗费时间,这种时间随着数据量的增加而不断递增。

使用注意事项

适合创建索引

  • 经常需要搜索的列上创建索引,加快搜索的速度
  • 经常使用where子句的列上创建索引,加快条件的判断速度
  • 经常需要排序的列上创建索引 ,因为索引已经排序,查询利用索引的排序,加快排序时间
  • 经常用在关联连接的列上创建索引,可以加快连接速度,
  • 经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的

不适合创建索引

  • 查询中很少使用或者参考的列不应该创建索引,很少使用,不能提高查询速度,反而因为增加了索引,降低了系统维护速度和空间需求
  • 对于很少数值的列如性别,不应该创建索引
  • 对于text、image、bit数据类型的列不应该增加索引
  • 经常修改更新的列不应该创建索引

索引分类

mysql主要索引种类有:

  • 单值索引:即一个索引只包含单个列,一个表可以有多个单列索引
  • 唯一索引:索引列的值必须唯一,但允许有空值
  • 复合索引:一个所以包含多个列

基本语法

  1. 创建:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    CREATE [UNIQUE] INDEX indexName ON mytable(columnname(length));

    ALTER TABLE mytable ADD INDEX indexName ON (columnname);//普通索引

    ALTER TABLE mytable ADD PRIMARY KEY(columnName);//主键

    ALTER TABLE mytable ADD UNIQUE INDEX indexName ON (columnname(length));//唯一索引

    ALTER TABLE mytable ADD FULLTEXT indexName(columnname);//全文索引
  1. 删除:

    1
    DROP INDEX indexName ON mytable;
  1. 查看:

    1
    SHOW INDEX FROM mytable;

mysql存储结构

mysql的基本存储结构是页,记录都存在页里面。各个数据页可以组成一个 双向链表。而每个数据页中的记录可以组成一个单向链表

  • 每个数据页都会为存储的记录生成一个页目录,在通过主键查找记录的时候,可以在目录中使用二分法快速定位到对应的槽,然后在遍历该槽对应分组中的记录即可快速找到指定的目录
  • 以非主键作为搜索条件:只能从最小记录开始,依次遍历单链表中的每条记录

执行查询sql时,如果没有进行创建索引优化的话,会默认:

  • 定位到记录所在的页:需要遍历双向链表,找到记录所在的页
  • 从所在的页内查找相应的记录,由于不是根据主键,只能遍历所在页的单链表了,在数据量很大的情况下,查找会很慢

没有索引我们需要遍历双向链表来定位对应的页,在使用索引之后(B+树),通过“目录”就可以很快的定位到数据对应的页了(二分查找,时间复杂度近似O(logn)),底层结构变成了B+树了。

索引结构

mysql索引结构分类有:B+Tree索引、Hash索引、Full-Text全文索引、R-Tree索引

B+Tree索引

B+树是平衡树的一种,如果一棵普通的树在极端的情况下,是能退化成链表的,这样树的优点就不存在了。B+树是不会退化成链表的,树的高度是相对比较低的,基本符合矮矮胖胖的结构,检索的时间复杂度就是O(logn),建立索引实际上就是建立一棵B+树。

  • B+树是一棵平衡树,如果我们对这棵树增删改的话,那肯定会破坏它的原有结构
  • 要维持平衡树, 就必须做额外的工作,因为这些额外的工作开销,导致索引会降低增删改的速度

B+Tree索引是mysql存储引擎的默认索引类型。因为B+Tree索引 的有序性,除了用于查找,还可以用来排序和分组;查找可以用于全键值键值范围键前缀查找,其中 键前缀查找只适用于最左前缀查找,如果不是按照索引列的顺序进行查找,则无法使用索引。

MyISAM

B+Tree叶结点的data域存放的是数据记录的地址,在索引检索的时候,首先按照B+Tree搜索算法搜索索引,如果指定的key存在,则取出data域的值,然后以data域的值为地址读取相应的数据记录,这被称为非聚簇索引

InnoDB

InnoDB的数据文件本身就是索引文件,相比MyISAM的索引文件和数据文件是分离的,InnoDB的表数据文件本身就是按照B+Tree组织的一个索引结构,树的叶结点data域保存了完整的数据记录,这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。这就被称为聚簇索引或聚集索引

而其余的索引都作为辅助索引,辅助索引的data域存储相应记录主键的值而不是地址,这也是和MyISAM不同的地方。在根据主索引搜索时,直接找到key所在的节点即可取出数据。

在根据辅助索引查找时,则需要先取出主键的值,在走一遍主索引,因此,在设计表的时候,不建议使用过长的字段作为主键,也不建议使用非单调字段作为主键,这样会造成主索引频繁分裂。

B树和B+树区别
  • B树的所有节点既存放key也存放数据data;而B+树只有叶子结点存放key和data,其他内结点只存放key
  • B树的叶子结点都是独立的;B+树的叶子结点都有一条引用指向与它相临的叶子结点
  • B树的检索过程相当于对范围内的每个结点的关键字做二分查找,可能还没有到达叶子结点,检索就结束了,而B+结点的效率就更稳定了,任何查找都是从根结点到叶子结点的过程,叶子结点的顺序检索很明显。

Hash索引

Hash索引底层数据结构就是哈希表,采用了哈希算法,把键值换算成新的哈希值,检索时不需要类似B+Tree那样从根结点到叶子节点查找(时间复杂度O(logn)),只需要一次哈希算法(时间复杂度O(1))就可以立刻定位到相应位置。但是也有很多局限性:

  • 哈希索引不能利用索引排序
  • 不支持最左匹配原则
  • 在大量重复键值情况下,哈希索引效率极低,即哈希碰撞问题
  • 不支持范围查询

InnoDB存储引擎有个特殊的功能叫“自适应哈希索引”,当某个索引值被使用的非常频繁时,会在B+Tree索引之上在创建一个哈希索引,这样就让B+Tree索引具有哈希索引的快速哈希查找的优点。

全文索引

M有ISAM存储引擎支持全文索引,用于查找文本中的关键词,而不是直接是否相等,查找条件使用MATCH AGAINST ,而不是普通的WHERE。

全文索引使用倒索引实现,它记录着关键词到其所在文档的映射,InnoDB存储引擎在Mysql5.6.4版本中也开始支持全文索引。

索引优化

独立的列

在进行查询时,索引列不能时表达的一部分,也不能是函数的参数,否则无法使用索引,例如:

1
select id from student where id+1 = 5;

多列索引

在需要使用多个列作为条件查询时,使用多列索引比使用多个单列索引性能更好。例如:

1
select id,name from student where id='1' and name='hehear';

索引列的顺序

让选择性最强的索引放在前面。索引的选择性是指:不重复的索引值和记录总数的比值,最大值为1,此时每个记录都有唯一的索引与其对应。选择性越高,每个记录的区分度越高,查询效率也越高。

前缀索引

对于BLOB、TEXT、VARCHAR类型的列,必须使用前缀索引,指索引开始的部分字符。前缀长度的选取要根据索引选择性来确定。

覆盖索引

覆盖索引是指查询的列和索引是对应的,也就是索引包含所有需要查询的字段的值,其具有以下优点:

  • 索引通常远小于数据行的大小,只读取索引大大减少数据访问量
  • 一些存储引擎(MyISAM)的内存中只缓存索引,而数据依赖于操作系统来缓存,因此只访问索引可以不使用系统调用
  • 对于InnoDB引擎,若辅助索引能够覆盖查询,则无需回表,即无需访问主索引在查找一次

最左匹配原则

mysql中的联合索引,使用时需按照一定的顺序引用多列。如student表中联合索引为(id,name),最左原则匹配原则是指,如果查询的时候查询条件精确匹配索引的左边连续的一列或者几列,则此列就可以被用到:

1
2
3
4
5
6
7
select * from student where id ='1' and name ='hehear'; //可以命中索引

select * from student where name ='hehear';//无法命中索引

select * from student where id='1';//可以命中索引

select * from student where name='hehear' and id='1';//如果索引字段都用上了,查询引擎会自动优化,命中索引

由于最左匹配原则,在创建联合索引时,索引字段的顺序需要考虑字段值去重之后的个数,较多的放在前面,order by语句也遵循此原则。

联合索引使用时,索引列只能用于是否相等,遇到范围查询(>、<、between、like)等就不能进一步匹配了,后续退化为线性查找。例如:

如有索引 (a,b,c,d),查询条件 a=1 and b=2 and c>3 and d=4,则会在每个节点依次命中a、b、c,无法命中d。(c已经是范围查询了,d肯定是排不了序了)

不需要考虑=、in的顺序,mysql会自动优化这些条件的顺序如:

如有索引 (a,b,c,d),查询条件 c>3 and b=2 and a=1 and d<4a=1 and c>3 and b=2 and d<4等顺序都是可以的,MySQL会自动优化为 a=1 and b=2 and c>3 and d<4,依次命中a、b、c。

查询性能优化

使用Explain进行分析

Explain用来分析SELECT查询语句,开发人员可以通过分析Explain结果来优化语句,比较重要的结果字段有:

  • select_type:查询类型,有简单查询、联合查询、自查询
  • key:使用的索引
  • rows:扫描的行数

优化数据访问

减少请求的数据量
  • 只返回必要的列:最好不要使用select * 语句
  • 只返回必要的行:使用LIMIT语句来限制返回数据
  • 缓存重复查询的数据:使用缓存可以避免在数据库中进行查询,提高数据库性能
减少服务器端扫描行数

最有效的方式就是使用索引来覆盖查询

重构查询方式

切分大查询

一个大查询如果一次性执行的话,可能一次锁住很多数据,占满整个事务日志,耗尽系统资源,阻塞很多小而重要的查询,所以当大的查询或更新,可以切分成几段,依次执行。

分解大的连接查询

将一个大的连接查询分解成对每个表进行一次单表查询,然后在应用程序中进行关联,这样的好处:

  • 让缓存更高效,对于连接查询,如果其中一个表发生变化,那么整个缓存就无法使用。而分解后的多个查询,即使其中一个表发生变化,对其他表的查询缓存依然可以使用。
  • 分解成多个单表查询,这些单表查询的缓存结果,更可能被其他的查询使用到,从而减少冗余记录的查询。
  • 减少锁竞争
  • 在应用层进行连接,可以更容易对数据库进行拆分,从而更容易做到高性能和可伸缩
  • 查询本身效率也会提升

 评论