一文带你了解MySQL之B+树索引的原理-慈云数据

前言

学完前面我们讲解了InnoDB数据页的7个组成部分，知道了各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。所以我们画一个简单的关系示意图如下：

在这里插入图片描述

其中页1、页2、页3…页n这些页可以不在物理结构上相连，只用通过双向链表相关联即可。

之前一直听说，给数据库创建索引，可以提高查询性能，但是索引到底是个啥，又是怎样工作的，今天的就来学习InnoDB存储引擎的B+树索引

一、没有索引的查找
- 1.1 一个页中查找
- 1.2 在很多页中查找
- 二、索引
- - 2.1 一个简单的索引方案
  - 2.2 InnoDB中的索引方案
  - 三、聚簇索引（Clustered Index）
  - 四、二级索引（Secondary Index）
  - 五、联合索引（复合索引）
  - 六、InnoDB的B+树索引的注意事项
  - - 6.1 根页面永不动窝
    - 6.2 内节点中目录项记录的唯一性
    - 6.3 一个页面最少存储2条记录
    - 七、MyISAM中的索引方案简单介绍
    - 八、MySQL中创建和删除索引的语句
    - 九、小结
      一、没有索引的查找
      
      在正式的学习索引之前，我们需要了解一下没有索引的时候是怎么查找记录的，为了方便理解，我们只用搜索条件为对某个列精确匹配（精确匹配，就是搜索条件中用等于=连接起的表达式）做个案例，就像下面这种语句：
```
select[列名列表] from 表名 where 列名 = xxx;
```
      1.1 一个页中查找
      
      我们知道一个数据页的大小为16KB（16384字节），除去页中必须的元数据信息需要一部分存储空间之外，还会剩下很多空间来存放我们的User Records。假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：
      - 已主键为搜索条件
        在页目录中使用二分法快速定位到对应的槽（Slot），然后再遍历该槽对应分组中的记录即可快速找到指定的记录
      - 以其他列作为搜索条件
        对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
        
        1.2 在很多页中查找
        
        大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
        
        定位到记录所在的页。
        从所在的页中查找相应的记录。
        在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那要等到猴年马月才能等到查找结果。
        
        所以，索引闪亮登场。
        
        二、索引
        
        为了方便展示，我们先创建一张表：
        
        mysql> create table demo6(c1 int primary key,c2 int,c3 char(1)) row_format=compact; Query OK, 0 rows affected (0.02 sec)
        
        这个新建的demo6表中有2个int类型的列，1个char(1)类型的列，而且我们规定了c1列为主键，这个表使用Compact行格式来实际存储记录的。为了方便理解索引，我们对demo6表的行格式示意图做了简化：
        
        再来回顾一下展示的这几部分的具体含义：
        
        record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、2表示最小记录、3表示最大记录、1我们还没用过，马上就会说到
        next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便理解，都用箭头来表明下一条记录是谁
        各个列的值：这里只记录在demo6表中的三个列，分别是c1 、c2和c3
        其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
        我们再来对示意图做一下调整，将记录格式示意图的其他信息去掉并把它竖起来的效果就是这样：
        
        把一些记录放到页里面的示意图如下（见颜色知其意哈）：
        
        2.1 一个简单的索引方案
        
        回到正题，根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？还记得我们为根据主键值快速定位一条记录在页中的位置而设立的页目录么？我们也可以想办法为快速定位记录所在的数据页而建立一个别的目录，建这个目录必须完成下边这些事儿：
        
        第一：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
        
        我们这里需要做一个假设：假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后我们向demo6表插入3条记录：
        
        mysql> insert into demo6 values(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y'); Query OK, 3 rows affected (0.01 sec) Records: 3 Duplicates: 0 Warnings: 0
        
        那么这些记录已经按照主键值的大小串联成一个单向链表了，如图所示：
        
        从图中可以看出来，demo6表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入1条记录：
        
        mysql> insert into demo6 values(4, 4, 'a'); Query OK, 1 row affected (0.01 sec)
        
        页10最多只能放3条记录，所以我们不得不再分配一个新页
        
        新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。
        
        页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：
        
        将主键值为5的记录移到页28
        
        将主键为4的插入到页10
        
        这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。
        
        第二：给所有的页建立一个目录项
        
        由于数据页的编号可能并不是连续的，所以在向demo6表中插入许多条记录后，可能是这样的效果：
        
        因为这些16KB的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：
        
        页的用户记录中最小的主键值，我们用key 来表示
        页号，我们用page_no表示
        所以我们上边几个页做好的目录就像这个样子：
        
        以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为20的记录，具体查找过程分两步：
        
        先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为12