您的位置: 首页  >  文章  >  学习笔记之数据库索引

学习笔记之数据库索引

分类: 文章 • 2023-12-14 19:40:46

文章目录

一、索引

数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。
但是，为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。

二、索引分类

1、从逻辑角度

  • 单列索引：一个索引只包含单个列，但一个表中可以有多个单列索引。
    • 普通索引：MySQL中基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值，纯粹为了查询数据更快一点。
    • 唯一索引：索引列中的值必须是唯一的，但是允许为空值。
    • 主键索引：是一种特殊的唯一索引，不允许有空值。（主键约束，就是一个主键索引）
  • 组合索引：也叫联合索引，在表中的多个字段组合上创建的索引，只有在查询条件中使用了这些字段的左边字段时，索引才会被使用，使用组合索引时遵循最左前缀集合。最左前缀匹配原则见下文。
  • 全文索引：全文索引，只有在MyISAM引擎上才能使用，只能在CHAR,VARCHAR,TEXT类型字段上使用全文索引，介绍了要求，说说什么是全文索引，就是在一堆文字中，通过其中的某个关键字等，就能找到该字段所属的记录行
  • 空间索引：空间索引是对空间数据类型的字段建立的索引，MySQL中的空间数据类型有四种，GEOMETRY、POINT、LINESTRING、POLYGON。在创建空间索引时，使用SPATIAL关键字。要求，引擎为MyISAM，创建空间索引的列，必须将其声明为NOT NULL。

2、从物理存储角度

  • 聚集索引，也叫聚簇索引：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。
    如果表上有定义主键，则该主键就是聚集索引；如果未定义主键，mysql会取第一个唯一索引（unique）而且只含非空列（NOT NULL）作为主键，InnoDB使用它作为聚集索引；如果没有这样的列，InnoDB就自己产生一个这样的ID值，它是6个字节，而且是隐藏的，使其作为聚集索引。
  • 非聚集索引：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。除了聚集索引以外的索引都是非聚集索引，只是人们想细分一下非聚集索引，分成普通索引，唯一索引，全文索引等。

Tips：
(1)MySQL里主键就是聚集索引，而SQL Sever默认主键为聚集索引，也可以指定为非聚集索引。（不能直接说主键就是聚集索引）
(2)按物理存储角度又有一种分法：一级索引（包含聚集索引）和二级索引（除一级索引外，所有的非聚集索引都是），其中**一级索引的叶子节点指向数据节点，二级索引的叶子节点指向一级索引。**示意图如下：
学习笔记之数据库索引
学习笔记之数据库索引
参考
https://www.cnblogs.com/s-b-b/p/8334593.html
https://jingyan.baidu.com/article/e73e26c0f1e82d24acb6a75d.html

三、索引的实现方式

数据库索引一般实现包含B- tree和B+ tree，但红黑树也往往与它们做对比，因此，在此也一并列出比较学习。

1、红黑树

红黑树的应用非常广泛，常见的函数库，如C++中的map，multimap,以及Java中的TreeMap，TreeSet， Java8中的HashMap的实现也采用了红黑树。
红黑树从本质上来说就是一颗二叉查找树，但是在二叉树的基础上增加了着色相关的性质，使得红黑树可以保证相对平衡，从而保证红黑树的增删改查的时间复杂度最坏也能达到O(log N)。下面是红黑树最重要的5条性质，后面需要正常回来查看：

  • 1、每个节点要么是黑的，要么是红的
  • 2、根节点是黑的
  • 3、叶节点是黑的
  • 4、如果一个节点是红的，他的两个儿子节点都是黑的
  • 5、对于任一节点而言，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点
    学习笔记之数据库索引
    上图是一棵典型的红黑树，红黑树的5条特性确保了从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，使得整棵树大致上是平衡的。树上的增删改查操作的最坏情况时间都与树的高度成正比，所以红黑树在最坏情况下也是高效的。
    在红黑树中一般用黑的NIL节点表示叶节点，不包含值，只是标志该分支结束，有时候绘图中会直接省略。

2、B-树

B-Tree就是我们常说的B树，一定不要读成B减树，否则就很丢人了。B树是一种多路自平衡搜索树，它类似普通的二叉树，但是B书允许每个节点有更多的子节点。B树示意图如下：
学习笔记之数据库索引
B树的特点：

  • （1）所有键值分布在整个树中
  • （2）任何关键字出现且只出现在一个节点中
  • （3）搜索有可能在非叶子节点结束
  • （4）在关键字全集内做一次查找，性能逼近二分查找算法

3、B+树

B+树是B树的变体，也是一种多路平衡查找树，B+树的示意图为：
学习笔记之数据库索引
从图中也可以看到，B+树与B树的不同在于：

  • （1）所有关键字存储在叶子节点，非叶子节点不存储真正的data
  • （2）为所有叶子节点增加了一个链指针

4、B/B+树和红黑树区别

（1）为什么用B/B+树这种结构来实现索引呢？

红黑树等结构也可以用来实现索引，但是文件系统及数据库系统普遍使用B/B+树结构来实现索引。mysql是基于磁盘的数据库，索引是以索引文件的形式存在于磁盘中的，索引的查找过程就会涉及到磁盘IO(为什么涉及到磁盘IO请看文章后面的附加理解部分)消耗，磁盘IO的消耗相比较于内存IO的消耗要高好几个数量级，所以索引的组织结构要设计得在查找关键字时要尽量减少磁盘IO的次数。为什么要使用B/B+树，跟磁盘的存储原理有关。

局部性原理与磁盘预读：当一个数据被用到时，其附近的数据也通常会马上被使用，程序运行期间所需要的数据通常比较集中。

为了提升效率，要尽量减少磁盘IO的次数。实际过程中，磁盘并不是每次严格按需读取，而是每次都会预读。磁盘读取完需要的数据后，会按顺序再多读一部分数据到内存中。

（2）红黑树 和 b+树的用途有什么区别？

1.红黑树多用在内部排序，即全放在内存中的，STL的map和set的内部实现就是红黑树。

红黑树的目的，就是解决平衡树的增删起来比较麻烦的问题，红黑树，读取略逊于平衡树，增删强于平衡树，每次插入和删除的平均旋转次数应该是远小于平衡树。

2.B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。

(1)磁盘读写代价更低
树的非叶子结点里面没有数据，这样索引比较小，可以放在一个blcok（或者尽可能少的blcok）里面。避免了树形结构不断的向下查找，然后磁盘不停的寻道，读数据。这样的设计，可以降低io的次数。
(2)查询效率更加稳定
非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
(3)遍历所有的数据更方便
B+树只要遍历叶子节点就可以实现整棵树的遍历，而其他的树形结构 要中序遍历才可以访问所有的数据。

5、B-树和B+树区别

为什么使用 B+树？

  • （1）**非叶子节点不会带上指向记录的指针，这样，一个块中可以容纳更多的索引项，**一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。
  • （2）**叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。**具体的来讲，如何想扫描一次所有数据，对于b+树来说，可以从因为他们的叶子结点是连在一起的，所以可以横向的遍历过去。而对于b-树来说，就这能中序遍历了。

参考：
以B tree和B+ tree的区别来分析mysql索引实现：https://www.jianshu.com/p/0371c9569736
对B+树，B树，红黑树的理解：https://www.jianshu.com/p/86a1fd2d7406
图解红黑树：https://www.jianshu.com/p/0eaea4cc5619

四、MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。但是无论是MyISAM还是InnoDB，都采用了B+树的索引实现。

1、MyISAM索引实现

MyISAM使用B+树作为索引结构，叶结点的data域存放的是数据记录的地址。
学习笔记之数据库索引
这里设表一共有三列，假设我们以Col1为主键，则图8是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
学习笔记之数据库索引
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

2、InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
**第一个重大区别是InnoDB的数据文件本身就是索引文件。**从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
学习笔记之数据库索引
上图为InnoDB主索引（同时也是数据文件）的示意图，可以看到叶结点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
**第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。**换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：
学习笔记之数据库索引
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
拓展：
InnoDB行锁是通过索引上的索引项来实现的，这一点ＭySQL与Oracle不同，后者是通过在数据中对相应数据行加锁来实现的。InnoDB这种行锁实现特点意味者：只有通过索引条件检索数据，InnoDB才会使用行级锁，否则，InnoDB将使用表锁！

3、MyISAM和InnoDB区别

  MyISAM InnoDB
构成上的区别 每个MyISAM在磁盘上存储成三个文件。第一个文件的名字以表的名字开始，扩展名指出文件类型。
.frm文件存储表定义。
数据文件的扩展名为.MYD (MYData)。
索引文件的扩展名是.MYI (MYIndex)。		 基于磁盘的资源是InnoDB表空间数据文件和它的日志文件，InnoDB 表的大小只受限于操作系统文件的大小，一般为 2GB
事务处理上方面 MyISAM类型的表强调的是性能，其执行数度比InnoDB类型更快，但是不提供事务支持 InnoDB提供事务支持事务，外部键等高级数据库功能
SELECT,UPDATE,INSERT,Delete操作 如果执行大量的SELECT，MyISAM是更好的选择 1.如果你的数据执行大量的INSERT或UPDATE，出于性能方面的考虑，应该使用InnoDB表
2.DELETE FROM table时，InnoDB不会重新建立表，而是一行一行的删除。
3.LOAD TABLE FROM MASTER操作对InnoDB是不起作用的，解决方法是首先把InnoDB表改成MyISAM表，导入数据后再改成InnoDB表，但是对于使用的额外的InnoDB特性（例如外键）的表不适用
对AUTO_INCREMENT的操作 每表一个AUTO_INCREMEN列的内部处理。
MyISAM为INSERT和UPDATE操作自动更新这一列。这使得AUTO_INCREMENT列更快（至少10%）。在序列顶的值被删除之后就不能再利用。(当AUTO_INCREMENT列被定义为多列索引的最后一列，可以出现重使用从序列顶部删除的值的情况）。
AUTO_INCREMENT值可用ALTER TABLE或myisamch来重置
对于AUTO_INCREMENT类型的字段，InnoDB中必须包含只有该字段的索引，但是在MyISAM表中，可以和其他字段一起建立联合索引更好和更快的auto_increment处理		 如果你为一个表指定AUTO_INCREMENT列，在数据词典里的InnoDB表句柄包含一个名为自动增长计数器的计数器，它被用在为该列赋新值。
自动增长计数器仅被存储在主内存中，而不是存在磁盘上
关于该计算器的算法实现，请参考： AUTO_INCREMENT列在InnoDB里如何工作
表的具体行数 select count(*) from table,MyISAM只要简单的读出保存好的行数，注意的是，当count(*)语句包含 where条件时，两种表的操作是一样的 InnoDB 中不保存表的具体行数，也就是说，执行select count(*) from table时，InnoDB要扫描一遍整个表来计算有多少行
锁 表锁 提供行锁(locking on row level)，提供与 Oracle 类型一致的不加锁读取(non-locking read in SELECTs)，另外，InnoDB表的行锁也不是绝对的，如果在执行一个SQL语句时MySQL不能确定要扫描的范围，InnoDB表同样会锁全表，例如update table set num=1 where name like '%aaa%'

参考：
myisam和innodb索引实现的不同：https://www.jianshu.com/p/c3fb0b01c44d
http://blog.codinglabs.org/articles/theory-of-mysql-index.html

五、索引的几种运用场景

1、联合索引运用-最左匹配原则

CREATE TABLE `test` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `uId` int(10) unsigned NOT NULL,
  `chatId` smallint(5) unsigned NOT NULL,
  `tId` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `test_uId_chatId_tId` (`uId`,`chatId`,`tId`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8mb4;

在MySQL建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配，如上表建表语句中建了一个三个字段的联合索引test_uId_chatId_tId，联合索引test_uId_chatId_tId 实际建立了(uId)、(uId,chatId)、(uId,chatId,tId)三个索引。
SELECT * FROM test WHERE uId=“1” AND chatId=“2”;
上面这个查询语句执行时会依照最左前缀匹配原则，检索时会使用索引(uId,chatId)进行数据匹配。
注：
索引的字段可以是任意顺序的
例如：
SELECT * FROM test WHERE uId=“1” AND chatId=“2”;
SELECT * FROM test WHERE chatId=“2” AND uId=“1”;
这两个查询语句都会用到索引(uId,chatId)，uId、chatId两个字段，只是顺序不一样，查询条件一样，最后所查询的结果肯定是一样的，mysql查询优化器会判断纠正这条sql语句该以什么样的顺序执行效率最高，最后才生成真正的执行计划。

拓展：
对于联合索引(uId,chatId,tId)，查询语句SELECT * FROM test WHERE chatId=2;是否能够触发索引,当时面试官问我时我回答是不触发，实际上是触发索引的。
原因如下：
学习笔记之数据库索引
学习笔记之数据库索引
上述两个查询的explain结果中显示用到索引的情况类型是不一样的。可观察explain结果中的type字段，分别是：

  • type: index
    index：这种类型表示mysql会对整个该索引进行扫描，*通常发生在查询结果只包含索引字段时。*如上图SELECT * FROM test WHERE chatId=2;中*包含了id,uId,chatId,tId，而这四个字段id建了主键索引，uId,chatId,tId建了联合索引，正好符合index索引场景。
  • type: ref
    ref：这种类型表示mysql会根据特定的算法快速查找到某个符合条件的索引，而不是会对索引中每一个数据都进行一一的扫描判断，也就是所谓你平常理解的使用索引查询会更快的取出数据。而要想实现这种查找，索引却是有要求的，要实现这种能快速查找的算法，索引就要满足特定的数据结构。简单说，也就是索引字段的数据必须是有序的，才能实现这种类型的查找，才能利用到索引。

参考：
MySQL联合索引运用-最左匹配原则：https://www.jianshu.com/p/4c6d4c4a89c6
mysql索引最左匹配原则的理解：https://www.jianshu.com/p/46641d098a17

2、覆盖索引

覆盖索引（covering index）指一个查询语句的执行只用从索引中就能够取得，不必扫描表读取。也可以称之为实现了索引覆盖。
如果一个索引包含了（或覆盖了）满足查询语句中字段与条件的数据就叫做覆盖索引。
例如：对test_index表建立一个联合索引，包含id,name两列。查看下面sql的执行计划
explain select id ,name from test_index ;
学习笔记之数据库索引
执行另一个sql：
explain select id ,name ,email from test_index ;
学习笔记之数据库索引
优点：

  • 减少数据访问量和减少响应时间：索引条目通常小于数据行大小，只读取索引，极大减少数据访问量。
  • 减少I/O：索引按照列值顺序存储，索引对于I/O密集型的范围查询会比从磁盘随机读取每一行数据的I/O少很多。
  • 减少系统调用和降低开销：一些存储引擎如MyISAM在内存中只缓存索引，数据则依赖当前操作系统缓存，因此要访问数据需要一次系统调用。这可能导致严重的性能问题，尤其是那些系统调用占了数据访问中的最大开销的场景。
  • InnoDB避免二次查询：由于InnoDB的聚簇索引，覆盖索引对InnoDB特别有用。InnoDB的二级索引在叶子节点保存了行的主键值，所以如果二级主键查询能够覆盖索引，则可以避免对主键索引的二次查找。

无法使用覆盖索引查询情况：
1.select选择的字段中含有不在索引中的字段 ，即索引没有覆盖全部的列。
2.where条件中不能含有对索引进行like的操作。
例如：
学习笔记之数据库索引
参考：
MYSQL优化——索引覆盖：https://www.cnblogs.com/webph/p/6549285.html
mysql-覆盖索引：https://www.cnblogs.com/happyflyingpig/p/7662881.html

3、索引合并-Index merge

MySQL在 5.0版本中引入新特性：索引合并优化(Index merge optimization)，当查询中单张表可以使用多个索引时，同时扫描多个索引并将扫描结果进行合并。在表数据量有限的情况，性能提高明显。
该特新主要应用于以下三种场景：
1、 对OR语句求并集，如查询SELECT * FROM TB1 WHERE c1=“xxx” OR c2="“xxx"时，如果c1和c2列上分别有索引，可以按照c1和c2条件进行查询，再将查询结果合并（union）操作，得到最终结果
2、 对AND语句求交集，如查询SELECT * FROM TB1 WHERE c1=“xxx” AND c2=”“xxx"时，如果c1和c2列上分别有索引，可以按照c1和c2条件进行查询，再将查询结果取交集（intersect）操作，得到最终结果
3、 对AND和OR组合语句求结果
该新特性可以在一些场景中大幅度提升查询性能，但受限于MySQL糟糕的统计信息，也导致很多场景查询性能极差甚至导致数据库崩溃。以SELECT * FROM TB1 WHERE c1=“xxx” AND c2=”“xxx” 为例：如果表数据量大时候，分别以c1和c2都会返回大量的数据，然后求交集，此过程导致整条SQL需要消耗大量CPU和IO资源且相应时间超长。由于上述的问题，绝大多数的运维团队都会选择关闭该特性来避免执行异常。

参考：
https://www.jianshu.com/p/67b39af2f851

六、索引失效情况

1、is null，is not null无法使用索引。
2、mysql中使用!=或<>无法使用索引。
3、like以%开头的索引失效。注：（1）前缀没有%，后缀有%，索引有效；（2）前缀有%，但使用覆盖索引也能走index索引。
4、字符串不加单引号无法使用索引。
5、使用or无法使用索引。注：如果要用索引，则需要or条件中每个列都加上索引，采用索引合并优化解决。
6、在索引列上做操作（计算、函数、（自动或手动）类型转换）无法使用索引。
7、联合索引中不遵守最左前缀原则无法使用索引。

参考：
https://www.cnblogs.com/zjxiang/p/9160810.html
https://blog.csdn.net/student__software/article/details/82078786
https://blog.csdn.net/wuseyukui/article/details/72312574

七、mysql执行计划(explain)名称解析

1.id 表示执行的顺序，id越大越先执行，id一样的从上往下执行。
2.select_type 表示查询类型，通常有:

  • simple：表示不需要union操作或者不包含子查询的简单查询。
  • primary：表示最外层查询。
  • union：union操作中第二个及之后的查询。
  • dependent union：union操作中第二个及之后的查询，并且该查询依赖于外部查询。
  • subquery：子查询中的第一个查询。
  • dependent subquery：子查询中的第一个查询，并且该查询依赖于外部查询。
  • derived：派生表查询，既from字句中的子查询。
  • materialized：物化查询。
  • uncacheable subquery：无法被缓存的子查询，对外部查询的每一行都需要重新进行查询。
  • uncacheable union：union操作中第二个及之后的查询，并且该查询属于uncacheable subquery。

3.table 表名或者表的别名。
4.partitions 分区信息，非分区表为null。
5.type 访问类型，表示找到所查询数据的方法，也是本文重点介绍的属性。该属性的常见值如下，性能从差到好

  • ALL：全表扫描
  • index：索引全扫描 ，遍历索引树查询，通常发生在查询结果只包含索引字段时。
  • range：索引范围扫描，常用语<,<=,>=,between等操作
  • ref：使用非唯一索引扫描或唯一索引前缀扫描，返回单条记录，常出现在关联查询中
  • eq_ref：类似ref，区别在于使用的是唯一索引，使用主键的关联查询
  • const/system：单条记录，系统会把匹配行中的其他列作为常数处理，如主键或唯一索引查询
  • null ：MySQL不访问任何表或索引，直接返回结果，比如获取一个索引列的最大值或最小值。由于innodb采用B+树最为索引的物理结构，而B+树的叶子节点是顺序排列的，所以当查询索引的最大或最小值时，不需要遍历叶子节点，只需要拿到叶子节点头或者尾即可。

6.possible_keys 表示mysql此次查询中可能使用的索引。
7.key 表示mysql实际在此次查询中使用的索引。
8.key_len 表示mysql使用的索引的长度。该值越小越好。
9.**ref **表示连接查询的连接条件。
10.rows 表示mysql估计此次查询所需读取的行数。该值越小越好。
11.extra 表示mysql解决查询的其他信息，有几十种不同的值，该信息也是我们优化sql可以专注的一个值。下面列举几个常见的：

  • using index ：使用覆盖索引的时候就会出现
  • using where：在查找使用索引的情况下，需要回表去查询所需的数据
  • using index condition：查找使用了索引，但是需要回表查询数据
  • using index ; using where：查找使用了索引，但是需要的数据都在索引列中能找到，所以不需要回表查询数据

相关推荐