2. InnoDB中索引的推演

文章目录

一、索引 1. 索引的介绍

索引是存储引擎用于快速找到数据记录的一种数据结构，类似一本书的目录。MySQL在进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描。

索引是在存储引擎中实现的，因此每种存储引擎的索引都不一定完全相同。

同时存储引擎可以定义每张表的最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256个字节。有些存储引擎支持更多的索引数和更大的索引长度。

优点： 缺点：

提示：

索引可以提高查询速度，但是会影响插入记录的速度，这种情况下，最好的办法是可以先删除表中的索引，然后再插入数据，插入完成后重新创建索引。

2. InnoDB中索引的推演 2.1 没有索引之前的查找

先来看一个精确匹配的例子：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

首先需要了解数据是以页为单位进行存储的。

在一页中查找：

假设数据量很小，只有一页数据。

在很多页中查找：

大部分情况下数据量都不只一页，在很多页中查找记录可以分为两个步骤：

在没有索引的情况下，无论是主键列还是非主键列，我们都无法快速定位到数据在哪一页，所以只能从第一页开始往下找，在每一页中根据上面所写的（在一页数据中查找）的方式进行查找。很显然，我们需要遍历所有的数据页，效率很低。

2.2 索引的设计

前置知识：

建一个表：

这个新建的 index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键。

这个表使用 Compact 行格式来实际存储记录的。这里我们简化了index_demo表的行格式示意图：

我们只在示意图里展示记录的这几个部分：

1. 一个简单的索引设计方案

为什么我们需要遍历整张表呢？因为各个页中的记录并没有规律，所以不得不遍历所有的数据项。

因此我们可以建立一个目录，类似图书馆中的分类一样，提高查找的效率。

建立目录需要完成下面的要求：

2. InnoDB中的索引方案： （1）第一次迭代 ：目录项记录的页

从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。

这里再次强调 目录项记录 和普通的 用户记录 的不同点：

相同点：

（2）第二次迭代：多个目录项记录的页

由于页的大小是有限的，一页可能存储不了目录项，因此需要多页来存储目录项记录。

（3）第三次迭代：目录项记录的目录页

如图，我们生成了一个存储更高级目录项的 页33 ，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在 [1, 320) 之间，则到页30中查找更详细的目录项记录，如果主键值 不小于320 的话，就到页32中查找更详细的目录项记录。

我们可以用下边这个图来描述它：

这个数据结构，它的名称是 B+树 。

（4）B+Tree：

一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层。

前面我们举的例子，所用的数据量都很少。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放 100条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存放 1000条目录项记录 ，那么：

所以一般情况下，我们 用到的B+树都不会超过4层 ，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过 二分法 实现快速定位记录。

2.3 常见索引概念：

索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。

1. 聚簇索引：

（1）特点：

根据主键值的大小进行记录和页的排序，这包含三个方面： B+树的叶子节点存储的是完整的用户记录，也就是存储了所有的列的值。

我们把具有这两种特性的B+树称为聚簇索引。

（2）优点：

（3）缺点：

（4）限制：

2. 非聚簇索引：

上面介绍的聚簇索引只能在搜索条件是主键时才能发挥作用，因为B+树中的数据都是依据主键进行排序的。那如果我们想通过别的列作为搜索条件该怎么办呢？答案是：多建几棵B+树，不同的B+树采用不同的排序规则。例如我们可以对c2列的大小作为数据页，页中记录的排序规则，再建一棵B+树，如图：

**回表：**我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程称为 回表 。

聚簇索引和非聚簇索引之间的区别：

3. 联合索引：

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照 c2和c3列 的大小进行排序MySQL 索引，这个包含两层含义：

本质上联合索引也是二级索引。

2.4 InnoDB的B+树的补充说明： 1. 根页面位置往年不动

B+树的形成过程是这样的；

这个过程需要注意的是：**一个B+树索引的根节点自诞生开始，便不会移动。**这样当我们需要用到这个索引时，都会从一个固定的地方来访问这个根节点。

2. 内节点中目录项记录的唯一性

内节点：除了叶子节点外的节点。

上面我们对内节点内容的表示都是 索引列+页号，其实是不严谨的。

假设有索引所处的状态是这样的：

此时我们如果向插入一条新的纪录，其中c1，c2，c3的值为：9，1，‘c’，那么在修改这棵B+树时就遇到了问题：此时页3中的目录项记录是由c2+页号的值构成的，而有两条记录的c2值都是一样的，那么新插入的数据应该放到页4还是页5呢？

因此，我们需要**保证在B+树的同一层节点的目录项记录除页号外的字段是唯一的。**所以对于二级索引的内节点的目录项纪录的内容实际上是由三个部分组成的：

这样就能够确保各目录项记录除页号外是唯一的。

3. MyISAM中的索引方案

即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb和MyISAM默认的索引是Btree索引；而Memory默认的索引是Hash索引。

MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是 数据记录的地址 。

3.1 MyISAM索引的原理

在InnoDB中，索引即数据，因为聚簇索引的B+树的叶子节点已经包含了完整的用户记录了。而MyISAM虽然也是采用B+树，但是索引和数据是分开存储的：

因此MyISAM的检索方式：先通过B+树搜索算法搜索索引，如果指定的索引值存在，那么就会根据data域中的地址，读取相应的数据记录。

3.2 MyISAM和InnoDB的对比

MyISAM的索引方式都是非聚簇索引，InnoDB包含一个聚簇索引。

4. 索引的代价

索引虽好，但不可乱来。它在时间和空间上都有消耗：

5. MySQL数据结构选择的合理性 5.1 全表遍历

不借助索引，对整张表进行遍历。

5.2 Hash结构

Hash函数，又称散列函数。能够大幅度提高我们的检索效率。

Hash算法是通过某种确定性的算法（比如MD5，SHA1，SHA2，SHA3）将输入转为输出。相同的输入永远可以得到相同的输出。

加速查找速度的数据结构，常见的有两类：

采用Hash进行检索效率非常高，基本上一次检索就能够找到，而B+树需要自顶向下一次查找，多次访问结点，多次进行IO操作，从效率上来说Hash比B+树更快。

那既然Hash结构效率更高，为什么索引要设计成树形的呢？

Hash索引的适用性

虽然Hash索引有很多限制，但有一些场景采用Hash索引效率更高，比如在键值数据库中，Redis存储的核心就是Hash表。

MySQL中的Memory存储引擎支持Hash存储，把某个字段设置成Hash索引，比如字符串类型的字段，进行Hash计算后长度可以缩短到几个字节。当字段的重复度低，并且经常需要等值查询时，采用Hash索引是个不错的选择。

**InnoDB本身是不支持Hash索引的，但是提供了自适应Hash索引。**如果某个数据经常被访问，并且满足一定条件时，就会把这个数据页的地址放到Hash表中。这样下次查询时，就可以直接找到这个页面的位置。

可以通过 show variables like '%innodb_adaptive_hash_index' 来查看是否开启了自适应Hash索引，默认是开启的。

5.3 二叉搜索树

如果利用二叉搜索树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。

二叉搜索树的特点

理想的二叉搜索树构建后是这样的：

但是也有可能有些二叉搜索树创建后是这样的：

这样就退化成O(N)的时间复杂度了。因此为了减少磁盘的IO次数，就需要尽量降低树的高度，所以就引入了AVL树。

5.4 AVL树

为了解决上面二叉搜索树退化成链表的问题，人们提出了平衡二叉搜索树，又称AVL树，它在二叉搜索树的基础上增加了约束：

它是一棵空树或者它的左右子树的高度差的绝对值不超过1，并且左右子树都是一棵平衡二叉树。

常见的平衡二叉树有很多种：平衡二叉搜索树，红黑树，数堆，伸展树。

一般说的平衡二叉树就是指平衡二叉搜索树。

当数据很多时，平衡二叉搜索树的高度也会很高，这意味着磁盘IO操作次数多，针对这种情况，如果我们把二叉树改成M叉树呢？

当M等于3时，同样的节点可以存储成这样：

5.5 B-Tree

B树的英文是Balance Tree，也就是多路平衡查找树。它的高度远小于平衡二叉搜索树的高度。

B树的结构如下图所示：

B树作为多路平衡查找树，它的每一个节点都包含M个子节点，M被称为B树的阶。

**每个磁盘块中包含了关键字和子节点的指针。**如果一个磁盘块包含了x个关键字，那么指针数就是x+1。

对于一个100阶的B树来说，如果有3层的话最多可以存储约100万条数据。对于大量的数据来说，采用B树的结构是非常适合的，因为树的高度要远小于二叉树的高度。

小结：

5.6 B+Tree

B+树也是一种多路搜索树，基于B树进行了改进。相比于B-Tree，B+Tree更适合文件索引系统。

B+Tree和B-Tree的差异主要在以下几点：

B+Tree的中间节点并不存储数据，这样有什么好处？为什么说B+Tree是B-Tree的改进？

在MySQL采用的索引结构是B+树，但是B树和B+树各有各的应用场景，并不能踩一捧一。

思考题：

为了减少IO，索引树会一次性加载吗？

答：不会，数据库索引是存储在磁盘中的，当数据量很大时，必然会导致索引大小也会很大，是不可能一次性加载到内存中的，而是逐一加载磁盘页。

B+树的存储能力如何？为何说一般查找行记录，最多只需要1-3次磁盘IO？

答：InnoDB存储引擎的页的大小为16KB，一般表的主键是INT类（占用4个字节）或者BIGINT（占用8个字节），而指针的大小也一般为4或8个字节，也就是一个页（也就是B+树的一个节点）能够存储 16KB / (8B+8B) = 1K 个键值，为了方便计算，这里的K取值为103，也就是说一个深度为3的B+树能够存储 103 * 103 * 103 = 10亿条记录！（这里假定一个数据页也存储103 条行记录数据）。

实际情况中每个节点可能不能填满，因此在数据库中，B+Tree的高度一般是2-4层。但是MySQL的InnoDB存储引擎是将根节点常驻在内存中的，因此说查找某一条记录最多只需要1-3次磁盘IO。

为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引呢？

答：

一是B+树的读写代价更小。由于B+树的非叶子节点没有存放数据记录，因此同一磁盘页可以存放更多的索引，一次性读入内中的需要查找的关键字就更多，IO读写次数就降低了。

二是B+树的查询效率更加稳定。由于B+树的数据都存放在叶子节点，因此查询时必须从根节点到叶子节点一次遍历，导致每一关键字的查询效率相当。

Hash索引和B+树索引的区别？

前面已经有详细说明了，这里再总结概括一下：

一是Hash索引不能进行范围查找，B+树可以。因为Hash索引是无序的，而B+树的叶子节点是由有序的链表连接。

二是Hash索引不支持联合索引的最左侧原则，B+树可以。对于联合索引，Hash索引是将索引键合在一起后计算Hash值的，不会针对每个索引单独计算。因此如果需要用到联合索引中最左侧的单个或者几个索引时，联合索引是无法使用的。

三是Hash索引不支持ORDER BY排序，这也是因为Hash索引是无序的。同理，Hash索引也无法进行模糊查询，而B+树使用LIKE 进行模糊查询时，如果是进行后模糊查询的话（比如%结尾），就可以起到优化作用。

Hash索引和B+树索引是在建索引时手动指定的吗？

对于InnoDB和MyISAM是不支持Hash索引的，默认是B+树索引。InnoDB提供自适应Hash索引，无需手动指定。

5.7 R-Tree

R-Tree在MySQL中很少使用，仅支持geometry数据类型。

举个R-Tree的应用场景：查找20英里内的餐厅。一般情况下我们会把餐厅的坐标x，y分成两个字段存储在数据库中，一个记录经度，一个记录维度。这样我们就需要遍历所有的餐厅获取它的位置信息，然后计算是否满足要求。如果餐厅的数量是100家，那么我们就需要判断100次，显然效率是很低的。

R树就很好的解决这种空间搜索问题，它把B树的思想扩展到了多维空间，相比于B-Tree，R-Tree的优势在于范围查找。

由于很少使用，且不是重点，因此这里也不过多介绍。

（编辑：通辽站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!