第18期:索引设计(认识哈希表)
ccwgpt 2024-12-31 09:55 69 浏览 0 评论
MySQL 的默认索引结构是 B+ 树,也可以指定索引结构为 HASH 或者 R 树等其他结构来适应不同的检索需求。这里我们来介绍 MySQL 哈希索引。
MySQL 哈希索引又基于哈希表(散列表)来实现,所以了解什么是哈希表对 MySQL 哈希索引的理解至关重要。接下来,我们来一步一部介绍哈希表。
1. 数组
数组是最常用的数据结构,是一种线性表的顺序存储方式,由下标(也叫索引)和对应的值构成。数组在各个开发语言以及数据库中都有类似的结构,类似下图1:
图 1 展示了一个一维整数数组,数组的长度为 10,下标从 0-9, 每个下标对应不同的值。每种编程语言基本上都有数组,大部分数据库也提供了数组或者是类似数组的结构,MySQL 也有数组,以下为 MySQL 的一维数组:
mysql> select @a as "array",json_length(@a) as "array_size";
+-------------------------------------------+------------+
| array | array_size |
+-------------------------------------------+------------+
| [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] | 10 |
+-------------------------------------------+------------+
1 row in set (0.00 sec)
数组元素也可以是数组,这样的表示称为多维数组,如图 2,一个二维字符串数组:
以下为 MySQL 里的多维数组:
mysql> select json_pretty(@a)\G
*************************** 1. row ***************************
json_pretty(@a): [
[
"mysql",
"db2"
],
[
"oracle",
"mongodb",
"sql server",
"redis"
],
[
"memcached",
"dble",
"postgresql",
"mariadb"
]
]
1 row in set (0.01 sec)
数组优缺点如下,
优点:
数组最大的优点是可以根据下标来快速读取到对应的值,通俗的说法就是时间复杂度为 O(1)。
缺点:
1)对数组的写入(插入或者删除)要涉及到原下标对应值的迁移以及新下标的生成;
2) 数组存储需要一块连续的存储区域,后期数组扩容需要申请新的连续存储区域,造成空间浪费。
2. 字典
字典和数组结构类似,不同的是,下标并非是从 0 开始的数字,而是任意的字符串。有的程序语言里把字典也叫数组,由 Key 映射为对应的 value,字典的结构类似于图 2:
MySQL 也同样提供了这样的字典,比如下面定义了一个字典,存入变量 @a,把图 2 里前 4 个元素拿出来,对应的 value 分别为 “mysql","db2","oracle","mongodb".
mysql> set @a='{"10":"mysql","20":"db2","30":"oracle","40":"mongodb"}';
Query OK, 0 rows affected (0.00 sec)
mysql> select json_keys(@a);
+--------------------------+
| json_keys(@a) |
+--------------------------+
| ["10", "20", "30", "40"] |
+--------------------------+
1 row in set (0.00 sec)
mysql> set @x1=json_extract(@a,'$."10"');
Query OK, 0 rows affected (0.01 sec)
mysql> set @x2=json_extract(@a,'$."20"');
Query OK, 0 rows affected (0.00 sec)
mysql> set @x3=json_extract(@a,'$."30"');
Query OK, 0 rows affected (0.00 sec)
mysql> set @x4=json_extract(@a,'$."40"');
Query OK, 0 rows affected (0.00 sec)
mysql> select @x1 "dict['10']", @x2 "dict['20']", @x3 "dict['30']", @x4 "dict['40']";
+------------+------------+------------+------------+
| dict['10'] | dict['20'] | dict['30'] | dict['40'] |
+------------+------------+------------+------------+
| "mysql" | "db2" | "oracle" | "mongodb" |
+------------+------------+------------+------------+
1 row in set (0.00 sec)
3. 链表
链表也是一种线性表的存储结构,但是和数组不一样,存储线性表数据的单元并非顺序的。每个元素(也叫节点)包含了自己的值以及指向下一个元素地址的指针。
比如图 3,一个单线链表,MySQL 的 B+ 树索引叶子节点就是一个链表结构。
链表的优缺点如下,
优点:
1) 链表不需要连续的存储区域,任何空余的存储区域都可以保存链表元素,只要指针指向正确的地址即可。
2) 对链表的更改(插入或者删除)操作非常快,时间复杂度为 O(1),只需要更改节点对应的指针即可,不需要挪动任何数据。比如上图,往 “MySQL” 和 “DB2” 中间插入一个新的元素 “maxdb”,只需要把 “MySQL" 的指针指向 “maxdb",同时把 "maxdb" 的指针指向 "db2" 即可。
缺点:
无法快速定位到指定的元素,必须从链表开头的第一个元素顺序查找,假设要查找的元素是链表的最后一个,那需要把每个元素都扫描一遍,时间复杂度为 O(N) 。
4. 哈希表(散列表)
哈希表(散列表),表现为根据 {key,value}(类似字典)直接访问的一种数据结构。哈希表一般用数组来保存,其中下标是根据一个固定的函数 func1(散列函数)带入参数 key 计算的结果,value 为对应的数据。对于数组 a 来说,a[func1(key)] = value。比如图 4,func1 这里为取模函数 mod(key,9):
从上图可以发现以下几个问题:
1)数组的值直接保存了对应的 VALUE,比如相同下标对应多个 VALUE,每个 VALUE 本身又占用很大空间,那查询这样的 VALUE 时,就得在内存中申请一块连续的存储区域。
2)数组的写入效率很差,VALUE 存在数据的值里是否合适?
3) 数组的下标生成有重复,也就是说散列函数的结果不唯一,也叫散列值发生碰撞。
那如何规避掉以上问题? 答案是肯定的!
针对前两个问题,可以把数组和链表结合起来,这样既可以使用数组的高性能随机读,又能使用链表的高性能随机写,这种一般叫做拉链法,见图 5:
图 5 所示的散列表依然用数组保存,下标为散列函数根据 KEY 计算的结果,值变为指向一个链表的指针,链表里保存了对应的 VALUE,这样的优点是数组本身占用空间不大,后期需要扩容效率也高。
比如查找 key 为 20 对应的 VALUE,通过函数 func1 计算得到结果为 2,就可以很快找到下标为 2 的值。
那接下来看图 4 里发现的最后一个问题,散列函数的选择。理论上来讲,对任何键值都有可能存在一个完美的散列函数并且不会发生任何碰撞,但是现实场景中找一个散列碰撞极少的散列函数就已经很优化了。
大致有两个层面要考虑,
1) 数据分布
比如上面的取模函数,针对整数类型集合,如果除数足够大,其生成结果产生的碰撞几率就足够小。举个简单例子,
以下 Key 集合 {1,2,...,1000000},有 100W 个元素,每个元素类型都为无符号整数,那这样,可以用最大值 1000000 来做基数取模,每个值的散列结果都唯一。但是这个得提前获知集合的大小以及类型。
2) 散列函数的效率
散列表能快速查找,归功于散列函数的快速计算,如果一个散列函数计算耗时很久,那对应的散列表查找也就不可能很快。一般来说,散列函数的复杂度都假设为趋近于 O(1),一个好的散列函数理论上应该是稳定、快速。比如 MySQL 的哈希分区就用的函数 password。下图 6 是基于一个非常差的散列函数生成的散列表。可以看到结果多次碰撞,应该避免这种场景发生。
对上图中的散列表来说,不可能快速检索。不过可以考虑当链表到达一定的长度后,把链表变为一棵 AVL 树来加快检索效率。散列表的实现除了一般的拉链法还有比如开放地址法等,感兴趣的可以深入研究。
哈希表(散列表)的优缺点总结如下,
优点:
哈希表的目的是让写入和查找时间复杂度都接近常量 O(1),所以小表做哈希性能非常好。
缺点:
要提前预判用来生成哈希表的基础表数据量,防止数据量过大,哈希表被撑大。
要找到合适的哈希函数,以防哈希表碰撞太频繁。
总结
哈希索引的实现就是建立在散列表的基础上,把索引字段当成 KEY,通过散列函数计算结果后,指向对应的行记录。认识哈希表对后期的 INNODB 自适应哈希索引以及对 HASH JOIN 的理解就会更加深刻。
关于 MySQL 的技术内容,你们还有什么想知道的吗?赶紧留言告诉小编吧!
相关推荐
- 腾讯开源框架TarsCpp-rpc设计分析-server(二)
-
2Tars协议2.1是什么借用官方说法:TARS编码协议是一种数据编解码规则,它将整形、枚举值、字符串、序列、字典、自定义结构体等数据类型按照一定的规则编码到二进制数据流中。对端接收到二进制数据流...
- 微服务调用为什么用RPC框架,http不更简单吗?
-
简单点,HTTP是协议,RPC是概念!实现RPC可以基于HTTP协议(Feign),TCP协议(Netty),RMI协议(Soap),WebService(XML—RPC)框架。传输过程中,也因为序列...
- go-zero:开箱即用的微服务框架(gin框架微服务)
-
go-zero是一个集成了各种工程实践的Web和rpc框架,它的弹性设计保障了大并发服务端的稳定性,并且已经经过了充分的实战检验。go-zero在设计时遵循了“工具大于约定和文档”的理...
- SOFARPC :高性能、高扩展性、生产级的 Java RPC 框架
-
#暑期创作大赛#SOFARPC是一个高性能、高扩展性、生产级的JavaRPC框架。在蚂蚁金服,SOFARPC已经使用了十多年,已经发展了五代。SOFARPC致力于简化应用程序之间的RPC...
- 自研分布式高性能RPC框架及服务注册中心ApiRegistry实践笔记
-
痛点1.bsf底层依赖springcloud,影响bsf更新springboot新版本和整体最新技术版本升级。2.eureka已经闭源,且框架设计较重,同时引入eureka会自行引入较多sprin...
- Rust语言从入门到精通系列 - Tonic RPC框架入门实战
-
Rust语言是一种系统级语言,被誉为“没有丧失性能的安全语言”。Rust语言的优势在于其内存安全机制,在编译时就能保证程序的内存安全。Tonic模块是Rust语言的一个RPC(RemoteProce...
- 腾讯开源框架TarsCpp-rpc设计分析-client(一)
-
前言Tars是腾讯开源的微服务平台,包含了一个高性能的rpc框架和服务治理平台,TarsCpp是其C++版本。对于以C++为主要开发语言,同时还想深入了解rpc和微服务框架具体实现的同学来说,Tars...
- 设计了一款TPS百万级别的分布式、高性能、可扩展的RPC框架
-
为啥要开发RPC框架事情是这样的,在开发这个RPC框架之前,我花费了不少时间算是对Dubbo框架彻底研究透彻了。冰河在撸透了Dubbo2.x和Dubbo3.x的源码之后,本来想给大家写一个Dubbo源...
- rpc框架使用教程,超级稳定好用,大厂都在使用
-
rpc是什么远程调用协议如何使用导入依赖<dependency><groupId>org.apache.dubbo</groupId><art...
- Layui 框架实战:动态加载 Select 与二级联动全解析
-
在现代Web开发中,下拉选择框(Select)是用户输入数据时不可或缺的组件。很多时候,我们需要的选项并非静态写死在HTML中,而是需要根据业务逻辑从后端动态获取。更有甚者,我们可能需要实现“...
- 15个能为你节省数百小时的前端设计神器,从UI库到文档生成
-
无论你是刚开始开发之旅的新手,还是疲于应付生产期限的资深程序员,有一个真理始终不变:正确的工具能彻底改变你的工作流程。多年来,我测试了数百个开发工具——有些实用,大多数平庸。但有一批免费网站经受住了时...
- Layui与WinForm通用权限管理系统全解析
-
嘿,小伙伴们,今天咱们来聊聊Layui和WinForm这两个框架在通用权限管理系统中的应用。别担心,我会尽量用简单易懂的语言来讲解,保证让大家都能跟上节奏!首先说说Layui。Layui是一个前端UI...
- 纯Python构建精美UI!MonsterUI让前端开发效率飙升
-
“无需CSS知识,告别类名记忆,11行代码实现专业级卡片组件”在传统Web开发中,构建美观界面需要同时掌握HTML、CSS、JavaScript三剑客,开发者不得不在多种语言间频繁切换。即使使用Boo...
- WebTUI:将终端用户界面(TUI)之美带到浏览器的CSS库
-
在当今Web技术飞速发展的时代,界面设计愈发复杂多样。然而,随着现代化工具的广泛使用,一些开发者开始回归极简风格,追求一种简洁而富有韵味的设计。WebTUI正是这样一款CSS库,它将经典的终...
- 人教版二年级下册生字描红汇总(拼音+笔顺+描红),可打印!
-
可定制内容,评论区留言。本次整理的为人教版二年级下册所有生字,共计300个;写字是小学阶段一项重要的基本功训练,把汉字写得正确、工整、美观,可以提高运用汉字这一交际工具的准确性和效率。对小学生进行写字...
你 发表评论:
欢迎- 一周热门
- 最近发表
-
- 腾讯开源框架TarsCpp-rpc设计分析-server(二)
- 微服务调用为什么用RPC框架,http不更简单吗?
- go-zero:开箱即用的微服务框架(gin框架微服务)
- SOFARPC :高性能、高扩展性、生产级的 Java RPC 框架
- 自研分布式高性能RPC框架及服务注册中心ApiRegistry实践笔记
- Rust语言从入门到精通系列 - Tonic RPC框架入门实战
- 腾讯开源框架TarsCpp-rpc设计分析-client(一)
- 设计了一款TPS百万级别的分布式、高性能、可扩展的RPC框架
- rpc框架使用教程,超级稳定好用,大厂都在使用
- Layui 框架实战:动态加载 Select 与二级联动全解析
- 标签列表
-
- 框架图 (58)
- flask框架 (53)
- quartz框架 (51)
- abp框架 (47)
- jpa框架 (47)
- springmvc框架 (49)
- 分布式事务框架 (65)
- scrapy框架 (56)
- shiro框架 (61)
- 定时任务框架 (56)
- java日志框架 (61)
- JAVA集合框架 (47)
- mfc框架 (52)
- abb框架断路器 (48)
- ui自动化框架 (47)
- beego框架 (52)
- java框架spring (58)
- grpc框架 (65)
- tornado框架 (48)
- 前端框架bootstrap (54)
- ppt框架 (48)
- 内联框架 (52)
- cad怎么画框架 (58)
- ssm框架实现登录注册 (49)
- oracle字符串长度 (48)