深入理解MySQL原理之二--如何建立高效索引

小鱼儿 2022-11-02 03:46 169阅读 0赞

# 一、前言 #

当数据库中存储大量数据(比如百万行)，并从中快速检索到我们所需要的记录，如果采用逐行扫描，从磁盘中读取数据并分析，很显然这是个非常糟糕的方案。实际上，生活中有很多类似的例子，比如我们要查某个字，不可能一页一页翻字典，而是根据笔画或者拼音先检索出所要找的字在哪一页，然后再翻到这一页看具体的解释。数据库也是一样，先根据"索引"检索出数据的位置，根据位置就能快速读取内容。

在这一章节，我们将重点介绍：

1、什么是B+树索引，B+树索引有哪些优点。

2、什么是聚簇索引和非聚簇索引，设计的目的是什么？

3、实际研发过程中，如何利用B+树的索引原理，优化索引，使其更加高效。

# 二、B+树索引 #

一提到MySQL的索引的数据结构，对MySQL有一定了解的都知道是B+树，这个答案算是部分正确，实际上还有其他的数据结构，比如哈希索引，全文索引，只不过我们常用的是B+树。本章节我们重点谈下InnoDB的B+树索引，既然有B+树，那么必定有B树(balance tree,注意没有B-树)。我们先看下B树，B+树的数据结构，两者有什么不同，MySQL为何要用B+树。

## 1、数据结构 ##

B树是一颗多叉的平衡树。对于一个m阶的树，定义如下：

(1)、根结点至少有两个子女。  
(2)、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1，┌m/2┐表示向上取整。根节点的关键字个数为1<=j<m-1。  
(3)、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m 。  
(4)、所有的叶子结点都位于同一层。

以上定义理解比较费劲，我们来看个实例，以5阶的B数为例，根节点关键字范围1<=k<=4，非根节点关键字范围2<=k<=4。

以18,70,50,40,22,23,25,39构建5阶的B树为例。构建的过程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70][]

我们看下B树的特点：

(1)、每层的关键字都是从小到大顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。比如23，它的左子树都小于它(18,22)，右子树都大于它(25,39)。

(2)、所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。

(3)、每个节点都存有索引和数据，也就是对应的key和value，即全量数据。(这条如果不理解，可以结合后面MySQL索引再来理解)。

总结一下，B树是一个**平衡的多叉树，数据存储是有序的，每个节点保存全量数据**。

接下来，我们在看下B+树的数据结构。

**相同点**：

1、根节点至少一个元素。

2、非根节点元素范围：┌m/2┐ - 1 <=k <= m-1。┌m/2┐表示向上取整。

**不同点**：

1、非叶子节点，只存储索引(key)，而不存储数据(value)，叶子节点存储所有的数据。

2、非叶子节点，所有的关键字(key)从左到有右，按照从小到大顺序排列，每个key的左子树所有的key值都小于它，右子树的所有key值都**大于等于**它。

3、叶子结点，每个叶子节点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

4、父节点存有右孩子树的第一个元素的索引。

同样，还采用上面B树的例子，看下其B+树结构，并进行比较。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 1][]

总结一下，B+树是一个**平衡的多叉树，数据存储是有序的，非叶节点仅保存索引，叶子节点保存全量数据，相邻叶子节点之间通过指针链接。**

MySQL什么选择B+树，而不是B树？又是如何构建B+树索引的？请继续

## 2、索引 ##

有一张user表，有三个字段，分别为userid，username，sex。如下表

<table style="width:229px;"> 
 <tbody> 
  <tr> 
   <td style="width:75px;">userid</td> 
   <td style="width:87px;">username</td> 
   <td style="width:63px;">sex</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">18</td> 
   <td style="width:87px;">a1</td> 
   <td style="width:63px;">0</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">70</td> 
   <td style="width:87px;">a2</td> 
   <td style="width:63px;">0</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">50</td> 
   <td style="width:87px;">a3</td> 
   <td style="width:63px;">0</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">40</td> 
   <td style="width:87px;">a4</td> 
   <td style="width:63px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">22</td> 
   <td style="width:87px;">a5</td> 
   <td style="width:63px;">0</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">23</td> 
   <td style="width:87px;">a6</td> 
   <td style="width:63px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">25</td> 
   <td style="width:87px;">a7</td> 
   <td style="width:63px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:75px;">39</td> 
   <td style="width:87px;">a8</td> 
   <td style="width:63px;">1</td> 
  </tr> 
 </tbody> 
</table>

假设构建以userid为主键索引。

B树索引如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 2][]

B+数索引如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 3][]

再来比较的两者索引的不同点：

1、B树非叶节点，即保存索引key值，又保存数据；B+树非叶节点，仅保存索引key值，数据统一存储到叶子节点。innodb页的默认大小是16KB，如果不存储数据，就能存储更多的key值，阶数就是做的更大，树就可以更矮更胖，查找磁盘的IO次数就会减少，效率就会提高。

2、B+树的叶子节点的数据页通过双向链表按照顺序链接，并保存全量的数据。这就使得排序查找，范围查找，分组查找变的简单，效率更高，但对于B树是无法做到这点的。

3、B+树每次检索所需要进行磁盘IO的次数是同样的，性能更加稳定；而对于B树，根据节点所在的位置，读盘次数从1-m不等。

所以对于MySQL的索引，B+树更有优势。

# 三、聚簇索引与非聚簇索引 #

上面介绍我们MySQL的B+索引的原理，再来看什么是聚簇索引，聚簇索引并不是一种索引数据结构，而是一种存储方式。

Innodb表中都会存在一个主键，如果我们不创建，那么系统会选择一个唯一的非空索引代替，如果也没有这样的索引，会隐式的创建一个主键，总之，必须有个主键。主键的索引就是聚簇索引，其主要的特点**就是叶子节点上保存全部记录数据**。比如上面的示例中，userid为主键索引，那么该索引就是聚簇索引，其叶子节点上保存了对应的userid，username，sex三个字段值。

除了主键索引，其他都是非聚簇索引，它的特点是叶子节点上仅保存主键的值，而不是记录数据。比如以"username"为索引，查询sql"select \* from user where username='a3'"

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 4][]

最后在叶节点查到记录是主键值50，再根据主键值到聚簇索引查询完整的数据，进行二次查询，俗称"**回表**"。(需要注意的是，如果是"select userid,username from user where username='a3'",是不需要回表的，因为非聚簇索引树上已经有需要查询的数据了)。

下面我们就来思考几个问题：

1、为什么要用聚簇索引，它有什么优势？

2、非聚簇索引的叶子节点为什么不保存行指针，或者行记录，而保存主键值。

第一个问题，在《高性能MySQL》中提了几点，总结起来就是，利用聚簇索引，使用主键访问，效率更高。这个比较好理解，数据就是叶子节点上，减少了IO的访问。对于聚簇索引，索引即数据，数据即索引。

第二个问题，因为B+树是顺序的，在数据插入时，聚簇索引的叶子节点的页(行数据页)可能会"裂变",如果非聚簇索引的叶节点记录的是行指针，那么也得更新，但是记录主键的值就不需要更新。至于为何不保存行记录数据，因为聚簇索引已经保存了行记录，其他索引就没有必要再保存行记录数据了，否则导致存储空间的浪费。

# 四、高性能索引策略 #

上面介绍了MySQL的Innodb索引的原理，接下来我们看下这对我们建立索引有哪些影响，或者说如何利用其原理特点建立高效的索引。

## 1、主键索引 ##

主键索引为聚簇索引，其他的索引(非聚簇索引)都是依赖该索引二次检索，所以主键索引对于整个索引的影响很大的。回顾下聚簇索引的特点:

(1)索引数据是有序的(B+树特点)

(2)叶子节点存储行数据

在数据插入时，顺序插入对于磁盘来说效率是最高的，MySQL建议**主键索引列数据建议采用自增长**，特别要避免一些UUID，hashcode，随机数之类的数据列作为主键，这样会引起随机插入，并发写性能会下降。

## 2、区分度 ##

面对表中几十个字段，在不考虑查询条件等因素情况下， 有没有快速的判断标准，哪些适合做索引，哪些不适合？

MySQL提出了一个区分度的概念，即count(distinct col)/count(\*)，区分度越大，表示需要扫描的次数越少，原则上适合作为索引,，比如主键索引的区分度是1；而类似性别字段在大数据的时候，区分度为0，就不适合作为索引字段。但是这个也仅是原则性的，还得看具体的应用场景，一般大于0.1就认为适合。

## 3、多列索引 ##

对于表的一次查询，只会使用到一个索引，所以对于where的联合查询条件，一般情况下，MySQL建议使用多列索引，而不是建立多个独立的索引。比如建立(a,b,c,d)联合索引，在检索时，先检索a，匹配后在检索b，依次往下。

按这个规则，多列索引存在**最左前缀匹配原则**。我们看以下几种情况:

1、a=1 and b=2 and **d=3 and c=5**,可以使用该索引(a,b,c,d)。虽然c,d的顺序与索引顺序不一致，但是优化器会帮我们调整。**in和=都可以乱序**。

2、a=1 and b=2 **and d=3**，可以利用该索引的(a,b)，但无法使用(c,d)。

3、a=1 and **b>2** and c=5 and d=3，仅可以使用(a,b)。**当遇到范围查询(>、<、between、like)就会停止匹配。**

4、a=1 **or** b=2 **or** c=5 **or** d=3,不可以使用(a,b,c,d)。对于or条件，很难利用索引优化，一般采用union 或者in替换。

## 3、覆盖索引 ##

前面我们介绍了"回表"，回表会导致二次检索，那么有没有方法能一次检索，在索引上就能获得所有的数据，从而避免回表。我们来还看上面的例子"select \* from user where username='a3'"，创建联合索引(username,sex)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 5][]

可以看到所有的数据都在此索引上，无需回表查询，这就是"覆盖索引"，即将select\[col1 ..col2\]与where\[col1...col2\]，所有的列做联合索引，从而避免回表查询。

覆盖索引的好处是显而易见的，但是很多时候受限于索引自身限制，是无法实现的，比如上面提到的范围查询，导致索引无法利用，“覆盖”也就无存谈起了。

## 4、索引扫描做排序 ##

上一篇中，我们谈到了利用索引做排序优化，那么在本章节中，我们结合索引的原理再看下。B+树是有序的，如果能用索引扫描做排序，那么效率会大大高于文件排序。与where的条件一样，也是要满足最左前缀匹配原则。比如建立(a,b,c,d)联合索引，我们看以下几种情况：

1、where a=1 order by b,c,可以使用索引扫描排序。

2、where a>1 order by a,b，可以使用索引扫描排序

3、where a=1 order by b asc,c desc,不可以使用索引扫描排序。使用不同的排序方向

4、where a>1 order by b,c，不可以使用索引扫描排序。范围查询导致索引失效。

5、where a>1 order by c ，不可以使用索引扫描排序，不满足最左前缀匹配原则。

6、where a in(1,2) order by b,不可以使用索引扫描排序，a是范围查询。

**在大数据量的情况下，文件排序的效率非常低，尽量使用联合索引或者覆盖索引来做排序**，如无法做到，考虑从应用层代码优化，比如上面的where a in(1,2) order by b,考虑拆成两个SQL，然后在应用层实现排序。

# 五、总结 #

以上我们了解了B+树数据结构，并介绍了MySQL如何使用B+树构建索引，并从索引原理角度，分析和介绍了开发过程中，创建索引一些策略。

**Q:什么是B+树索引，B+树索引有哪些优点？**

**A:**B+树是一棵多叉的平衡树，在B树的基础上做了优化。B+树天然具有顺序性特点，同时与B树相比，在树的深度，搜索稳定性，范围查找上都具有优势。

**Q:什么是聚簇索引和非聚簇索引，设计的目的是什么？**

**A:**聚簇索引就是主键索引，非聚簇索引就是除主键索引外的其他索引。

聚簇索引的叶节点上保存行记录数据，非聚簇索引叶节点上保存主键值。聚簇索引使用主键提升查询效率，非聚簇索引在减少存储空间的同时，又能配合使用聚簇索引提升性能。

**Q:实际研发过程中，如何利用B+树的索引原理，优化索引，使其更加高效。**

A:我们再来总结这些策略：

1、最左前缀匹配原则，是B+数索引非常重要的原则，MySQL会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配。

2、尽量选择区分度高的列作为索引。

3、尽量的扩展索引，不要新建索引，根据具体场景，使用覆盖索引效率会更高。

4、尽量使用联合索引或者覆盖索引做排序，避免使用文件排序

5、索引列不能参与计算，保持列“干净”，否则引起索引失效。

总之，对于一些慢sql，通过explain查找出问题所在，优先从索引方面着手解决，然后再考虑应用层优化，不拘泥一招一式，要有组合拳，以解决问题为主要目的。

附：

[深入理解MySQL原理之一--如何提升查询SQL的性能][MySQL_--_SQL]

[深入理解MySQL原理之二--如何建立高效索引][MySQL_--]

[深入理解MySQL原理之三--如何实现事务与分库分表][MySQL_-- 1]

[深入理解MySQL原理之四--如何实现高可用][MySQL_-- 2]

[深入理解MySQL原理之五--如何高效利用InnoDB存储引擎][MySQL_--_InnoDB]

[深入理解MySQL原理之六--核心算法有哪些][MySQL_-- 3]

[深入理解MySQL原理之七--云原生时代将何去何从][MySQL_-- 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70]: /images/20221024/6019124061464da286995e6f9173b288.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 1]: /images/20221024/abaa2b51a443429789e89ead01053df7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 2]: /images/20221024/178b9935344945a183afafa9eefc6874.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 3]: /images/20221024/30769ab5d615485ab26b798dedf44d4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 4]: /images/20221024/8074ac289f4f4bcf800eb6c5bf2d068c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RjeTgz_size_16_color_FFFFFF_t_70 5]: /images/20221024/7fffdf97f07641f5aed61937666dc52d.png
[MySQL_--_SQL]: https://blog.csdn.net/tcy83/article/details/108546004
[MySQL_--]: https://blog.csdn.net/tcy83/article/details/114048168
[MySQL_-- 1]: https://blog.csdn.net/tcy83/article/details/114848104
[MySQL_-- 2]: https://blog.csdn.net/tcy83/article/details/115453583
[MySQL_--_InnoDB]: https://blog.csdn.net/tcy83/article/details/117407724
[MySQL_-- 3]: https://blog.csdn.net/tcy83/article/details/117918385
[MySQL_-- 4]: https://blog.csdn.net/tcy83/article/details/119088747