[数据结构与算法]MySQL索引详解

索引

简介

• MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。索引是一种用于快速查询和检索数据的数据结构
• 一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上
• 我们平常所说的索引，如果没有特别指明，都是指B树(多路搜索树，并不一定是二叉的)结构组织的索引。其中聚集索引，次要索引，覆盖索引，复合索引，前缀索引，唯一索引默认都是使用B+树索引，统称索引。当然，除了B+树这种类型的索引之外，还有哈稀索引(hash index)等。

索引的作用就相当于目录的作用。目录已经按一定的规则把字排好序了，在目录上查找相当于先找到字的内存地址，然后通过内存地址直接能快速的找到那个字，不需要一页一页找。

优缺点

优点

• 大大加快检索数据的效率，同时也大大减少检索的数据量，降低数据库的IO成本
• 通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗
• 创建唯一性索引，可以保证数据库表中每一行数据的唯一性

缺点

• 索引能提高查询的速度，但也会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存索引文件每次更新添加了索引列的字段，调整因为更新所带来的键值变化后的索引信息
• 创建索引和维护索引需要一定的时间、空间成本
• 实际上**索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录，所以索引列也是要占用空间的，索引需要使用物理文件存储，也会耗费一定空间**

使用索引一定能提高查询性能吗?

大多数情况下，索引查询都是比全表扫描要快的。但是如果数据库的数据量不大，那么使用索引的提升并不大，而且耗费空间。

哪些情况需要创建索引

1. 主键自动建立唯一索引
2. 频繁作为查询条件的字段应该创建索引(where 后面的语句)
3. 查询中与其它表关联的字段，外键关系建立索引
4. 单键/组合索引的选择问题，who？(在高并发下倾向创建组合索引)
5. 查询中排序的字段，排序字段若通过索引去访问将大大提高排序速度
6. 查询中统计或者分组字段

哪些情况不需要创建索引

1. 表记录太少
2. 经常增删改的表，Why:提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。
   因为更新表时，MySQL不仅要保存数据，还要保存一下索引文件
3. Where条件里用不到的字段不创建索引
4. 数据重复且分布平均的表字段，
   注意，如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。
   • why？ 重复的内容太多就不需要排序

底层数据结构

前言

B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+树即由这些树逐步优化而来。

二叉查找树

具有以下性质：

• 左子树的值小于根的值，右子树的值大于根的值
• 深度为n的节点的查找次数为n，深度为1的节点的查找次数为1，深度为2的查找次数为2。

二叉查找树可以任意地构造，同样是2,3,5,6,7,8这六个数字，也可以按照下图的方式来构造：

但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树

平衡二叉树

平衡二叉树（AVL Tree）：

• 在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1

实例

下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差<=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1；

如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：

这四种失去平衡的姿态都有各自的定义：

• LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。

• RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。

• LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。

• RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。

==AVL树失去平衡之后，可以通过旋转使其恢复平衡。==下面分别介绍四种失去平衡的情况下对应的旋转方法。

LL的旋转。LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：

1. 将根节点的左孩子作为新根节点。
2. 将新根节点的右孩子作为原根节点的左孩子。
3. 将原根节点作为新根节点的右孩子。

LL旋转示意图如下：

RR的旋转：RR失去平衡的情况下，旋转方法与LL旋转对称，步骤如下：

1. 将根节点的右孩子作为新根节点。
2. 将新根节点的左孩子作为原根节点的右孩子。
3. 将原根节点作为新根节点的左孩子。

RR旋转示意图如下：

LR的旋转：LR失去平衡的情况下，需要进行两次旋转，步骤如下：

1. 围绕根节点的左孩子进行RR旋转。
2. 围绕根节点进行LL旋转。

LR的旋转示意图如下：

RL的旋转：RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称，步骤如下：

1. 围绕根节点的右孩子进行LL旋转。
2. 围绕根节点进行RR旋转。

RL的旋转示意图如下：

B-Tree

平衡多路查找树（B-Tree）是为**磁盘等外存储设备设计**的一种平衡查找树。

因此在讲B-Tree之前先了解下磁盘的相关知识。

• 系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

• InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位

• 可通过参数innodb_page_size将页的大小设置为4K、8K、16K

• InnoDB存储引擎中默认每个页的大小为16KB，

在MySQL中可通过如下命令查看页的大小：

mysql> show variables like 'innodb_page_size';

但是系统一个磁盘块的存储空间往往没有这么大（16KB），但是**InnoDB在把磁盘数据读入到内存时会以页为基本单位**

所以InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB

在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。(应该是索引)

B-Tree结构特性

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键的值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

一棵m阶的B-Tree有如下特性： （二叉树的阶数是一个节点的子节点数目的最大值。）

1. 每个节点最多有m个孩子。
2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子（ceil(x)返回不小于x的最小整数值（然后转换为double型））
3. 若根节点不是叶子节点，则至少有2个孩子
4. 所有叶子节点都在同一层，且不包含其它关键字信息
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)为关键字，且关键字升序排序。
8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

实例

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

• 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字(主键)和三个指向子树根节点的指针
• 指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
• 以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：

根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
比较关键字29在区间（17,35），找到磁盘块1的指针P2。
根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
比较关键字29在区间（26,30），找到磁盘块3的指针P2。
根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
在磁盘块8中的关键字列表中找到关键字29。

结论

• 分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。
• 由于内存中的关键字（主键）是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。
• B-Tree相对于AVLTree缩减了节点个数（一个结点里存了多个数据），使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree

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

特点

在B+Tree中

• 所有数据记录节点都是按照主键大小顺序存放在同一层的叶子节点上
• 而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
• 指针数和键值数相等
• 所有叶子节点（即数据节点）之间是一种链式环结构

B+TREE 第二级的 数据并不能直接取出来，只作索引使用。在内存有限的情况下，查询效率高于 B-TREE
B-TREE 第二级可以直接取出来，树形结构比较重，在内存无限大的时候有优势。

将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^3）。也就是说一个深度为3的B+Tree索引可以维护10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2-4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1-3次磁盘I/O操作。（IO操作，从磁盘读数据到内存里）

数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。

• 上面的B+Tree示例图在数据库中的实现即为聚集索引**，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据**。

• 辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。

• 当通过辅助索引来查询数据时（辅助索引访问数据总是需要二次查找）

  • InnoDB存储引擎会遍历辅助索引找到主键

  • 然后再通过主键在聚集索引中找到完整的行记录数据

区别

B-Tree每个节点中不仅包含数据的key值，还有data值。而**每一个页的存储空间是有限**的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，只能纵向发展，增大查询时的磁盘I/O次数，进而影响查询效率。

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

1. 非叶子节点只存储键值信息（主键）。
2. 所有叶子节点之间都有一个链指针。
3. 数据记录都存放在叶子节点中。

B 树& B+树

B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。

目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。

B 树& B+树两者有何异同呢？

• B 树的所有节点既存放键(key) 也存放 数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
• B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
• B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。

分类

存储结构划分

从存储结构上来划分：

1. BTree索引（B-Tree或B+Tree索引），
2. Hash索引
3. full-index（全文索引）
4. R-Tree索引（空间数据索引）

这里所描述的是索引存储时保存的形式

主键索引

英文：Primary Key

• 主键列使用的就是主键索引
• 一张数据表有只能有一个主键，并且主键不能为 null，不能重复。
• 叶子节点保存行数据
• 在 MySQL 的 InnoDB 的表中，当没有显式的指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。

二级索引

二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。

唯一索引

英文：Unique Key

目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。

• 属性列不能出现重复数据
• 允许数据为 NULL，一张表允许创建多个唯一索引

普通索引

英文：Index

唯一作用就是为了快速查询数据，并允许数据重复和 NULL。

• 单值索引：只创建一个普通索引
• 复合索引：一张表允许创建多个普通索引

前缀索引

英文：Prefix

前缀索引是对文本的前几个字符创建索引

• 适用于字符串类型的数据。
• 相比普通索引建立的数据更小， 因为只取前几个字符。

全文索引

英文：Full Text

主要是为了检索大文本数据中的关键字的信息

• 是目前搜索引擎数据库使用的一种技术
• Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之后 InnoDB 也支持了全文索引。

聚簇索引

简介

• 聚集索引即索引结构和数据一起存放的索引，索引结构的叶子节点保存了行数据。主键索引属于聚集索引。
• 聚簇索引并不是一种单独的索引类型，而==是一种数据存储方式。==

创建

聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引

1. 有主键的情况下,主键就是聚簇索引
2. 没有主键的情况下,第一个非空null的唯一索引就是聚簇索引
3. 如果上面都没有,那么就是有一个隐藏的row-id作为聚簇索引

大部分情况下,我们建表的时候都会创建主键,因此大部分都是根据主键聚簇的

当我们根据主键字段来进行查询时,效率是最高的,不需要二次查找,直接主键字段查询索引树,叶子节点就是存储的数据了

Innodb通过主键聚集数据，如果没有定义主键，innodb会选择非空的唯一索引代替。如果没有这样的索引，innodb会隐式的定义一个主键来作为聚簇索引。

优点：

1. 数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
2. 聚簇索引对于主键的排序查找和范围查找速度非常快

缺点：

1. 依赖于有序的数据 ：因为 B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢，因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
2. 更新代价大 ： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且况聚集索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。，对于InnoDB表，我们一般定义主键为不可更新

非聚集索引

简介

• 非聚集索引即索引结构和数据分开存放的索引。索引结构的叶子节点指向了数据地址（保存了主键）
• 二级索引属于非聚集索引
• 非聚集索引的叶子节点并不一定存放数据的指针， 因为二级索引的叶子节点就存放的是主键，根据主键再回表查数据

优点

更新代价比聚集索引要小 。非聚集索引的更新代价就没有聚集索引那么大了，非聚集索引的叶子节点是不存放数据的

缺点

1. 跟聚集索引一样，非聚集索引也依赖于有序的数据
2. 可能会二次查询(回表) :这应该是非聚集索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

这是 MySQL 的表的文件截图:

聚集索引和非聚集索引:

覆盖索引

前言

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是列值+主键。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！

覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了， 而无需回表查询。

• 如主键索引，如果一条 SQL 需要查询主键，那么正好根据主键索引就可以查到主键。
• 再如普通索引，如果一条 SQL 需要查询 name，name 字段正好有索引， 那么直接根据这个索引就可以查到数据，也无需回表。

覆盖索引: