MySQL - 索引底层实现 - B+树/Hash

小灰灰 2022-12-04 08:57 187阅读 0赞

1.应用场景

<table> 
 <tbody> 
 <tr> 
 <td> 主要学习MySQL索引底层实现，数据结构与算法， 同时了解B+树/Hash索引的区别与优缺点以及各自的应用场景. 
 <blockquote> 
 对于一般需求来说，B+树在数据库应用的场景更多; 
 Hash适用一些特殊的需求，比如文件校验，密码学等. 
 </blockquote> MySQL查询中存在着很多范围查询、order by的场景，在这些场景下，B+树的性能好于Hash索引； 关键字出现相同Hash码时，会出现hash冲突。 </td> 
 </tr> 
 <tr> 
 <td>读书是易事，思索是难事，但两者缺一，便全无用处。——富兰克林</td> 
 </tr> 
 </tbody> 
</table>

2.学习/操作

<table> 
 <tbody> 
 <tr> 
 <td> <h2>一. 文档阅读</h2> 
 <blockquote> 
 <a href="https://time.geekbang.org/column/article/112298" rel="nofollow">https://time.geekbang.org/column/article/112298</a>&nbsp;// 24丨索引的原理：我们为什么用B+树来做索引？ 
 <a href="https://time.geekbang.org/column/article/113669" rel="nofollow">https://time.geekbang.org/column/article/113669</a>&nbsp; // 25丨Hash索引的底层原理是什么？ 
 <a href="https://time.geekbang.org/column/article/64233" rel="nofollow">https://time.geekbang.org/column/article/64233</a>&nbsp;//&nbsp;18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？ 
 <a href="https://time.geekbang.org/column/article/64586" rel="nofollow">https://time.geekbang.org/column/article/64586</a>&nbsp;//&nbsp;19 | 散列表（中）：如何打造一个工业级水平的散列表？ 
 <a href="https://time.geekbang.org/column/article/64858" rel="nofollow">https://time.geekbang.org/column/article/64858</a>&nbsp;//&nbsp;20 | 散列表（下）：为什么散列表和链表经常会一起使用？ 
 <a href="https://time.geekbang.org/column/article/77830" rel="nofollow">https://time.geekbang.org/column/article/77830</a>&nbsp;// 48 | B+树：MySQL数据库索引是如何实现的？ 
 <a href="https://xueyuanjun.com/post/21942" rel="nofollow">https://xueyuanjun.com/post/21942</a>&nbsp; // 存储引擎系列（二）：数据库索引底层数据结构 —— B+ 树 
 <a href="https://xueyuanjun.com/post/21946" rel="nofollow">https://xueyuanjun.com/post/21946</a>&nbsp; // 存储引擎系列（三）：不同类型的数据库索引 B+ 树是如何维护的 
 <a href="https://time.geekbang.org/column/article/127873" rel="nofollow">https://time.geekbang.org/column/article/127873</a>&nbsp;//&nbsp;34丨答疑篇：关于索引以及缓冲池的一些解惑 
 <a href="https://blog.csdn.net/william_n/article/details/100827803" rel="nofollow">https://blog.csdn.net/william_n/article/details/100827803</a>&nbsp;//&nbsp;MySQL 索引 - 学习/实践 
 </blockquote> <h2>二. 整理输出</h2> 经过上面的文档学习，个人的目前理解如下✍ <h3>引言</h3> 按照推荐学习的方法论，是什么/WHAT，为什么/WHY，怎样做/HOW？ <h1>--------------------------------- B+树</h1> <h3>1. 介绍与区别</h3> <h3>B 树</h3> 
 <blockquote> 
 B 树的出现就是为了解决这个问题，B 树的英文是 Balance Tree，也就是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的<a href="https://blog.csdn.net/william_n/article/details/100827803" rel="nofollow">索引</a>结构经常采用 B 树来实现。 
 
 对于大量的索引数据来说，采用 B 树的结构是非常适合的，因为树的高度要远小于二叉树的高度。 
 
 一个 M 阶的 B 树（M&gt;2）有以下的特性： 
 <ul> 
 <li>根节点的儿子数的范围是[2,M]。</li> 
 <li>每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为[ceil(M/2), M]。</li> 
 <li>叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为[ceil(M/2), M]。</li> 
 <li>假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]&lt;Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …, P[k]，其中 P[1]指向关键字小于 Key[1]的子树，P[i]指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]指向关键字大于 Key[k-1]的子树。所有叶子节点位于同一层。</li> 
 </ul> 
 </blockquote> B 树的结构如下图所示： <img alt="" src="https://img-blog.csdnimg.cn/img_convert/e3f4ba170a29dbfc53262acfccf77d34.png"> <h3>B+树</h3> 
 <blockquote> 
 B+ 树基于 B 树做出了改进，主流的 DBMS 都支持 B+ 树的索引方式。 
 </blockquote> 比如 MySQL。B+ 树和 B 树的差异在于以下几点 
 <blockquote> 
 <ul> 
 <li>有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 +1。</li> 
 <li>非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。</li> 
 <li>非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非叶子节点既保存索引，也保存数据记录。</li> 
 <li>所有关键字都在叶子节点出现，叶子节点构成一个有序链表[双向链表]，而且叶子节点本身按照关键字的大小从小到大顺序链接。</li> 
 </ul> 
 </blockquote> B+ 树的结构如下图所示： <img alt="" src="https://img-blog.csdnimg.cn/img_convert/47e17170ffbd7af453f918f4c8f2681c.png"> <h3>2. 过程解释</h3> 上图就是一棵 B+ 树，阶数为 3。 根节点中的关键字 1、18、35 分别是子节点（1，8，14），（18，24，31）和（35，41，53）中的最小值。每一层父节点的关键字都会出现在下一层的子节点的关键字中，因此在叶子节点中包括了所有的关键字信息，并且每一个叶子节点都有一个指向下一个节点的指针，这样就形成了一个链表。 
 <ol> 
 <li>与根节点的关键字 (1，18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2）</li> 
 <li>找到磁盘块 2，关键字为（1，8，14），因为 16 大于 14，所以得到指针 P3（指向磁盘块 7）</li> 
 <li>找到磁盘块 7，关键字为（14，16，17），然后我们找到了关键字 16，所以可以找到关键字 16 所对应的数据。</li> 
 </ol>整个过程一共进行了 3 次 I/O 操作，看起来 B+ 树和 B 树的查询过程差不多，但是 B+ 树和 B 树有个根本的差异在于，B+ 树的中间节点并不直接存储数据。这样的好处都有什么呢？ 
 <blockquote> 
 首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。 
 
 其次，B+ 树的查询效率更高，这是因为通常 B+ 树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少。同样的磁盘页大小，B+ 树可以存储更多的节点关键字。 
 
 不仅是对单个关键字的查询上，在查询范围上，B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，并通过有序链表进行了链接。而在 B 树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。 
 </blockquote> 个人看法: 
 <blockquote> 
 上面说的优点：简单说，就是牺牲局部的最优[找到数据，就能返回，不一定非要到叶子结点]换取整体上的最优[每个数据，都要走到叶子结点，因为非叶子结点不需要存储数据，则相同大小的磁盘页，存放的节点就更多，树的构造可以更加矮胖，所需要进行的磁盘 I/O 次数更少]，达到更加公平[掺杂人为因素]，至于稳定性，则是附带而来～ 说是优点，感觉有点牵强～ 
 </blockquote> <h3>3. 总结</h3> 
 <blockquote> 
 磁盘的 I/O 操作次数对索引的使用效率至关重要。虽然传统的二叉树数据结构查找数据的效率高，但很容易增加磁盘 I/O 操作的次数，影响索引使用的效率。因此在构造索引的时候，我们更倾向于采用“矮胖”的数据结构。 
 
 B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树，B+ 树在查询性能上更稳定，在磁盘页大小相同的情况下，树的构造更加矮胖，所需要进行的磁盘 I/O 次数更少，更适合进行关键字的范围查询。 
 </blockquote> <img alt="" src="https://img-blog.csdnimg.cn/img_convert/83cb65f7395b24be054a4e180ef1b36c.png"> <h3>4. 课后题</h3> 你能说下为什么数据库索引采用 B+ 树，而不是平衡二叉搜索树吗？ 另外，B+ 树和 B 树在构造和查询性能上有什么差异呢？ 
 <blockquote> 
 1. 平衡二叉树必须满足（所有节点的左右子树高度差不超过1）。 
 执行插入还是删除操作，只要不满足上述条件，就要通过旋转来保持平衡，而旋转是非常耗时的， 
 所以AVL树适合用于查找多的情况。 
 2. 二叉树的数据结构，会导致“深度”，比较深，这种“瘦高”的特性，加大了平均查询的磁盘IO次数，随着数据量的增多，查询效率也会受到影响； 二、B+ 树和 B 树在构造和查询性能上有什么差异呢？ 
 构造上： 
 主要的区别： 1. B+ 树的中间节点并不直接存储数据。 
 2. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。 
 
 查询性能 1. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 
 2. B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。 
 3、由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。 
 </blockquote> <h1></h1> <h1>--------------------------------- Hash</h1> <h3>1. 前言</h3> 
 <blockquote> 
 这里并不单单只涉及到MySQL 
 应该是涉及了多种不同的关系型数据库 
 
 另外 
 针对MySQL 默认的存储引擎InnoDB，或者使用MyISAM存储引擎都会默认使用的是B+树来进行存储，无法使用Hash索引。 
 InnoDB提供的自适应Hash是不需要手动指定的。 
 如果是Memory/Heap，或者是NDB存储引擎，是可以进行选择的（Hash还是B+树）。 
 
 详情继续往下看&nbsp;↓ 
 </blockquote> <h3>2. 介绍</h3> 
 <blockquote> 
 Hash 本身是一个函数，又被称为散列函数，它可以帮助我们大幅提升检索数据的效率。 
 
 打个比方，Hash 就好像一个智能前台，你只要告诉它想要查找的人的姓名，它就会告诉你那个人坐在哪个位置，只需要一次交互就可以完成查找，效率非常高。 
 
 大名鼎鼎的 MD5 就是 Hash 函数的一种。 
 Hash 算法是通过某种确定性的算法（比如 MD5、SHA1、SHA2、SHA3）将输入转变为输出。 
 
 相同的输入永远可以得到相同的输出，假设输入内容有微小偏差，在输出中通常会有不同的结果。 
 
 如果你想要验证两个文件是否相同，那么你不需要把两份文件直接拿来比对，只需要让对方把 Hash 函数计算得到的结果告诉你即可，然后在本地同样对文件进行 Hash 函数的运算，最后通过比较这两个 Hash 函数的结果是否相同，就可以知道这两个文件是否相同。 
 </blockquote> <h3>3. 实验</h3> 
 <blockquote> 
 Hash 可以高效地帮我们完成验证的工作，它在数据库中有广泛的应用。 
 </blockquote> 今天的课程主要包括下面几个部分： 
 <blockquote> 
 动手写程序统计一下 Hash 检索的效率。 
 了解 MySQL 中的 Hash 索引，理解使用它的优点和不足。 
 Hash 索引和 B+ 树索引的区别以及使用场景。 
 </blockquote> <h3>3.1 动手统计 Hash 检索效率</h3> 我们知道 Python 的数据结构中有数组和字典两种，其中数组检索数据类似于全表扫描，需要对整个数组的内容进行检索；而字典是由 Hash 表实现的，存储的是 key-value 值，对于数据检索来说效率非常快。 对于 Hash 的检索效率，我们来个更直观的认知。 下面我们分别看一下采用数组检索数据和采用字典（Hash）检索数据的效率到底有怎样的差别。 实验 1： 在数组中添加 10000 个元素，然后分别对这 10000 个元素进行检索，最后统计检索的时间。 代码如下： 
 <blockquote> 
 import time # 插入数据 result = [] for i in range(10000): &nbsp; &nbsp; &nbsp; &nbsp;result.append(i) # 检索数据 time_start=time.time() for i in range(10000): &nbsp; &nbsp; &nbsp; &nbsp;temp = result.index(i) time_end=time.time() print('检索时间', time_end-time_start) 
 </blockquote> 运行结果：检索时间为 1.2436728477478027 秒 实验 2： 采用 Hash 表的形式存储数据，即在 Python 中采用字典方式添加 10000 个元素，然后检索这 10000 个数据，最后再统计一下时间。 代码如下： 
 <blockquote> 
 import time # 插入数据 result = {} for i in range(1000000): &nbsp; &nbsp; &nbsp; &nbsp;result[i] = i # 检索数据 time_start=time.time() for i in range(10000): &nbsp; &nbsp; &nbsp; &nbsp;temp = result[i] time_end=time.time() print('检索时间：',time_end-time_start) 
 </blockquote> 运行结果：检索时间为 0.0019941329956054688 秒。 你能看到 Hash 方式检索差不多用了 2 毫秒的时间，检索效率提升得非常明显。 
 <blockquote> 
 这是因为 Hash 只需要一步就可以找到对应的取值，算法复杂度为 O(1)，而数组检索数据的算法复杂度为 O(n)。 
 </blockquote> <h3>4.&nbsp;MySQL 中的 Hash 索引</h3> 采用 Hash 进行检索效率非常高，基本上一次检索就可以找到数据，而 B+ 树需要自顶向下依次查找，多次访问节点才能找到数据，中间需要多次 I/O 操作，从效率来说 Hash 比 B+ 树更快。 我们来看下 Hash 索引的示意图： <img alt="" src="https://img-blog.csdnimg.cn/img_convert/f9aa589ec29643a62b00062b9912bf86.png"> <h3></h3> 键值 key 通过 Hash 映射找到桶 bucket。 在这里桶（bucket）指的是一个能存储一条或多条记录的存储单位。 一个桶的结构包含了一个内存指针数组，桶中的每行数据都会指向下一行，形成链表结构，当遇到 Hash 冲突时，会在桶中进行键值的查找。 那么什么是 Hash 冲突呢？ 如果桶的空间小于输入的空间，不同的输入可能会映射到同一个桶中，这时就会产生 Hash 冲突，如果 Hash 冲突的量很大，就会影响读取的性能。 通常 Hash 值的字节数比较少，简单的 4 个字节就够了。 在 Hash 值相同的情况下，就会进一步比较桶（Bucket）中的键值，从而找到最终的数据行。 Hash 值的字节数多的话可以是 16 位、32 位等，比如采用 MD5 函数就可以得到一个 16 位或者 32 位的数值，32 位的 MD5 已经足够安全，重复率非常低。 我们模拟一下 Hash 索引。 关键字如下所示，每个字母的内部编码为字母的序号，比如 A 为 01，Y 为 25。我们统计内部编码平方的第 8-11 位（从前向后）作为 Hash 值： <img alt="" src="https://img-blog.csdnimg.cn/img_convert/b941ac36116ec22c892739ccf15ff5cf.png"> <h3></h3> <h3>5.&nbsp;Hash 索引与 B+ 树索引的区别</h3> 我们上面讲到过 B+ 树索引的结构，Hash 索引结构和 B+ 树的不同，因此在索引使用上也会有差别。 Hash 索引不能进行范围查询，而 B+ 树可以。 
 <blockquote> 
 这是因为 Hash 索引指向的数据是无序的，而 B+ 树的叶子节点是个有序的链表。 
 </blockquote> Hash 索引不支持联合索引的最左侧原则（即联合索引的部分索引无法使用），而 B+ 树可以。 
 <blockquote> 
 对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用。 
 </blockquote> Hash 索引不支持 ORDER BY 排序，因为 Hash 索引指向的数据是无序的，因此无法起到排序优化的作用，而 B+ 树索引数据是有序的，可以起到对该字段 ORDER BY 排序优化的作用。 同理，我们也无法用 Hash 索引进行模糊查询，而 B+ 树使用 LIKE 进行模糊查询的时候，LIKE 后面前模糊查询（比如 xx% 开头）的话就可以起到优化作用。 对于等值查询来说，通常 Hash 索引的效率更高，不过也存在一种情况，就是索引列的重复值如果很多，效率就会降低。 
 <blockquote> 
 这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。 
 </blockquote> <h3>6. 总结</h3> 从&nbsp;Hash 索引的底层原理，可以看到 Hash 索引存在着很多限制，相比之下在数据库中 B+ 树索引的使用面会更广，不过也有一些场景采用 Hash 索引效率更高，比如在键值型（Key-Value）数据库中，Redis 存储的核心就是 Hash 表。 另外 MySQL 中的 Memory 存储引擎【内存型存储引擎】支持 Hash 存储，如果我们需要用到查询的临时表时，就可以选择 Memory 存储引擎，把某个字段设置为 Hash 索引，比如字符串类型的字段，进行 Hash 计算之后长度可以缩短到几个字节。 当字段的重复度低，而且经常需要进行等值查询的时候，采用 Hash 索引是个不错的选择。 
 <blockquote> 
 另外 MySQL 的 InnoDB 存储引擎还有个“自适应 Hash 索引”的功能，就是当某个索引值使用非常频繁的时候，它会在 B+ 树索引的基础上再创建一个 Hash 索引，这样让 B+ 树也具备了 Hash 索引的优点。 
 </blockquote> <img alt="" src="https://img-blog.csdnimg.cn/img_convert/0087830a9b68a95c668b3ad7f281b07b.png"> <h3>7. 问题收集</h3> <h3>7.1&nbsp;所以老师能在稍微解释一下“自适应 Hash 索引”吗？自己查了一些资料，不是很懂。</h3> 
 <blockquote> 
 作者回复: 
 我们先回顾下B+树索引和Hash索引： B+树索引是MySQL的默认索引机制，也是大部分 因为可以使用范围搜索，可以很容易对数据进行排序操作，在联合索引中也可以利用部分索引建进行查询。这些情况下，我们都没法使用Hash索引，是因为Hash索引仅能满足=, &lt;&gt;, IN查询，不能使用范围查询，同时因为数据的存储是没有顺序的，所以在ORDER BY的情况下，还需要对数据重新进行排序。而对于联合索引的情况，Hash值是针对联合索引建合并后一起来计算Hash值，因此无法对单独的一个键或者几个索引键进行查询。 好了，默认使用B+树作为索引是因为B+树存在着以上的优点，那为什么还需要自适当Hash索引呢？ 
 这里，需要了解Hash索引的特点，因为Hash索引结构的特点，导致它的检索数据效率非常高，通常只需要O(1)的复杂度，也就是一次就可以完成数据的检索。虽然Hash索引的使用场景有很多限制，但是优点也很明显，所以MySQL提供了一个自适当Hash索引的功能（Adaptive Hash index）。注意，这里的自适应指的是不需要人工来制定，而是系统根据情况来自动完成的。 
 
 那什么情况下才会使用自适应Hash索引呢？ 
 如果某个数据经常会访问到，当满足一定条件的时候，就会将这个数据页的地址存放到Hash表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。 
 
 需要说明的是： 1）自适应哈希索引只保存热数据（经常被使用到的数据），并非全表数据。因此数据量并不会很大，可以让自适应Hash放到缓冲池中，也就是InnoDB buffer pool，进一步提升查找效率。 2）InnoDB中的自适应Hash相当于是“索引的索引”，采用Hash索引存储的是B+树索引中的页面的地址。这也就是为什么可以称自适应Hash为索引的索引。 采用自适应Hash索引目的是可以根据SQL的查询条件加速定位到叶子节点，特别是当B+树比较深的时候，通过自适应Hash索引可以提高数据的检索效率。 3）自适应Hash采用Hash函数映射到一个哈希表中，所以对于字典类型的数据查找非常方便 哈希表是数组+链表的形式。通过Hash函数可以计算索引键值所对应的bucket（桶）的位置，如果产生Hash冲突，如果产生哈希冲突，就需要遍历链表来解决。 4）是否开启了自适应Hash，可以通过innodb_adaptive_hash_index变量来查看，比如：mysql&gt; show variables like '%adaptive_hash_index'; 所以，总结下InnoDB本身不支持Hash，但是提供自适应Hash索引，不需要用户来操作，而是存储引擎自动完成的。自适应Hash也是InnoDB三大关键特性之一，另外两个分别是插入缓冲（Insert Buffer）和二次写(Double Write)。 
 </blockquote> <h3>7.2&nbsp;老师，你好，hash索引与B+树索引是在建索引的时候手动指定么</h3> 
 <blockquote> 
 作者回复: 
 在MySQL的InnoDB和如果使用的是MySQL的话，我们需要了解下MySQL的存储引擎都支持哪些索引结构，可以参考&nbsp;<a href="https://dev.mysql.com/doc/refman/8.0/en/create-index.html" rel="nofollow">https://dev.mysql.com/doc/refman/8.0/en/create-index.html</a> ） 针对MySQL 默认的存储引擎InnoDB，或者使用MyISAM存储引擎都会默认使用的是B+树来进行存储，无法使用Hash索引。 
 InnoDB提供的自适应Hash是不需要手动指定的。 
 如果是Memory/Heap，或者是NDB存储引擎，是可以进行选择的（Hash还是B+树）。 
 
 官网存储引擎支持的索引类型情况：&nbsp; 
 <img alt="" height="206" src="https://img-blog.csdnimg.cn/20210806175940650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbGxpYW1fbg==,size_16,color_FFFFFF,t_70" width="634"> 
 
 各存储引擎下，不同逻辑功能索引类型对各种参数支持情况： 
 <img alt="" height="1198" src="https://img-blog.csdnimg.cn/20210806180053508.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbGxpYW1fbg==,size_16,color_FFFFFF,t_70" width="1132"> 
 
 </blockquote> <h3>7.3&nbsp;查找某个固定值时 Hash 索引比 B+ 树更快，为什么 MySQL 还要采用 B+ 树的存储索引呢？</h3> <h3>另外，当两个关键字的 Hash 值相同时会发生什么？</h3> 
 <blockquote> 
 问题一原因：Hash索引有很大的限制，如联合索引、模糊查询、范围查询，以及列里有重复值多都不支持。 问题二会发生：需要遍历链表中所有行指针，逐一进行比较，直到找到所有符合条件的 
 </blockquote> 后续补充 ... </td> 
 </tr> 
 </tbody> 
</table>

3.问题/补充

<table> 
 <tbody> 
 <tr> 
 <td> <h3>1. MySQL InnerDB存储引擎中的“自适应 Hash 索引”是什么吗？</h3> 
 <blockquote> 
 作者回复: 我们先回顾下B+树索引和Hash索引： B+树索引是MySQL的默认索引机制，也是大部分 因为可以使用范围搜索，可以很容易对数据进行排序操作，在联合索引中也可以利用部分索引建进行查询。这些情况下，我们都没法使用Hash索引，是因为Hash索引仅能满足=, &lt;&gt;, IN查询，不能使用范围查询，同时因为数据的存储是没有顺序的，所以在ORDER BY的情况下，还需要对数据重新进行排序。而对于联合索引的情况，Hash值是针对联合索引建合并后一起来计算Hash值，因此无法对单独的一个键或者几个索引键进行查询。 好了，默认使用B+树作为索引是因为B+树存在着以上的优点，那为什么还需要自适当Hash索引呢？这里，需要了解Hash索引的特点，因为Hash索引结构的特点，导致它的检索数据效率非常高，通常只需要O(1)的复杂度，也就是一次就可以完成数据的检索。虽然Hash索引的使用场景有很多限制，但是优点也很明显，所以MySQL提供了一个自适当Hash索引的功能（Adaptive Hash index）。注意，这里的自适应指的是不需要人工来制定，而是系统根据情况来自动完成的。 那什么情况下才会使用自适应Hash索引呢？如果某个数据经常会访问到，当满足一定条件的时候，就会将这个数据页的地址存放到Hash表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。需要说明的是： 1）自适应哈希索引只保存热数据（经常被使用到的数据），并非全表数据。因此数据量并不会很大，可以让自适应Hash放到缓冲池中，也就是InnoDB buffer pool，进一步提升查找效率。 2）InnoDB中的自适应Hash相当于是“索引的索引”，采用Hash索引存储的是B+树索引中的页面的地址。这也就是为什么可以称自适应Hash为索引的索引。 采用自适应Hash索引目的是可以根据SQL的查询条件加速定位到叶子节点，特别是当B+树比较深的时候，通过自适应Hash索引可以提高数据的检索效率。 3）自适应Hash采用Hash函数映射到一个哈希表中，所以对于字典类型的数据查找非常方便 哈希表是数组+链表的形式。通过Hash函数可以计算索引键值所对应的bucket（桶）的位置，如果产生Hash冲突，如果产生哈希冲突，就需要遍历链表来解决。 4）是否开启了自适应Hash，可以通过innodb_adaptive_hash_index变量来查看，比如：mysql&gt; show variables like '%adaptive_hash_index'; 所以，总结下InnoDB本身不支持Hash，但是提供自适应Hash索引，不需要用户来操作，而是存储引擎自动完成的。 
 自适应Hash也是InnoDB三大关键特性之一，另外两个分别是插入缓冲（Insert Buffer）和二次写(Double Write)。 
 </blockquote> 2. B+树 与 跳表的区别？--- Coming from time.geekbang.org 算法与数据结构专栏 
 <blockquote> 
 Harry陈祥&nbsp;2019-02-21 您好。 
 有次面试，面试官直接问我，什么数据结构可以做到O(logn)的范围查询？ 
 当时没有想到填表，想到了B+树，而且数据库索引确实也是用的B+树。 那么问题来了，跳表和B+树在实现难度和性能上有什么区别，在数据量很大的情况下，表现性能如何，为什么redis选跳表？ 
 谢谢老师 
 作者回复: 
 b+树主要是用在外部存储上，为了减少磁盘IO次数。 跳表比较适合内存存储。 实际上，两者本质的设计思想是雷同的，性能差距还是要具体看应用场景，无法从时间复杂度这么宽泛的度量标准来度量了。 
 </blockquote> </td> 
 </tr> 
 </tbody> 
</table>

4.参考

<table> 
 <tbody> 
 <tr> 
 <td> <a href="https://time.geekbang.org/column/article/112298" rel="nofollow">https://time.geekbang.org/column/article/112298</a>&nbsp;// 24丨索引的原理：我们为什么用B+树来做索引？ <a href="https://time.geekbang.org/column/article/113669" rel="nofollow">https://time.geekbang.org/column/article/113669</a>&nbsp; // 25丨Hash索引的底层原理是什么？ <a href="https://time.geekbang.org/column/article/64233" rel="nofollow">https://time.geekbang.org/column/article/64233</a>&nbsp;//&nbsp;18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？ <a href="https://time.geekbang.org/column/article/64586" rel="nofollow">https://time.geekbang.org/column/article/64586</a>&nbsp;//&nbsp;19 | 散列表（中）：如何打造一个工业级水平的散列表？ <a href="https://time.geekbang.org/column/article/64858" rel="nofollow">https://time.geekbang.org/column/article/64858</a>&nbsp;//&nbsp;20 | 散列表（下）：为什么散列表和链表经常会一起使用？ <a href="https://time.geekbang.org/column/article/77830" rel="nofollow">https://time.geekbang.org/column/article/77830</a>&nbsp;// 48 | B+树：MySQL数据库索引是如何实现的？ <a href="https://xueyuanjun.com/post/21942" rel="nofollow">https://xueyuanjun.com/post/21942</a>&nbsp; // 存储引擎系列（二）：数据库索引底层数据结构 —— B+ 树 <a href="https://xueyuanjun.com/post/21946" rel="nofollow">https://xueyuanjun.com/post/21946</a>&nbsp; // 存储引擎系列（三）：不同类型的数据库索引 B+ 树是如何维护的 <a href="https://time.geekbang.org/column/article/127873" rel="nofollow">https://time.geekbang.org/column/article/127873</a>&nbsp;//&nbsp;34丨答疑篇：关于索引以及缓冲池的一些解惑 <a href="https://blog.csdn.net/william_n/article/details/100827803" rel="nofollow">https://blog.csdn.net/william_n/article/details/100827803</a>&nbsp;//&nbsp;MySQL 索引 - 学习/实践 </td> 
 </tr> 
 </tbody> 
</table>

后续补充

...