Innodb索引原理解析

image.png

今天讲解mysql储存引擎(Innodb)使用的索引。大家应该都用过各种索引（主键索引/唯一索引/全文索引）等等。。但索引的具体实现很多人还不是很了解，今天笔者将内容整理整理，详细讲讲索引的原理。

大家操作数据库工具时会发现索引类型是可选的。

image.png

索引在 MySQL 数据库中分三类：
🚑Hash 索引
🚓B+ 树索引
🚒全文索引

• 1.先看看Hash索引吧:

  
  image

首先会将数据的主键进行Hash运算后，放入相应的位置。与HashMap数组的链表原理差不多。

「题外话：为什么HashMap的初始容量为16,扩容也是扩容到2的n次幂？」

image.png

• 🚔1.因为key转换为Hash值后会与【容量的值-1（比如16-1=15）】的二进制进行一次【或】的运算。
• 🚍2.或的运算就是【0或1=0，0或0=1】/【1或1=1】。
  所以只有两边为1或出来的值才为1。
• 🚘3.这就是为什么容量为2的n次幂的原因。因为（2的n次幂-1）二进制一定会是11111....不会是0，那【或】出来的值就会可0可1。
• 🚖4.所以这样就不会出现算出来的值都是0的情况，这样布局就很均匀，不会浪费空间也减少hash值的冲突的几率了。

「 题外话结束。。继续讲hash索引」

优点：利用hash的索引，我们可以很快的定位到所要查找的数据主键值，定位到数据。

缺点：因为hash索引为无序的，当我们的搜索条件为 where XX>0 那hash索引则无能为力了。必须通过全盘扫描定位到数据。

• 2.数组索引

既然hash索引无序的，那最初会引入有序数组的索引。与我们经常用到的ArrayList有些相像。

虽然数组是有序的，但是我们知道ArrayList不是很支持比较高频率的增加和删除操作。

image.png

如图所示：添加一条数据我们需要进行复制，删除，添加操作。
这样，一张表需要增加删除数据的时候效率就极其低了。

结论：一般用于不需要【增加/删除】的数据，
如：2019年的某宝支付账单，2019年的某宝购物记录等等

• 3. 二叉数索引
     二叉树结构如图：

     
     image.png

二叉数：基本的插入原理就是比节点大的id放在右边，比节点小的放在左边。

🚀对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次

比如：查找图中id为3的数据，本来需要遍历图中的6个数据，查找6次才找到。通过二叉树，则从6的节点开始，查找第二次就找到id为3的这一条数据了。

🚁但我们会发现，当数据总是比节点的大，或者总是比节点的小的话，二叉树就毫无意义了，

还是要遍历所有才能找到需要的数据。如图：

image.png

✈️所以我们要通过转化节点的数据来调整二叉树，使其平衡。

• 4.平衡二叉树

  
  image.png
  

  这样调整后我们的搜索就又快了很多。

那是否这样平衡二叉树做索引就快了很多了呢?

此言差矣，索引也不只是在内存里面存储的，还是要落盘持久化的，可以看到图中才这么一点数据，如果数据多了，树高会很高，查询的成本就会随着树高的增加而增加。

🏠如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。

🏡我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？

.
.

• 5. B树 🌲

为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。

B 树（Balance Tree）即为平衡树的意思，下图即是一棵 B 树：

image.png

🏖因为索引数据落盘会以页为单位，一页为一个磁盘块。当我们io获取数据的时候，拿出一个磁盘块的数据，就等于获取了很多条数据。之前二叉树一个磁盘块只存放一个数据，那会导致磁盘空间浪费，而且查找数据io的次数会增多。

从上图可以看出，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。
基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。

假如我们要查找 id=28 的用户信息，那么我们在上图 B 树中查找的流程如下：

• 1.🚧先找到根节点也就是页 1，判断 28 在键值 17 和 35 之间，那么我们根据页 1 中的指针 p2 找到页 3。
• 2.🚦将 28 和页 3 中的键值相比较，28 在 26 和 30 之间，我们根据页 3 中的指针 p2 找到页 8。
• 3.🚥将 28 和页 8 中的键值相比较，发现有匹配的键值 28，键值 28 对应的用户信息为（28，bv）。

.
.

• 6. B+ 树🌲
     B+ 树是对 B 树的进一步优化。让我们先来看下 B+ 树的结构图：

     
     image.png

根据上图我们来看下 B+ 树和 B 树有什么不同：

①B+ 树非叶子节点上是不存储数据的，仅存储键值，而 B 树节点中不仅存储键值，也会存储数据。

• 1.🚑之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。
• 2.🚒如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。
• 3.🚐另外，B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。
  一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。

②因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。

• 1.🏄‍♂️那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。

• 2.🏄B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。

上图中的 B+ 树索引就是 InnoDB 中 B+ 树索引真正的实现方式，准确的说应该是聚集索引。
通过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。