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

桃扇骨 2022-09-06 10:17 259阅读 0赞

## 哈希索引（memory支持） ##

**memory：基于内存的存储引擎**  
**哈希表**在可控的冲突范围，我们经常写的链式哈希表，它的增删改查的时间复杂度都是O(1)  
**哈希索引，基于哈希表这个数据结构实现的**  
链式哈希表：

**平衡树**的增删改查的时间复杂度是O(logn)  
**B+树索引**就是把磁盘上的存储的索引加载到内存上构建的数据结构，索引就是数据结构。

**看起来哈希表比B+树好。  
但是为什么MyISAM和InnoDB存储引擎用的是B+树索引？**  
我们主要看  
1、搜索的效率：  
2、磁盘I/O的花费：

**我们改用创建哈希索引来看看**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**实际上，show create 只是显示你创建索引的标志，底层到底是不是哈希索引是不准的**

**这个是准的**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**都是B+树**

## 假设现在默认存储引擎是memory ##

**默认选择的是哈希索引**  
![在这里插入图片描述][30d91321b26e44dcb36e4a0b1bf63f9b.png]  
**构建链式哈希表**  
根据选定的哈希函数，把每一行记录的name字段作为参数来求一个哈希值  
，哈希值相当于桶的序号。（哈希冲突）  
解决哈希冲突：在桶里面用链表串起来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**哈希表的增删查效率高，是O(1)，但是哈希表中的元素没有任何顺序可言。  
意味着如果用哈希表来构建索引的话，我们只能进行等值比较。**  
![在这里插入图片描述][90960dbb644e45cc94475b4617bbbacc.png]  
**像上面这个，就用不着索引了。**  
**不能确保**  
![在这里插入图片描述][c7b3e8ece44f4d27b02c2eb778c0309b.png]  
**在一个桶中**  
**对于哈希表来说，不能做范围搜索和前缀搜索和order by**  
**在哈希表中，不同元素，哪怕是15和16，很近，通过求哈希值，模上一个桶的个数，可能就不在一个桶中了。**

**如果用链式哈希表构建索引，一个桶里面的节点代表1次磁盘I/O，除非是等值搜索，不然就太慢了。**  
**哈希索引只适用于数据都在内存上，仅仅适合等值查询。**  
**不能为我们减少磁盘I/O的次数**  
![在这里插入图片描述][ee91d56775414faebd2ebf6494d36fa4.png]

## InnoDB自适应哈希索引 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
**如果 InnoDB存储引擎**监测到同样的二级索引不断被使用（select \*，要回表，要搜主键索引树），那么它会根据这个**二级索引**在内存上根据二级索引树(B+树）上的二级索引的值，在内存上构建1个哈希索引来加速搜索（只有等值比较）  
**O(1)的时间复杂度就访问到name了，然后直接访问它的数据data指针，就可以速度更快了**

**自动的功能，优化的功能，加快搜索**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
蓝色的箭头先搜二级索引树，再通过二级索引树找到主键，再通过主键索引树找到相应的数据页。现在是用二级索引直接构建哈希索引了，name=‘zhangsan’，通过这个哈希表找到‘zhangsan’直接得到data的指针了，就是图中的黄色箭头，直接访问到数据页了。  
**省了二级索引树和主键索引树的搜索过程**  
**对B+树上频繁使用二级索引搜索并且进行回表操作的优化！**  
**hash索引的生成和维护也是耗费性能的**，**我们有参数指标，通过参数指标查看，如果自适应哈希索引可以提供效率，那我们使用它，如果它成为性能的损坏，我们就关闭自适应哈希索引。**  
**自适应哈希索引并不能绝对的在任何场景下提高对二级索引搜索的效率**  
**分区**：要是在一个链表或者数组进行并行操作，只能加锁。要是在不同的桶操作，就不用加锁。  
每一个索引被分到1个分区。  
![在这里插入图片描述][763f9ec741114ae682e16be66cf031c6.png]  
**默认开启**

**在MySQL 5.7中，对自适应哈希索引搜索系统进行了分区。每个索引都绑定到一个特定的分区，并且每个分区都由单独的锁存器保护。**  
分区由innodb \_ adaptive \_ hash \_ index \_ parts配置选项控制。在…里  
在早期版本中，自适应散列索引搜索系统由一个锁存器保护，该锁存器  
在繁重的工作负载下可能会成为争夺点。这innodb \_ adaptive \_ hash \_ index \_ parts选项默认设置为8。最大设置为512。  
**哈希索引总是基于表上现有的B+树索引构建的**。**InnoDB可以构建一个  
为B树定义的任何长度的关键字的前缀上的散列索引**，  
这取决于InnoDB观察到的B树索引的搜索模式。**散列索引可以是部分的**，只覆盖索引中那些经常被访问的页面。  
您可以监视自适应哈希索引的使用以及在**SHOW ENGINE INNODB STATUS**命令输出的信号量部分。如果你看到许多线程在等待btr0sea.c中创建的读写锁，那么禁用它可能是有用的自适应散列索引。  
![在这里插入图片描述][ac87ee77847f4c0f8c870d41f6c442c5.png]

**分区：**  
![在这里插入图片描述][b1d95aef9db945888210fe2285c3ea89.png]  
**5.7以后，每个分区都有1把锁**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/4f8f25c6e50c4472a93ee4e15a990ccc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/b8ad94ae8b5147d88a4583fc0901907e.png
[30d91321b26e44dcb36e4a0b1bf63f9b.png]: /images/20220829/b9d2f25621c64b32adae0dec482bffd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/9df09d3cbcfd4ea08a9b0b23b6022460.png
[90960dbb644e45cc94475b4617bbbacc.png]: /images/20220829/000c9c41795b47c3a95eba416b65cd4f.png
[c7b3e8ece44f4d27b02c2eb778c0309b.png]: /images/20220829/54abae4e1d04449484921ef3308cc2c3.png
[ee91d56775414faebd2ebf6494d36fa4.png]: /images/20220829/7006769e610240cbb0c84d7ba9462db5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/8eeaf2497d654117bf214ab7d13f2a05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/14301cf6a00d421593fca9f22348a414.png
[763f9ec741114ae682e16be66cf031c6.png]: /images/20220829/8ff3227b2539445a9940fbd4c2d696e7.png
[ac87ee77847f4c0f8c870d41f6c442c5.png]: /images/20220829/26845ef816a14c779b9c2339fcd40992.png
[b1d95aef9db945888210fe2285c3ea89.png]: /images/20220829/c1ac5a534b1e461f94513e5ac06538b5.png