• 索引的本质
• 数据结构与算法
• B+树深?剖析
• 索引的使?

索引的本质

在?产环境中，随着数据量不断的增?，SQL执?速度会越来越慢，常?的?段就是通过索引来提升查询速度，那么究竟为什么要添加索引？应该如何正确添加索引？本套课程将以MySQL为例，从索引的底层进?分析，?起探究索引相关的?系列问题。

MySQL官?对索引的定义为：索引（Index）是帮助MySQL?效获取数据的数据结构（有序）。所以，就可以得到索引的本质：索引是有序的数据结构。

环境

本套课程以MySQL5.7为例讲解，使?docker进?部署：

docker run --name mysql-5.7 -e MYSQL_ROOT_PASSWORD=root -d -p 13306:3306 -v

mysql-5.7-data:/var/lib/mysql -v mysql-5.7-conf:/etc/mysql/conf.d mysql:5.7.31

索引?件

在MySQL中，索引实际上存储在?件中的，其位置与数据库数据?件在相同的?录中。

-- 创建测试表

CREATE TABLE `tb_user` (

`id` int(11) NOT NULL AUTO_INCREMENT,

`username` varchar(20) DEFAULT NULL,

`password` varchar(20) DEFAULT NULL,

`created` datetime DEFAULT NULL,

PRIMARY KEY (`id`),

KEY `username` (`username`) USING BTREE

) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8;

CREATE TABLE `tb_user2` (

`id` int(11) NOT NULL AUTO_INCREMENT,

`username` varchar(20) DEFAULT NULL,

`password` varchar(20) DEFAULT NULL,

`created` datetime DEFAULT NULL,

PRIMARY KEY (`id`)

) ENGINE=MyISAM DEFAULT CHARSET=utf8;

查看数据库?件，路径：/var/lib/docker/volumes/mysql-5.7-data/_data/

-rw-r-----. 1 polkitd input 61 9? 2 11:31 db.opt

-rw-r-----. 1 polkitd input 8668 9? 2 11:36 tb_user2.frm #表结构?件

-rw-r-----. 1 polkitd input 0 9? 2 11:36 tb_user2.MYD #MyISAM引擎类型的

表数据?件

-rw-r-----. 1 polkitd input 1024 9? 2 11:36 tb_user2.MYI #MyISAM引擎类型的

索引?件

-rw-r-----. 1 polkitd input 8668 9? 2 11:33 tb_user.frm #表结构?件

-rw-r-----. 1 polkitd input 114688 9? 2 11:34 tb_user.ibd #InnoDB的表空间?

件，?于存储数据以及索引?件

索引示例

此示例中，在左侧表示的2列数据，其中最左侧的为数据的物理地址，真实的地址可能并不是连续的地址。右侧是根据col2建?的索引结构，先把此结构看作是?叉树结构，每个节点分别包含索引键值和?个指向对应数据记录物理地址的指针。

查找数据：

• 在没有索引的情况下，会全表扫描数据，其时间复杂度为：O(n)，值为：7
• 在索引（?叉树）情况下，查找数据的时间复杂度为：O(log2n)，值为： 2.80735492
• 可?，基于索引的查询要更快?些。

需要注意的是，数据库系统?乎没有使??叉查找树、红?树实现的，在MySQL中是使?的是B+Tree。

数据结构与算法

算法的动态演示地址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

?分查找法

?分法查找，也称为折半法，是?种在有序数组中查找特定元素的搜索算法。

?分法查找的思路如下：

• ?先，从数组的中间元素开始搜索，如果该元素正好是?标元素，则搜索过程结束，否则执?下?步。
• 如果?标元素?于/?于中间元素，则在数组?于/?于中间元素的那?半区域查找，然后重复步骤1的操作。
• 如果某?步数组为空，则表示找不到?标元素。

?叉树

?叉树（binary tree）是指树中节点的度不?于2的有序树，它是?种最简单且最重要的树。如下图：

?般情况下，?叉树查找效率要?于顺序查找，但是也有特殊情况如下：

在该树中，如果查找8元素，其执?效率和顺序查找差不多了。为了解决这个问题，就需要将?叉数做平衡操作。

平衡?叉树

平衡?叉树（Balanced Binary Tree）?被称为AVL树，且具有以下性质：它是?棵空树或它的左右两个?树的?度差的绝对值不超过1，并且左右两个?树都是?棵平衡?叉树。

这个?案很好的解决了?叉查找树退化成链表的问题，把插?，查找，删除的时间复杂度最好情况和最坏情况都维持在O(log2N)。但是频繁旋转会使插?和删除牺牲掉O(log2N)左右的时间，不过相对?叉查找树来说，时间上稳定了很多。

红?树

红?树是?种平衡?叉查找树的变体，它的左右?树?差有可能?于 1，所以红?树不是严格意义上的平衡?叉树（AVL），但对之进?平衡的代价较低 。

由于每?颗红?树都是?颗?叉排序树，因此，在对红?树进?查找时，可以采?运?于普通?叉排序树上的查找算法，在查找过程中不需要颜?信息。

特征

• 节点是红?或??。
• 根节点是??。
• 所有叶?都是??。（叶?是NUIL节点）
• 每个红?节点的两个?节点都是??。（从每个叶?到根的所有路径上不能有两个连续的红?节点）
• 从任?节点到其每个叶?的所有路径都包含相同数?的??节点。

B-Tree

B-Tree是为了磁盘或其它存储设备?设计的?种多叉平衡查找树，相对于?叉树，B-Tree每个内节点有多个分?，即多叉。

B-Tree中的2个概念：

• 度数：在树中，每个节点的?节点（?树）的个数就称为该节点的度（degree）。
• 阶数：定义为?个节点的?节点数?的最?值。多个分?，即多叉。

m阶B-Tree满?以下条件：

• 每个节点最多拥有m个?树
• 根节点?少有2个?树
• 分?节点?少拥有m/2颗?树（除根节点和叶?节点外都是分?节点）
• 所有叶?节点都在同?层、每个节点最多可以有m-1个key，并且以升序排列
• 每个?叶?节点由n-1个key和n个指针组成，key和指针互相间隔，节点两端是指针

实际上，每个节点除了键值以外还包含数据，如下：

如果选?B-Tree作为索引存储的话（?如：MongoDB），每?个节点包含指针、数据都存储到?个磁盘块中（NTFS?件系统中，默认8个扇区组成?个簇，??为4KB）：

B-Tree相对较?叉树的优势在于，?次读取?个磁盘块数据中包含了多个key数据，这样就可以在内存中做?较操作，减少了磁盘IO的操作。

插?或者删除元素都会导致节点发?裂变反应，有时候会?常麻烦，但正因为如此才让B树能够始终保持多路平衡，这也是B树?身的?个优势：?平衡；

B树主要应?于?件系统以及部分数据库索引，如MongoDB，?部分关系型数据库索引则是使?B+树实现

B+Tree

这是?个3阶的B+Tree示意图

B+Tree是在B-Tree基础上的?种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是?B+Tree实现其索引结构。

B-Tree结构中可以看到每个节点中不仅包含数据的key值，还有data值。?每?个块的存储空间是有限的，如果data数据较?时将会导致每个节点（即?个块）能存储的key的数量很?，当存储的数据量很?时同样会导致B-Tree的深度较?，增?查询时的磁盘I/O次数，进?影响查询效率。

在B+Tree中，所有数据记录节点都是按照键值??顺序存放在同?层的叶?节点上，??叶?节点上只存储key值信息，这样可以??加?每个节点存储的key值数量，降低B+Tree的?度。

B+Tree相对于B-Tree有?点不同：

• ?叶?节点只存储键值信息。
• 所有叶?节点之间都有?个链指针。
• 数据记录都存放在叶?节点中。

在B+Tree中，所有叶?节点（即数据节点）之间是?种链式环结构。因此可以对B+Tree进?两种查找运算：?种是对于主键的范围查找和分?查找，另?种是从根节点开始，进?随机查找。

B+树深?剖析

MySQL索引为什么要使?B+树

?先需要明确的是，B树或B+树要??叉树更适合作为索引存储，因为B树中的节点可以存储多个数据，从?就可以减少树的?度，也就减少了提升了查找性能。

那么在MySQL中为什么选择B+树?不选择使?B树呢？

主要原因体现在3个??：

• B+树的磁盘读写代价更低

B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更?，如果把所有同?内部节点的关键字存放在同?盘块中，那么盘块所能容纳的关键字数量也越多，?次性读?内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

• B+树的查询效率更加稳定

由于?终节点并不是最终指向?件内容的节点，?只是叶?节点中关键字的索引。所以任何关键字的查找必须??条从根节点到叶?节点的路。所有关键字查询的路径?度相同，导致每?个数据的查询效率相当。

• 由于B+树的数据都存储在叶?节点中，分?节点均为索引，?便扫库，只需要扫?遍叶?节点即可，但是B树因为其分?节点同样存储着数据，我们要找到具体的数据，需要从根节点按序开始扫描，所以B+树更加适合在区间查询的情况，所以通常B+树?于数据库索引。

MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现?式是不同的，下?我们针对MyISAM和InnoDB两个存储引擎的索引实现?式进?讨论学习。

MyISAM索引实现

MyISAM引擎使?B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

这?设表?共有三列，假设我们以Col1为主键，上图是?个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引?件仅仅保存数据记录的地址，在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯?的，?辅助索引的key可以重复。

如果我们在Col2上建??个辅助索引，则此索引的结构如下图所示

同样也是?颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为?先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引?式也叫做“?聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

InnoDB中的索引结构与MyISAM的索引结构有很?的不同。

第?个重?区别是InnoDB的数据?件本身就是索引?件。在MyISAM中，索引?件和数据?件是分离的，索引?件仅保存数据记录的地址。?在InnoDB中，表数据?件本身就是按B+Tree组织的?个索引结构，这棵树的叶节点data域保存了完整的数据记录，这个索引的key是数据表的主键，所以InnoDB表数据?件本身就是主索引。

从图中可以看到，叶?节点包含了完整的数据记录。这种索引叫做聚集索引。

因为InnoDB的数据?件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没

有），如果没有显式指定，则MySQL系统会?动选择?个可以唯?标识数据记录的列作为主键，如果不存在这种列，则MySQL?动为InnoDB表?成?个隐含字段作为主键，这个字段?度为6个字节，类型为?整形。（?试考题）

第?个与MyISAM索引的不同是，InnoDB的辅助索引data域存储相应记录主键的值?不是地址。换句话说，InnoDB的所有辅助索引都引?主键作为data域。例如，下图为定义在Col3上的?个辅助索引：

这?以英?字符的ASCII码作为?较准则。聚集索引这种实现?式使得按主键的搜索?分?效，但是辅助索引搜索需要检索两遍索引：?先检索辅助索引获得主键，然后?主键到主索引中检索获得记录。

InnoDB的B+ 树索引的特点是?扇出性，因此?般树的?度为2~4层，这样我们在查找?条记录时只?I/O 2~4次。当前机械硬盘每秒?少100次I/O/s，因此查询时间只需0.02~0.04s。

索引的使?

主键索引

在Innodb存储引擎中，每张表都会有主键，数据按照主键顺序组织存放，如果表定义时没有显式定义主键，则会按照以下?式选择或创建主键：

• 先判断表中是否有"?空的唯?索引"，如果有

1. 如果仅有?条"?空唯?索引"，则该索引为主键

2. 如果有多条"?空唯?索引"，根据索引索引的先后顺序，选择第?个定义的?空唯?索引为主键。

• 如果表中?"?空唯?索引"，则?动创建?个6字节??的指针作为主键，但是该主键是不能被查询的

在Innodb中，建议使??增id作为表的主键，这样有利于数据在底层的顺序存储，如果对于分表存储的数据，可以设置不同的步?解决或者使?第三?的代理框架解决。

联合索引

联合索引就是将表中的多个列?起进?索引，需要注意的是，联合索引是有顺序的，?如：A、B、C列的索引与A、C、B列的索引是不?样的

底层数据结构

联合索引的底层结构也是基于B+树的，其结构示意图如下

InnoDB会使?主键索引在B+树维护索引和数据?件，然后我们创建了?个联合索引（index_code,surname,name）也会?成?个索引树，同样是B+树的结构，只不过它的data部分存储的是联合索引所在?的主键值。

对于联合索引来说只不过?单值索引多了?列，?这些索引列全都出现在索引树上。对于联合索引，存储引擎会?先根据第?个索引列排序，如上图中第?个索引列，如：L、L、L、Q、M、W、Z、Z 是根据英?字?正序排序的；

如果第?列相等则再根据第?列排序，依次类推就构成了上图的索引树，如：L lei jun 、L li si、L liu hulan等。

联合索引的执?过程如下：

?先从根节点开始查找，根节点?般是常驻内存中的，第?个列为index_code，其值为：M，在L与W之间，会继续向?节点查询：

在查找到?节点后，将?节点数据从磁盘加载到内存中，采??分法进?查找，找到M ma yun数据符合条件，再继续查找?节点，读取到?节点中的data数据，其数据就是这条记录的主键，然后再通过主键索引查询数据，最终将在主键索引中查询到数据：

最左前缀原则

在使?联合索引时，必须按照索引的顺序查询，例如：

• 通过索引编号+姓+名就能定位到?机号，因为在索引结构中是排好序的
• 如果没有使?索引编号，那么整体来看就是混乱?序的，就?法使?排好序的索引，所以索引就不会?效

这就是最左前缀原则

EXPLAIN

使?EXPLAIN可以查看SQL语句的执?计划，从?可以知道SQL的瓶颈在哪?，就可以有针对性的进?优化了。

?法：

覆盖索引与回表查询

• 什么是回表查询？

先定位主键值，再定位?记录，它的性能较扫?遍索引树更低，这就是回表查询。

• 什么是覆盖索引？

只需要在?棵索引树上就能获取SQL所需的所有列数据，?需回表，速度更快