共计 3582 个字符，预计需要花费 9 分钟才能阅读完成。
Mysql 数据库面试问题系列继续更新，想追更欢送关注
微信公众号：pipi 的奇思妙想原文链接
你可能曾经晓得 B + 树被用于 Mysql 的索引底层实现，那么，为什么是 B + 树呢？本文由浅及深，带你摸索数据库索引底层实现。
由一个例子总结索引的特点
加索引是数据库减速查问的一种形式，那么为什么用索引能够放慢查问呢？
讲到索引，其实咱们常常会听到一个图书馆的例子，图书馆里的书目繁冗，咱们如何从若干本书外面找到一本咱们想要的书呢？
咱们依据图书馆零碎检索，能够找到某本书对应的图书编号。
在基于书籍依照肯定规定排列的前提下，咱们能够依据图书编号找到这本书。
例如，假如图书编号依据：
第几个书架 – 书架上第几个格子 – 从左到右数第几个地位
这样的规定编排，
咱们就能够轻松的获取到咱们想要的书籍。
你兴许发现了，这个例子中，藏着两个信息：
- 依照肯定的规定排列
- 有序
依照肯定的规定，建设肯定的映射关系，这让你联想到了什么？
没错，就是哈希表。
基于哈希表实现的哈希索引
在 Mysql 的 InnoDB 引擎中，自适应哈希索引就是用哈希表实现的。
哈希索引是数据库本身创立并应用的，DBA 自身不能对其进行干涉，然而能够通过参数来禁止或者启用此个性。
显然用哈希表实现索引的益处是非常明显的，查找单个指定数据只须要 O(1)的工夫复杂度。
例如上面的 sql 语句：
select id from tablename where id == 1;然而对于这种查找指定范畴的 sql 语句，哈希索引就无能为力了。
select id from tablename where id BETWEEN 20 AND 23;阐明：因为哈希表自身是无序的，所以不利于范畴查问
再次思考
到这里咱们遇到了一个问题，就是哈希表尽管从查找效率上满足了咱们查找单个数据的要求，然而显然，当遇到范畴查问时，因为哈希表自身的无序性，不利于指定范畴查找。
也就是说，咱们的需要减少了，咱们心愿数据的组织形式，既要有肯定规定，又要有序。
在引出这种数据结构之前，咱们首先来看一种查找形式：二分查找。
高效的查找形式：二分查找
二分查找的核心思想是给定一个 有序 的数组，在查找过程中采纳跳跃式的形式查找，即先以有序数列的中点地位为比拟对象，如果要查找的元素小于中点元素，则将待查序列放大为左半局部，否则为右半局部。通过每次比拟，将查找区间缩小一半，直到找到所需元素。
比方要从以下序列中查找到数字 4
[1,3,4,5,6,7,8]须要通过上面的查找步骤：
- 取核心地位对应元素，显然 5 大于 4，在右边区间 [1,3,4] 进行查找
- 持续取核心地位对应元素 3，显然 3 大于 4, 在左边区间 [4] 进行查找
- 4 等于 4，所以咱们查找胜利。
能够看到二分查找的效率是 O(log n)。
因为有序数组本身的有序性，所以范畴查问仍然能够通过二分查找的形式查找区间的边界来实现。
这样看来，如果单从查问效率上来说，有序的数组是一种很好的抉择。
然而显然有序数组对于插入和删除并不敌对，假如咱们要插入元素或者删除元素，都须要把局部元素全副向后或者向前挪动，最蹩脚的工夫复杂度是 O(n)。
有没有这样一种数据结构，既有肯定程序，又不便插入和删除呢？事实上，基于二分查找的思维，诞生了这样一种数据结构：二分查找树。
基于二分查找思维的二叉查找树
二叉查找树（Binary Search Tree）即 BST 树是这样的一种数据结构, 如下图：
在二叉搜寻树中：
1). 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2). 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3). 任意结点的左、右子树也别离为二叉搜寻树。
这样的构造非常适合用二分查找的思维查找元素。
比方咱们须要查找键值为 8 的记录：
- 先从根找起，找到 6；
- 显然 8 >6，所以接着找到 6 的右子树，找到 7；
- 显然 8 >7, 所以找 7 的右子树，找到了 8，查找完结。
这样一棵子树高度差不大于 1 的二叉查找树的查找效率靠近与 O(log n);
然而当二叉树的结构变成这样时,
此时咱们再查找 8 时, 查找效率就沦为靠近程序遍历查找的效率。
显然这不是咱们想要的，二叉查找树也须要 balance。
升级版的 BST 树：均衡二叉树
咱们对二叉查找树做个限度，限度必须满足任何节点的两个子树的最大差为 1，也是均衡二叉树的定义，这样咱们的查找效率就有了肯定的保障。
均衡二叉树(self-balancing binary search tree), 又叫 AVL 树。
当然，保护均衡二叉树也是须要肯定开销的，即当树插入 / 更新 / 删除新的数据时假如毁坏了树的平衡性，那么须要通过左旋和右旋来保护树的均衡。
当数据量很多时，同样也会呈现二叉树过高的状况。
咱们晓得均衡二叉树的查找效率为 O(log n)，也就是说，当树过高时，查找效率会降落。
另外因为咱们的索引文件并不小，所以是存储在磁盘上的。
文件系统须要从磁盘读取数据时，个别以页为单位进行读取，假如一个页内的数据过少，
那么操作系统就须要读取更多的页，波及磁盘随机 I / O 拜访的次数就更多。
将数据从磁盘读入内存波及随机 I / O 的拜访，是数据库外面老本最高的操作之一。
因此这种树高会随数据量增多急剧减少，每次更新数据又须要通过左旋和右旋保护均衡的二叉树，不太适宜用于存储在磁盘上的索引文件。
更加合乎磁盘特色的 B 树
后面咱们看到，尽管均衡二叉树既有链表的疾速插入与删除操作的特点，又有数组疾速查找的劣势，然而这并不是最合乎磁盘读写特色的数据结构。
也就是说，咱们要找到这样一种数据结构，可能无效的管制树高，那么咱们把二叉树变成 m 叉树，也就是下图的这种数据结构:B 树。
B 树是一种这样的数据结构：
1. 根结点至多有两个子结点;
2. 每个两头节点都蕴含 k - 1 个元素和 k 个子结点，其中 m/2 <= k <= m;
3. 每一个叶子结点都蕴含 k - 1 个元素，其中 m/2 <= k <= m;
4. 所有的叶子结点都位于同一层;
5. 每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该 k - 1 个元素正好是 k 个子结点蕴含的元素的值域的分划。
能够看到，B 树在保留二叉树预划分范畴从而晋升查问效率的思维的前提下，做了以下优化：
二叉树变成 m 叉树，这个 m 的大小能够依据单个页的大小做对应调整，从而使得一个页能够存储更多的数据，从磁盘中读取一个页能够读到的数据就更多，随机 IO 次数变少，大大晋升效率。
然而咱们看到，咱们只能通过中序遍历查问全表，当进行范畴查问时，可能会须要中序回溯。
一直优化的 B 树：B+ 树
基于以上的缺点，又诞生了一种新的优化 B 树的树:B+ 树
B+ 树在 B 树的根底上加了以下优化：
1. 叶子结点减少了指针进行连贯，即叶子结点间造成了链表；
2. 非叶子结点只存关键字 key，不再存储数据，只在叶子结点存储数据；
阐明：叶子之间用双向链表连贯比单向链表连贯多出的益处是通过链表中任一结点都能够通过往前或者往后遍历找到链表中指定的其余结点。
这样做的益处是：
1. 范畴查问时能够通过拜访叶子节点的链表进行有序遍历，而不再须要中序回溯拜访结点。
2. 非叶子结点只存储关键字 key，一方面这种构造相当于划分出了更多的范畴，放慢了查问速度，另一方面相当于单个索引值大小变小，同一个页能够存储更多的关键字，读取单个页就能够失去更多的关键字，可检索的范畴变大了，绝对 IO 读写次数就升高了。
一些总结
B+ 树和 B 树的区别？
1.B 树非叶子结点和叶子结点都存储数据, 因而查问数据时，工夫复杂度最好为 O(1), 最坏为 O(log n)。
B+ 树只在叶子结点存储数据，非叶子结点存储关键字，且不同非叶子结点的关键字可能反复，因而查问数据时，工夫复杂度固定为 O(log n)。
2.B+ 树叶子结点之间用链表相互连接，因此只需扫描叶子结点的链表就能够实现一次遍历操作，B 树只能通过中序遍历。
为什么 B+ 树比 B 树更适宜利用于数据库索引？
- B+ 树更加适应磁盘的个性，相比 B 树缩小了 I / O 读写的次数。因为索引文件很大因而索引文件存储在磁盘上，B+ 树的非叶子结点只存关键字不存数据，因此单个页能够存储更多的关键字，即一次性读入内存的须要查找的关键字也就越多，磁盘的随机 I / O 读取次数绝对就缩小了。
- B+ 树的查问效率相比 B 树更加稳固，因为数据只存在在叶子结点上，所以查找效率固定为 O(log n)。
- B+ 树叶子结点之间用链表有序连贯，所以扫描全副数据只需扫描一遍叶子结点，利于扫库和范畴查问；B 树因为非叶子结点也存数据，所以只能通过中序遍历按序来扫。也就是说，对于范畴查问和有序遍历而言，B+ 树的效率更高。
最初
1. 一个无聊的小科普，均衡二叉树叫 AVL 树是因为均衡二叉树是由
G.M.Adelson-Velsky 和 E.M.Landis
这两位俄罗斯科学家在 1962 年的论文中首次提出的
2. 闲来无事能够做道均衡二叉树的题目
110. 均衡二叉树
Mysql 数据库面试问题系列继续更新，想追更欢送关注
微信公众号：pipi 的奇思妙想点个赞也是激励哒~
