索引的发展过程

MySQL索引发展过程

1. 索引是什么？

MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构，索引本质：索引是数据结构。可以简单理解为”排好序的快速查找B+树数据结构“。

在MySQL5.5以后默认的InnoDB存储引擎，使用的就是B+树。

• B+树中的B代表平衡(balance)而不是二叉(binary)。

1.1 检索原理

在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

2. MySQL索引结构

2.1 BTREE

B树(Balance Tree多路平衡查找树)

B-树就是B树，中间横线不是减号。

2.2 为什么是B+树？B+树的发展历程

InnoDB存储引擎并非一开始就选择的B+树，而是经过了以下的迭代过程。

2.2.1 全部遍历

没有索引的情况，任何查找都要全表扫描，自然不可能使用这个。

2.2.2 Hash

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

• 哈希，例如HashMap，CRUD平均时间复杂度是O(1)；意思只要查询一次就能找到，最好的算法。但是，如果SQL语句中使用到范围查找或排序查找等SQL条件，哈希索引性能就会退化为O(n)，变成了最差的算法。
• 树，例如平衡二叉树，CRUD的平均时间复杂度都是O(log2(n))，不会因为使用到范围/排序等SQL条件的影响，依然保持O(log2(n))的效率，非常稳定。

InnoDB不支持哈希索引

2.2.3 二叉树

二叉搜索树的特点：

1. 一个节点只能有两个子节点，就是说一个节点度不能超过2；
2. 左子节点小于当前节点，右子节点大于等于当前节点。

• 查找时间复杂度
  • 深度为1的节点查找次数为1
  • 深度为2的节点查找次数为2
  • 深度为N的节点查找次数为N

• 故可得知：二叉搜索树的平均时间复杂度和树的高度成正比，平均时间复杂度为O(logn)。

• 缺点：如果插入的值是持续递增的，那么二叉树就会出现“右倾”现象，从树退化成链表结构，导致其时间复杂度退化为了O(n)，这就是二叉搜索树的不平衡。

以上二叉树图均来自于该网站的数据结构可视化，可加深对二叉树的理解。

2.2.4 平衡二叉树(AVL)

平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树会在插入数据时维护一个平衡因子，让树在不平衡时进行左旋或右旋，具体可见文章。

• 缺点：如上图插入10条数据，树的高度就达到了4层；数据量越多，树高就越高，树越高，查找次数越多，IO次数也就越多，从而导致系统性能下降。这就是树高度问题导致的磁盘IO过多。

因此要想办法将树的高度降下来，通过降低树的高度达到减少IO次数。

2.2.5 B树

B树(B-Tree)是一种多叉平衡查找树，每个节点可能有两个或三个，如下图所示：

• 底层原理

数据库索引是存储在硬盘上的，如果数据量很大，也会导致索引很大，超过几个G；当我们利用索引查询时，不可能将全部几个G的索引都加载进内存的，因此使用的是逐一加载每一个磁盘页，因为磁盘页对应着索引树的节点。

• 磁盘页/块

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

InnoDB存储引擎中有页(Page)的概念，页是其磁盘管理的最小单位。系统一个磁盘块的存储空间往往是有限的，因此InnoDB每次申请磁盘空间时都会是若干地址连续的磁盘块来达到一页的大小16KB。

MySQL中使用show global status like "Innodb_page_size;"命令可以查看当前数据库配置的磁盘页大小，默认大小为16KB。

InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘IO次数，提高查询效率。

可以把索引文件想象成一本书，而磁盘页就是其中的一页，里面存储的索引信息，写满一页才会写下一页。

• B树检索原理

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。

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

• 根据根节点找到磁盘块1，读入内存；[磁盘第一次IO]
• 比较关键字29所在区间(在17,35之间)，找到该区间指针磁盘1P2；
• 根据P2指针找到磁块3，读入内存；[磁盘第二次IO]
• 比较关键字29所在区间(26,30之间)，找到该区间指针磁盘3P2；
• 根据P2指针找到磁盘8，读入内存。[磁盘第三次IO]
• 在磁盘8中找到对应关键字29。

如上过程，发生了3次磁盘I/O操作和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个BTree查找效率的决定因素。BTree相对于ALVTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

如上操作，B树比AVL树减少了一次IO操作，故取代了它。

2.2.6 B+树

如图所示，可以看出所有data信息都移动到了叶子节点中，且子节点和子节点之间会有一个指针指向，这也是B+树的核心点，有序的链表结构，这样可以大大提升范围查询效率，也方便遍历整个树。

• 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；

• 叶子之间，增加了链表，获取所有节点，不再需要中序遍历了。

• 中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树；若二叉树为空则结束返回，否则继续。

  • 简言之：中序遍历就是左中右

• B+树检索原理

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

在B树中，每个节点不仅仅包含数据的key值，还有data值。而每一页的存储空间是有限的，如果data数据较大时将会导致每个节点(即一页)能存储的key的数量很少，当存储的数据量很大时同样会导致B树的深度较大，增大查询IO次数从而影响效率。

但在B+树中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点只存储key信息，这样可以大大增加每个节点存储的key值数量，从而降低B+树的高度。

• InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存储键值+指针。
• 索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中。

B+树算法：通过继承了B树的特征，B+树相比B树，新增叶子节点和非叶子节点的关系。

• 叶子节点中包含了键值和数据；
• 非叶子节点中只包含键值和子节点引用，不包含数据；
• 通过非叶子节点查询叶子节点获取对应的数据，所有相邻的叶子节点包含非叶子节点使用有序链表进行结合，叶子节点是顺序排序且相邻节点有顺序引用的关系。

3. 面试题

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

3.1 B树和B+树的区别

• B树没有叶子节点和非叶子节点之分，故B树的非叶子节点可以存储键值和数据。
• B+树的非叶子节点只存储键值信息，所有数据记录都存放在叶子节点中，故B+树每一页可以存放更多的key信息，从而降低树高。
• B+树的叶子节点之间都有一个链指针。

3.2 B+树相比B树的优势

1. IO次数更少，体现在以下几点：
   1. 范围查询时，相比于B树查询范围时的中序遍历，B+树只需遍历链表即可完成，IO次数更少；
   2. 由于B+树只在叶子节点存储数据，使得同样大小的磁盘页B+树能容纳更多的节点元素，意味着在数据量相同情况下，B+树结构比B树更“矮胖”，树高更低，因此IO次数也更少。
2. 查询性能稳定：B树由于枝节点也存储数据，所有查询性能不稳定(最优只查根节点、最坏查到叶子节点)，而B+树的每一次查找都是稳定的。
3. 范围查询简便：有序链表结构，范围查询无需中序遍历。

3.2 本文基本要求

要求说出上述所有索引结构，以及各自优缺点。