终极-2024校招八股文【MySQL索引】第一篇
1 什么是索引?
索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分),它们包含着对数据表里所有记录的引用指针。
索引是一种数据结构。数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。
更通俗的说,索引就相当于目录。为了方便查找书中的内容,通过对内容建立索引形成目录。索引是一个文件,它是要占据物理空间的。
2 索引有哪些优缺点?
索引的优点
- 可以大大加快数据的检索速度,这也是创建索引的最主要的原因。
- 通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。
索引的缺点
- 时间方面:创建索引和维护索引要耗费时间,具体地,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,会降低增/改/删的执行效率;
- 空间方面:索引需要占物理空间
3 为什么使用索引?
- 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。
- 可以大大加快数据的检索速度,这也是创建索引的最主要的原因。
- 帮助服务器避免排序和临时表
- 将随机IO变为顺序IO。
- 可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。
4 索引有哪几种类型?
主键索引: 数据列不允许重复,不允许为NULL,一个表只能有一个主键。
唯一索引: 数据列不允许重复,允许为NULL值,一个表允许多个列创建唯一索引。
- 可以通过 ALTER TABLE table_name ADD UNIQUE (column); 创建唯一索引
- 可以通过 ALTER TABLE table_name ADD UNIQUE (column1,column2); 创建唯一组合索引
普通索引: 基本的索引类型,没有唯一性的限制,允许为NULL值。
- 可以通过ALTER TABLE table_name ADD INDEX index_name (column);创建普通索引
- 可以通过ALTER TABLE table_name ADD INDEX index_name(column1, column2, column3);创建组合索引
全文索引:是目前搜索引擎使用的一种关键技术。
- 可以通过ALTER TABLE table_name ADD FULLTEXT (column);创建全文索引
5 索引的数据结构(b树,hash)
索引的数据结构和具体存储引擎的实现有关,在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的InnoDB存储引擎的默认索引实现为:B+树索引。对于哈希索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景,建议选择BTree索引。
B树索引
mysql通过存储引擎取数据,基本上90%的人用的就是InnoDB了,按照实现方式分,InnoDB的索引类型目前只有两种:BTREE(B树)索引和HASH索引。B树索引是Mysql数据库中使用最频繁的索引类型,基本所有存储引擎都支持BTree索引。通常我们说的索引不出意外指的就是(B树)索引(实际是用B+树实现的,因为在查看表索引时,mysql一律打印BTREE,所以简称为B树索引)
查询方式:
主键索引区:PI(关联保存的时数据的地址)按主键查询,
普通索引区:si(关联的id的地址,然后再到达上面的地址)。所以按主键查询,速度最快
B+tree性质:
1.)n棵子tree的节点包含n个关键字,不用来保存数据而是保存数据的索引。
2.)所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3.)所有的非终端结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。
4.)B+ 树中,数据对象的插入和删除仅在叶节点上进行。
5.)B+树有2个头指针,一个是树的根节点,一个是最小关键码的叶节点。
哈希索引
简要说下,类似于数据结构中简单实现的HASH表(散列表)一样,当我们在mysql中用哈希索引时,主要就是通过Hash算法(常见的Hash算法有直接定址法、平方取中法、折叠法、除数取余法、随机数法),将数据库字段数据转换成定长的Hash值,与这条数据的行指针一并存入Hash表的对应位置;如果发生Hash碰撞(两个不同关键字的Hash值相同),则在对应Hash键下以链表形式存储。当然这只是简略模拟图。
6 索引使用场景(重点)
where
如果有多个,最终会选一个较优的作为检索的依据。
order by
当我们使用order by将查询结果按照某个字段排序时,如果该字段没有建立索引,那么执行计划会将查询出的所有数据使用外部排序(将数据从硬盘分批读取到内存使用内部排序,最后合并排序结果),这个操作是很影响性能的,因为需要将查询涉及到的所有数据从磁盘中读到内存(如果单条数据过大或者数据量过多都会降低效率),更无论读到内存之后的排序了。
但是如果我们对该字段建立索引alter table 表名 add index(字段名),那么由于索引本身是有序的,因此直接按照索引的顺序和映射关系逐条取出数据即可。而且如果分页的,那么只用取出索引表某个范围内的索引对应的数据,而不用像上述那取出所有数据进行排序再返回某个范围内的数据。(从磁盘取数据是最影响性能的)
join
对join语句匹配关系(on)涉及的字段建立索引能够提高效率
索引覆盖
如果要查询的字段都建立过索引,那么引擎会直接在索引表中查询而不会访问原始数据(否则只要有一个字段没有建立索引就会做全表扫描),这叫索引覆盖。因此我们需要尽可能的在select后只写必要的查询字段,以增加索引覆盖的几率。
这里值得注意的是不要想着为每个字段建立索引,因为优先使用索引的优势就在于其体积小。
7 创建索引的原则(重中之重)
索引虽好,但也不是无限制的使用,最好符合一下几个原则
1) 最左前缀匹配原则,组合索引非常重要的原则,mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配,比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引,d是用不到索引的,如果建立(a,b,d,c)的索引则都可以用到,a,b,d的顺序可以任意调整。
2)较频繁作为查询条件的字段才去创建索引
3)更新频繁字段不适合创建索引
4)若是不能有效区分数据的列不适合做索引列(如性别,男女未知,最多也就三种,区分度实在太低)
5)尽量的扩展索引,不要新建索引。比如表中已经有a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可。
6)定义有外键的数据列一定要建立索引。
7)对于那些查询中很少涉及的列,重复值比较多的列不要建立索引。
8)对于定义为text、image和bit的数据类型的列不要建立索引。
8 使用索引查询一定能提高查询的性能吗?为什么
通常,通过索引查询数据比全表扫描要快。但是我们也必须注意到它的代价。
- 索引需要空间来存储,也需要定期维护, 每当有记录在表中增减或索引列被修改时,索引本身也会被修改。这意味着每条记录的INSERT,DELETE,UPDATE将为此多付出4,5 次的磁盘I/O。因为索引需要额外的存储空间和处理,那些不必要的索引反而会使查询反应时间变慢。使用索引查询不一定能提高查询性能,索引范围查询(INDEX RANGE SCAN)适用于两种情况:
- 基于一个范围的检索,一般查询返回结果集小于表中记录数的30%
- 基于非唯一性索引的检索
9 MyISAM和InnoDB实现B树索引方式的区别是什么?
MyISAM,B+Tree叶节点的data域存放的是数据记录的地址,在索引检索的时候,首先按照B+Tree搜索算法搜索索引,如果指定的key存在,则取出其data域的值,然后以data域的值为地址读取相应的数据记录,这被称为“非聚簇索引”
InnoDB,其数据文件本身就是索引文件,相比MyISAM,索引文件和数据文件是分离的,其表数据文件本身就是按B+Tree组织的一个索引结构,树的节点data域保存了完整的数据记录,这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引,这被称为“聚簇索引”或者聚集索引,而其余的索引都作为辅助索引,辅助索引的data域存储相应记录主键的值而不是地址,这也是和MyISAM不同的地方。
在根据主索引搜索时,直接找到key所在的节点即可取出数据;在根据辅助索引查找时,则需要先取出主键的值,再走一遍主索引。因此,在设计表的时候,不建议使用过长的字段为主键,也不建议使用非单调的字段作为主键,这样会造成主索引频繁分裂。
10 数据库索引采用B+树而不是B树,主要原因是什么?
主要原因:B+树只要遍历叶子节点就可以实现整棵树的遍历,而且在数据库中基于范围的查询是非常频繁的,而B树只能中序遍历所有节点,效率太低。
11 文件索引和数据库索引为什么使用B+树?
文件与数据库都是需要较大的存储,也就是说,它们都不可能全部存储在内存中,故需要存储到磁盘上。而所谓索引,则为了数据的快速定位与查找,那么索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数,因此B+树相比B树更为合适。数据库系统巧妙利用了局部性原理与磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入,而红黑树这种结构,高度明显要深的多,并且由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性。
最重要的是,B+树还有一个最大的好处:方便扫库。
B树必须用中序遍历的方法按序扫库,而B+树直接从叶子结点挨个扫一遍就完了,B+树支持range-query非常方便,而B树不支持,这是数据库选用B+树的最主要原因。
B+树查找效率更加稳定,B树有可能在中间节点找到数据,稳定性不够。
12 MySQL索引主要使用的两种数据结构是什么?
- 哈希索引**,对于哈希索引来说,底层的数据结构肯定是哈希表,因此在绝大多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余大部分场景,建议选择BTree索引
- BTree索引,Mysql的BTree索引使用的是B树中的B+Tree,BTREE索引就是一种将索引值按一定的算法,存入一个树形的数据结构中(二叉树),每次查询都是从树的入口root开始,依次遍历node,获取leaf。但对于主要的两种存储引擎(MyISAM和InnoDB)的实现方式是不同的。
13 MySQL中有四种索引类型,可以简单说说吗?
- FULLTEXT :即为全文索引,目前只有MyISAM引擎支持。其可以在CREATE TABLE ,ALTER TABLE ,CREATE INDEX 使用,不过目前只有 CHAR、VARCHAR ,TEXT 列上可以创建全文索引,需要注意的是MySQL5.6以后支持全文索引了,5.6之前是不支持的。
- HASH :由于HASH的唯一(几乎100%的唯一)及类似键值对的形式,很适合作为索引。 HASH索引可以一次定位,不需要像树形索引那样逐层查找,因此具有极高的效率。但是,这种高效是有条件的,即只在“=”和“in”条件下高效,对于范围查询、排序及组合索引仍然效率不高。
- BTREE :BTREE索引就是一种将索引值按一定的算法,存入一个树形的数据结构中(二叉树),每次查询都是从树的入口root开始,依次遍历node,获取leaf。这是MySQL里默认和最常用的索引类型。
- RTREE :RTREE在MySQL很少使用,仅支持geometry数据类型,支持该类型的存储引擎只有MyISAM、BDb、InnoDb、NDb、Archive几种。 相对于BTREE,RTREE的优势在于范围查找。
14 为什么说B+tree比B 树更适合实际应用中操作系统的文件索引和数据库索引?
B+tree的磁盘读写代价更低,B+tree的查询效率更加稳定数据库索引采用B+树而不是B树的主要原因:B+树只要遍历叶子节点就可以实现整棵树的遍历,而且在数据库中基于范围的查询是非常频繁的,而B树只能中序遍历所有节点,效率太低。
B+树的特点
- 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
- 不可能在非叶子结点命中;
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
15 数据库为什么使用B+树而不是B树
- B树只适合随机检索,而B+树同时支持随机检索和顺序检索;
- B+树空间利用率更高,可减少I/O次数,磁盘读写代价更低。一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗。B+树的内部结点并没有指向关键字具体信息的指针,只是作为索引使用,其内部结点比B树小,盘块能容纳的结点中关键字数量更多,一次性读入内存中可以查找的关键字也就越多,相对的,IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素;
- B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。
- B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起,只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作。
- 增删文件(节点)时,效率更高。因为B+树的叶子节点包含所有关键字,并以有序的链表结构存储,这样可很好提高增删效率。
16使用B树的好处
B树可以在内部节点同时存储键和值,因此,把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。这种特性使得B树在特定数据重复多次查询的场景中更加高效。
17 使用B+树的好处
由于B+树的内部节点只存放键,不存放值,因此,一次读取,可以在内存页中获取更多的键,有利于更快地缩小查找范围。B+树的叶节点由一条链相连,因此,当需要进行一次全数据遍历的时候,B+树只需要使用O(logN)时间找到最小的一个节点,然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历,这会需要更多的内存置换次数,因此也就需要花费更多的时间
18 什么时候需要建立数据库索引呢?要注意什么?
在最频繁使用的、用以缩小查询范围的字段,需要排序的字段上建立索引。不宜:1)对于查询中很少涉及的列或者重复值比较多的列2)对于一些特殊的数据类型,不宜建立索引,比如文本字段(text)等。
19 覆盖索引是什么?
如果一个索引包含(或者说覆盖)所有需要查询的字段的值,我们就称 之为“覆盖索引”。
我们知道在InnoDB存储引 擎中,如果不是主键索引,叶子节点存储的是主键+列值。最终还是要“回表”,也就是要通过主键再查找一次,这样就 会比较慢。覆盖索引就是把要查询出的列和索引是对应的,不做回表操作!
20 什么是聚集索引 ?
聚集索引就是按照拼音查询,非聚集索引就是按照偏旁等来进行查询。
其实,我们的汉语字典的正文本身就是一个聚集索引。比如,我们要查"安"字,就会很自然地翻开字典的前几页,因为"安"的拼音是"an",而按照拼音排序 汉字的字典是以英文字母"a"开头并以"z"结尾的,那么"安"字就自然地排在字典的前部。
如果您翻完了所有以"a"开头的部分仍然找不到这个字,那么就 说明您的字典中没有这个字;
同样的,如果查"张"字,那您也会将您的字典翻到最后部分,因为"张"的拼音是"zhang"。
也就是说,字典的正文部分本身 就是一个目录,您不需要再去查其他目录来找到您需要找的内容。
我们把这种正文内容本身就是一种按照一定规则排列的目录称为"聚集索引"