什么是Mysql索引

思考:了解过索引吗？（什么是索引）

索引（index）: 帮助MySQL高效获取数据的数据结构(有序)。

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

思考:Mysql索引的底层数据结构了解过嘛?

MySQL默认使用的索引底层数据结构是B+树

再介绍B+树之前，我们先知道二叉树(主要是二叉搜索树和红黑树)和B树

1.二叉树

二叉树: 顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。二叉树每个节点的左子树和右子树也分别满足二叉树的定义

常见的二叉树有:

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 红黑树

1.1. 二叉搜索树

二叉搜索树(Binary Search Tree,BST)： 名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值

在极端情况下，二叉树会形成一个单向链表，结构如下：

二叉搜索树,属于最坏的情况，已经退化成了链表，左右子树极度不平衡，此时查找的时间复杂度肯定是O(n)

1.2. 二叉树作为索引结构缺点

• 1.如果数据是有序的，则会顺序插入，形成链表，查询效率就降低
• 2.如果数据量比较大，层级就比较深，检索效率就慢

2. 红黑树

考虑到二叉树有这些缺点后，我们可能就会考虑使用二叉树进阶版红黑树，红黑树是一个自由平衡二叉树，解决了是顺序插入数据形成单向链表的缺点，最终形成的数据结构也是一颗平衡的二叉树

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）

红黑树数据结构如下:

2.1. 红黑树的特质

• 性质1：节点要么是红色,要么是黑色
• 性质2：根节点是黑色
• 性质3：红黑树中红色节点的子节点都是黑色
• 性质4: 叶子节点都是黑色
• 性质5：从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质

红黑树:保证平衡

虽然解决单向列表缺点，但是还是存在缺点:

如果数据量比较大，层级就较深，检索效率就慢

3. B树(B-Tree)

B-Tree：B树是一种多叉路衡查找树，相对于二叉树，B树每个节点可以有多个分支，即多叉。

B树(B-Tree)具有一下特点:

• 1.多叉树结构：B-Tree是一种多叉树，每个内部节点可以有多个子节点,使得B-Tree能够有效地存储和管理大量数据。
• 2.平衡性：B-Tree具有平衡性，这意味着从根节点到叶子节点的任何路径的长度几乎相等。这确保了在平均情况下，对树的操作（插入、删除、查找）具有稳定的性能，不会出现严重的性能退化。
• 3.按序存储：B-Tree内的节点和数据通常按照键的顺序存储，这有助于范围查询和排序操作的高效执行。
• 4.分层结构：B-Tree具有分层结构，从根节点到叶子节点有多个级别。
• 5.高度平衡：B-Tree的高度通常是相对较低，这是因为它的平衡性和多叉性质。高度平衡有助于减少查找操作所需的磁盘访问。

对数据库而言，所有的数据都将会保存到磁盘上，磁盘 I/O 的效率又比较低，特别是在随机磁盘 I/O 的情况下效率更低。

B树(B-Tree),高度决定了磁盘 I/O 的次数，磁盘 I/O 次数越少，对于性能的提升就越大，这也是为什么采用 B 树作为索引存储结构的原因

4. B+树(B+Tree)

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

相比较于 B-Tree结构来说，B+Tree做了两个方面的优化，如图所示：

可以看到两部分:

• 1.蓝色框部分，索引部分，是非叶子结点，仅仅起到索引数据的作用，不存储数据。
• 2.绿色框部分，数据存储部分，是叶子结点，叶子节点中要存储具体的数据。
• 3.MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能，利于排序

B树与B+树对比

• 磁盘读写代价B+树更低
• 查询效率B+树更加稳定
• B+树便于扫库和区间查询

5. Mysql索引面试题

面试官：了解过索引吗？（什么是索引）

候选人：

索引在项目中还是比较常见的，帮助MySQL高效获取数据的数据结构，主要是用来提高数据检索的效率，降低数据库的IO成本，同时通过索引列对数据进行排序，降低数据排序的成本，也能降低了CPU的消耗

面试官：索引的底层数据结构了解过嘛 ?

候选人：

MySQL的默认的存储引擎InnoDB采用的B+树的数据结构来存储索引，选择B+树的主要的原因是：

第一：阶数更多，路径更短，搜索效率高

第二：磁盘读写代价B+树更低，非叶子节点只存储指针，叶子阶段存储数据，而B-Tree,无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储键值减少，指针跟着减少，相对于B+树同样保存大量数据，只能增加树的高度，导致性能降低

第三：B+树便于扫库和区间查询，叶子节点是一个双向链表

面试官：B树和B+树的区别是什么呢？

候选人：

第一：在B树中，非叶子节点和叶子节点都会存放数据，而B+树的所有的数据都会出现在叶子节点，在查询的时候，B+树查找效率更加稳定

第二：在进行范围查询的时候，B+树效率更高，因为B+树都在叶子节点存储，并且叶子节点是一个双向链表