阿里面试官:设计个MySQL的Hash索引吧?

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介: 阿里面试官:设计个MySQL的Hash索引吧?

除了B-Tree 索引,MySQL还提供了如下索引:


Hash索引

只有Memory引擎支持,场景简单

R-Tree索引

MyISAM的一个特殊索引类型,主要用于地理空间数据类型

Full-text

MyISAM的一个特殊索引,主要用于全文索引,从MySQL 5.6开始InnoDB支持全文索引

索引 / 存储引擎 MyISAM InnoDB Memory
B-Tree索引 支持 支持 支持
HASH索引 不支持 不支持 支持
R-Tree索引 支持 支持 不支持
Full-text索引 支持 支持 不支持

最常用的索引也就是B-tree索引和Hash索引,且只有Memory,NDB两种引擎支持Hash索引。

Hash索引适于key-value查询,通过Hash索引比B-tree索引查询更加迅速。但Hash索引不支持范围查找例如<><==,>==等。

Memory只有在"="的条件下才会使用hash索引

MySQL在 8.0才支持函数索引,在此之前是能对列的前面某一部分进行索引,例如标题title字段,可以只取title的前10个字符索引,这样的特性大大缩小了索引文件的大小,但前缀索引也有缺点,在order by和group by操作时失效。

create index idx_title on film(title(10));

1 特点

值存在数组,用一个hash函数把key转换成一个确定的内存位置,然后把value放在数组的该位置。使用 hash 自然会有哈希冲突可能,MySQL 采取拉链法解决。

Hash索引基于Hash表实现,只有查询条件精确匹配Hash索引中的列时,才能够使用到hash索引。对于Hash索引中的所有列,存储引擎会为每行计算一个hashcode,Hash索引中存储的就是hashcode。


例如一个维护了身份证号和姓名的表,根据身份证号查找对应名字,其hash索引如下:

image.png

比如我们想查ID_card_n4对应username:


将ID_card_n4通过hash函数算出A

按顺序遍历,找到User4

四个ID_card_n值并不一定递增,这样即使增加新的User,速度也快,只需在后追加。

当然缺点也很明显,不是有序,所以hash索引做区间查询速度很慢。比如要找身份证号在[ID_card_X, ID_card_Y]区间的所有用户,就须全表扫描。

2 Hash索引的缺陷

不支持部分索引查找、范围查找

哈希码可能存在哈希冲突,如果hash 算法设计不好,碰撞过多,性能也会变差

索引存放的是hash值,所以仅支持 < = > 以及 IN

无法通过操作索引来排序,因为存放的时候会经过hash计算,但是计算的hash值和存放的不一定相等,所以无法排序

不能避免全表扫描,只是由于在memory表里支持非唯一值hash索引,即不同的索引键,可能存在相同hash值

因为哈希表是一种根据关键字直接访问内存存储位置的数据结构 ,所以利用其原理的hash 索引,也就需要将所有数据文件添加到内存,这就很耗内存

如果所有的查询都是等值查询,那么hash确实快,但实际上范围查找数据更多

只能处理键值的全值匹配查询

Hash函数决定着索引键的大小

要使InnoDB或MyISAM支持哈希索引,可以通过伪哈希索引来实现,叫自适应哈希索引。

可通过增加一个字段,存储hash值,将hash值建立索引,在插入和更新的时候,建立触发器,自动添加计算后的hash到表里。


哈希表这种结构适用于只有等值查询的场景,比如Memcached。

3 案例应用

假如有一个非常非常大的表,比如用户登录时需要通过email检索出用户,如果直接在email列建索引,除了索引区间匹配,还要进行字符串匹配比对,email短还好,如果长的话这个查询代价就比较大。

若此时,在email建立哈希索引,查询以int查询,性能就比字符串比对查询快多了。

Hash 算法

建立哈希索引,首先就要选定哈希算法,《高性能MySQL》说到的CRC32算法。

INSERT UPDATE SELECT 操作

在表中添加hash值的字段:

ALTER TABLE `User` ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;

接下来就是在UPDATE和INSERT时,自动更新 email_hash 字段,通过触发器实现:

DELIMITER |
CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
DELIMITER ;

这样SELECT请求就会变成:

SELECT `email`, `email_hash` FROM `User` WHERE 
  email_hash = CRC32(“xxoo@gmail.com”) 
      AND `email`= “xxoo@gmail.com”;
+----------------------------+------------+
| email                      | email_hash |
+----------------------------+------------+
| xxoo@gmail.com             | 2765311122 |
+----------------------------+------------+

AND email = "xxoo@gmail.com" 是为了防止哈希碰撞时数据不准确。

相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
15天前
|
缓存 关系型数据库 MySQL
MySQL索引策略与查询性能调优实战
在实际应用中,需要根据具体的业务需求和查询模式,综合运用索引策略和查询性能调优方法,不断地测试和优化,以提高MySQL数据库的查询性能。
|
16天前
|
SQL 关系型数据库 MySQL
大厂面试官:聊下 MySQL 慢查询优化、索引优化?
MySQL慢查询优化、索引优化,是必知必备,大厂面试高频,本文深入详解,建议收藏。关注【mikechen的互联网架构】,10年+BAT架构经验分享。
大厂面试官:聊下 MySQL 慢查询优化、索引优化?
|
2月前
|
存储 关系型数据库 MySQL
阿里面试:为什么要索引?什么是MySQL索引?底层结构是什么?
尼恩是一位资深架构师,他在自己的读者交流群中分享了关于MySQL索引的重要知识点。索引是帮助MySQL高效获取数据的数据结构,主要作用包括显著提升查询速度、降低磁盘I/O次数、优化排序与分组操作以及提升复杂查询的性能。MySQL支持多种索引类型,如主键索引、唯一索引、普通索引、全文索引和空间数据索引。索引的底层数据结构主要是B+树,它能够有效支持范围查询和顺序遍历,同时保持高效的插入、删除和查找性能。尼恩还强调了索引的优缺点,并提供了多个面试题及其解答,帮助读者在面试中脱颖而出。相关资料可在公众号【技术自由圈】获取。
|
1月前
|
SQL 缓存 关系型数据库
美团面试:Mysql 有几级缓存? 每一级缓存,具体是什么?
在40岁老架构师尼恩的读者交流群中,近期有小伙伴因未能系统梳理MySQL缓存机制而在美团面试中失利。为此,尼恩对MySQL的缓存机制进行了系统化梳理,包括一级缓存(InnoDB缓存)和二级缓存(查询缓存)。同时,他还将这些知识点整理进《尼恩Java面试宝典PDF》V175版本,帮助大家提升技术水平,顺利通过面试。更多技术资料请关注公号【技术自由圈】。
美团面试:Mysql 有几级缓存? 每一级缓存,具体是什么?
|
17天前
|
SQL 关系型数据库 MySQL
阿里面试:1000万级大表, 如何 加索引?
45岁老架构师尼恩在其读者交流群中分享了如何在生产环境中给大表加索引的方法。文章详细介绍了两种索引构建方式:在线模式(Online DDL)和离线模式(Offline DDL),并深入探讨了 MySQL 5.6.7 之前的“影子策略”和 pt-online-schema-change 方案,以及 MySQL 5.6.7 之后的内部 Online DDL 特性。通过这些方法,可以有效地减少 DDL 操作对业务的影响,确保数据的一致性和完整性。尼恩还提供了大量面试题和解决方案,帮助读者在面试中充分展示技术实力。
|
24天前
|
SQL 算法 关系型数据库
面试:什么是死锁,如何避免或解决死锁;MySQL中的死锁现象,MySQL死锁如何解决
面试:什么是死锁,死锁产生的四个必要条件,如何避免或解决死锁;数据库锁,锁分类,控制事务;MySQL中的死锁现象,MySQL死锁如何解决
|
28天前
|
监控 关系型数据库 MySQL
数据库优化:MySQL索引策略与查询性能调优实战
【10月更文挑战第27天】本文深入探讨了MySQL的索引策略和查询性能调优技巧。通过介绍B-Tree索引、哈希索引和全文索引等不同类型,以及如何创建和维护索引,结合实战案例分析查询执行计划,帮助读者掌握提升查询性能的方法。定期优化索引和调整查询语句是提高数据库性能的关键。
158 1
|
1月前
|
SQL 关系型数据库 MySQL
美团面试:Mysql如何选择最优 执行计划,为什么?
在40岁老架构师尼恩的读者交流群中,近期有小伙伴面试美团时遇到了关于MySQL执行计划的面试题:“MySQL如何选择最优执行计划,为什么?”由于缺乏系统化的准备,小伙伴未能给出满意的答案,面试失败。为此,尼恩为大家系统化地梳理了MySQL执行计划的相关知识,帮助大家提升技术水平,展示“技术肌肉”,让面试官“爱到不能自已”。相关内容已收录进《尼恩Java面试宝典PDF》V175版本,供大家参考学习。
|
2月前
|
存储 关系型数据库 MySQL
如何在MySQL中进行索引的创建和管理?
【10月更文挑战第16天】如何在MySQL中进行索引的创建和管理?
72 1
|
29天前
|
监控 关系型数据库 MySQL
数据库优化:MySQL索引策略与查询性能调优实战
【10月更文挑战第26天】数据库作为现代应用系统的核心组件,其性能优化至关重要。本文主要探讨MySQL的索引策略与查询性能调优。通过合理创建索引(如B-Tree、复合索引)和优化查询语句(如使用EXPLAIN、优化分页查询),可以显著提升数据库的响应速度和稳定性。实践中还需定期审查慢查询日志,持续优化性能。
67 0