54-MySQL(哈希索引,InnoDB自适应哈希索引)

哈希索引（memory支持）

memory引擎： 基于内存的存储引擎，支持哈希索引。

在可管理的负载因子范围内哈希表中的链式哈希表表现出尤为突出的时间复杂度特性，在该方案下实现的增删查改等基本操作均能够达到理论上的最优时间复杂度O(1)

Hash Index 是一种通过 数据结构 实现的存储和检索机制（其中一种具体实现方式为链式哈希表）。该机制通过将键映射到特定的位置以达到快速定位数据的目的。

AVL 树 的 插 入 、 删 除 操作 以 及 查 找 运 算 在 最 坏 情 况 下 具 有 较 低 的 时间 开 支 ， 其 复 杂 度 被 上 界 估 计 为 O(logn)。
B+ 树 是 一 种 优 化 数据 库 查询 效 率 的 数据 结 构 。 它 是 通 过 将 部 分 高 频 访 问 的 数 据 存 存 在 内 存 中 来 提 高 访 问 速 度 。 B+ 树 核 心 的 功 能 即 是 组 织 和 管 理 数 据 ， 其 中 包 含 关 键 字 符 和 对 应 的 引 数 指 针 ， 并 能 够 实 现 快 �MixedSearch

看起来哈希表在某些方面确实具有优势，
然而为何MyISAM与InnoDB等存储引擎仍采用基于B+树的索引方案呢？
我们主要关注以下几个关键指标：

• 搜索的效率如何
• 磁盘I/O操作的成本是多少

我们改用创建哈希索引来看看：

事实上，在使用show create命令查看索引创建信息时，默认会显示一些附加标记用于后续管理操作。经验证明确的是其底层是否采用哈希技术存在疑问。

我们看到，都是B+树！！！

在默认情况下，默认存储引擎被设定为memory该存储引擎基于内存实现，并支持哈希索引其数据及索引信息全部存于内存中一旦断电则信息将丢失

现在默认选择的是哈希索引：

构建链式哈希表：

通过选择特定的哈希函数对每一行记录中的name字段进行处理以计算其对应的唯一标识码该标识码决定了数据会被分配到特定的存储桶中（这可能导致不同记录被映射到同一存储桶的情况发生）

处理哈希冲突的方法：将哈希冲突时的多个数据项存储到同一个桶中，并通过建立链表结构进行组织。（链地址法）

哈希索引存储于内存中，并且其中的数据字段通过指针引用与外部的数据进行关联；每个索引项中所存储的是对应内存区域中的数据地址。

哈希表在增删查操作上表现出色，其时间复杂度为O(1)。然而由于其元素存储方式的特点，在哈希表内部是没有特定顺序排列的。因此，在采用哈希表构建索引时我们仅支持等值查找功能。

我们再看：

无需使用索引；由于无法确定数值的大小，并且无法保证位于同一分块。

对于哈希表而言，并不适合进行范围搜索、前缀搜索以及排序操作（order by）。
在哈希表中存储不同元素时，默认情况下即使相邻元素如15和16也非常接近，在计算其对应的哈希值后进行取模运算后也可能分属不同的桶。
如果采用链式哈希表构建索引结构，则每个节点对应一次磁盘访问操作（磁盘I/O），除非是等值查找操作，在这种情况下该方法效率极低。
基于此可知，在内存中的数据使用时可实现高效的增删查操作（增删查速度很快），但其查询功能仅适合于等值匹配场景。
值得注意的是这种方法无法有效降低磁盘读取次数（I/O operations）！

InnoDB自适应哈希索引

注意：

InnoDB自适应哈希索引模块是InnoDB数据库内生式地建立的（而非memory缓存层上的哈希索引），它是基于B+树构建的一个优化结构，在B+树二级索引的基础上进一步提升性能。该功能无需我们主动去创建相关索引项，在InnoDB内部进行管理维护；

自适应： 自动，优化的功能，加速搜索

数据在内存上，哈希表中存的是二级索引的值和数据的指针。

当InnoDB二级索引表无法获取所需字段信息时，系统将执行一次表内扫描。随后转向主键索引结构以完成搜索过程。

如果是 InnoDB存储引擎

• 如果系统检测到同一个二级索引节点反复被引用（例如：select *语句涉及回表操作并需要搜索主键索引树）；
  • 那么系统将根据该二级索引节点在内存中按照B+树结构中的相应子节点值来建立一个哈希表以加速搜索过程（仅进行等值比较操作）；
  • 现在通过O(1)时间复杂度快速定位到name字段后直接访问其data指针即可显著提升数据获取速度。

自动的功能，优化的功能，加快搜索。

该过程采用蓝色箭头指示先进行二级索引结构查找操作，在确定主键值后进而利用主键索引树定位目标数据存储位置。如今采用构建哈希索引的方式替代原有方法，在具体实现中只需输入name=‘zhangsan’即可快速定位到对应的数据存储指针位置（如图所示），从而实现了对数据页的直接访问。

优点：

• 优化了在B+树中大量依赖于第二层和主键索引进行查询的过程。

• 在B+树中大量依赖于第二层和主键索引进行查询，并对这些操作进行了改进以提升性能。

• 生成及维护hash索引的过程会消耗性能资源。为了实现高效的数据库操作需求，在实际应用中我们需要建立基于参数配置的评估体系。具体而言，在满足特定条件时（如预设的参数配置能够带来性能提升），我们可以启用自适应哈希索引功能；而当发现该功能可能导致系统性能下降（即其成为潜在的压力源）时，则应考虑关闭该功能。

• MySQL官方文档对此进行了详细说明：自适应哈希索引无法保证在所有情况下都提升搜索效率。

自适应哈希索引无法在任何情况下有效地提升二级索引搜索的效果

在分区机制中，对于单个链表或数组结构进行并行操作时，必须加锁以防止数据竞争。而对于不同桶之间的数据处理，则无需加锁。

每一个索引被分到1个分区。

• 自适应哈希索引默认已启用。
• 在MySQL 5.7版本中，默认情况下对自适应哈希表中的搜索系统进行了分片划分。每个哈希表都会与特定的分片相关联，并且每个分片都独立地由一个锁存器进行保护。
• 分片的数量是由innodb _ adaptive _ hash _ index _ parts配置选项来决定的。
• 在早期版本中，默认情况下自适应散列表搜索系统仅使用一个锁存器进行保护；这种设计在处理高负载数据时可能会导致性能瓶颈。
• 为了提高性能，在当前版本中，默认情况下innodb _ adaptive _ hash _ index _ parts被设置为8（最小值），最大值设定为512。
• 哈希表通常都是基于现有表上的B+树结构进行构建的。
• InnoDB能够根据不同的关键字长度生成相应的散列索引；这种生成过程是基于InnoDB对B树索引搜索模式的观察结果。
• 散列索引具有灵活性，在构建时可以选择是否覆盖所有页面（全表覆盖）或者仅覆盖那些经常被访问到的数据页码（部分覆盖）。
• InnoDB支持根据B树定义不同长度的关键字前缀上的散列索引；
• 这种散列索引的设计取决于InnoDB对B树索引搜索模式的具体实现；
• 部分哈希表可以在不同的时间点上进行优化配置以提高查询效率

• 您能够监控自适应哈希索引的使用情况，并且也能查看SHOW ENGINE INNODB STATUS命令输出的相关信号量。
• 如果遇到大量线程等待btr0sea.c中建立的读写锁时，请考虑暂时禁用该机制可能会有所帮助。（实际上建议继续使用传统的二级索引树结构进行搜索）

哈希索引的使用情况：

将数据划分为8个区域；其中对于hash类型的搜索，“0.00”代表占比为零；当实际值较高时，则表明该类型的数据在使用量上相对较多。（自适应哈希索引在性能上表现出明显优势）而对于非hash类型的搜索，“0.00”同样代表占比为零；当实际值较高时，则表明该类型的数据在查询比例上有显著提升。（经过测试分析发现该优化措施并未带来实质性能提升因此建议予以关闭）

分区：默认是8给个分区
每个分区管理1个或多个桶

自5.7版本起，在每个区域都分配了一把锁；多个区域能够同时进行操作；且在同一区域内的所有操作必须使用同一把锁来控制。