Hash Index 原理和应用精讲
线上沙龙 - 技术流第 35 期回放来啦
本期直播我们邀请到 KaiwuDB 高级研发工程师徐胜康,为大家分享 Hash Index 原理和应用。徐老师曾任职于 Sun Micro Systems, Lucent 等公司,具备多年 Linux/UNIX Operating System 内核、驱动、文件系统、数据库、研发工作与技术管理经验,对分布式系统、性能优化、数据加密等领域有着深入的研究。
索引数据结构是计算机科学里非常重要的,也是编程中最常使用、最有效的一种数据结构。索引结构有很多不同类型。本期直播详细对比了比较常见的多种索引结构,并着重深入讲解了哈希索引。欢迎点击链接观看本次直播回放↓↓↓
【Hash Index 原理和应用精讲-哔哩哔哩】 https://b23.tv/73yXO3b
直播重点回顾
01 背景介绍
1. 追加数据操作
存储设备有很多类型,例如,电脑文件系统、块设备、云存储、日志存储设备等,数据库和数据表也是一种存储方式。但不论何种存储形式,追加数据操作是最常用也是最有效的存储新数据的方式。
2. 追加操作的问题
尽管追加数据是插入新数据的有效方式,但会导致数据在存储设备中处于无序的状态,进而使得在无序存储中搜索某些特定数据浪费大量时间。
3. 索引资料结构是解决方案
使用索引数据结构能帮助解决如上问题,实现在无序的存储机制中快速查找数据记录。
02常用索引类型
有多种常见的索引数据结构。不同类型的索引结构以不同的方式工作,具有不同的特性。
-
列表类型的索引结构,如简单列表和跳过列表;
-
多级索引结构,如 B 树和 B+ 树;
-
学习索引是一种新的索引技术,但还没有流行;
-
哈希索引是一种常用的索引结构,也是最基本的索引结构之一。
不同类型索引结构对比:
每个索引结构都有优点、缺点和适用情况,不存在全能的索引结构。
03哈希索引
1. 原始哈希索引
哈希索引最简单的形式是有序数组,它是按键排序的数组,这种方法并不实用,因为索引键可能不是整数;然而,如果可以把索引键转换为整数,它的范围可能会很大,有效条目可能不多,从而导致记忆体利用率变低。
2. 基本哈希索引
基本哈希索引使用哈希函数将键转换为整数,哈希值用于索引桶数组,所有具有相同杂凑(键)值的资料记录将进入相同的杂凑桶。
3. 哈希索引搜索步骤
4. 哈希桶内的记录搜索
哈希桶内的资料记录未排序或组织。因此,定位到哈希桶后,在桶内进行搜寻也面临同样的问题,但规模会相对较小。
5. 改良的哈希桶设计
基于考虑 CPU 快取行和 SIMD(单指令多资料)而设计的桶格式有效地改善了桶内的搜寻。
-
一种新的利用 CPU 缓存行感知和 SIMD 指令的存储桶格式设计;
-
Bucket 结构必须与 CPU 缓存行对齐;
-
第一个缓存行包含:32-bit 有效位图、一个 8 字节溢出指针、32 字节签名;
-
随后的四个高速缓存行保存 32 个 TID。每个 TID 8 字节。
6. 改良型哈希桶搜索步骤
在大多数情况下,在桶中搜寻一条记录只需要三个步骤和三次 CPU 快取未命中。
-
哈希函数生成 BucketID 和 8-bit 签名码;
-
SIMD 比较 8-bit 签名与 32 个签,并输出 32-bit 匹配位图。32-bit 匹配位图 AND 32-bit 有效位图生成一个 32-bit 目标位图;
-
根据目标位图找到 TID。
04哈希索引在 KaiwuDB 中的运用
1. SQL 语法
KaiwuDB 支持多种索引类型,包括哈希索引。KaiwuDB 在哈希连接操作中也使用了哈希索引。
2. KaiwuDB 是一个高效能数据库
KaiwuDB 从一开始就内建了高性能,KaiwuDB 从架构到设计,再到编码实践都遵循最高标准和最佳实践。
-
KaiwuDB 是一个高性能、多功能、高集成的多模块数据库;
-
高性能哈希索引是 KaiwuDB 高性能产品的一部分,它主要用于表索引和散列连接;
-
KaiwuDB 还支持其他类型的索引,例如 B-tree。
3. KaiwuDB 是一个多功能数据库
KaiwuDB 的模块化架构和设计意味着它可以以灵活且可扩展的方式支持多种功能。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
全面解读 SQL 优化 - 统计信息
一、简介 数据库中的优化器(optimizer)是一个重要的组件,用于分析 SQL 查询语句,并生成执行计划。在生成执行计划时,优化器需要依赖数据库中的统计信息来估算查询的成本,从而选择最优的执行计划。以下是关于数据库中优化器统计信息的简介: (1)统计信息概述 统计信息是描述表或索引中数据分布情况的元数据。这些信息包括行数、数据分布、重复值等,都是优化器选择执行计划的关键因素。 (2)统计信息来源 统计信息被收集并存储在数据字典中,可以通过特定的 SQL 命令(如 ANALYZE TABLE)来手动收集;也可以被自动收集,以保持数据字典的最新状态。 (3)统计信息类型 统计信息包括两种不同类型的信息,系统级别和对象级别。系统级别的统计信息是全局性的,如整个数据库中所有表的平均行长度;而对象级别的统计信息是特定对象的信息,如表或索引的平均行长度、列值的分布和直方图等。 (4)统计信息用途 优化器使用统计信息作为计算成本的基础,从而选择最优执行计划。优化器所使用的统计信息包括表的行数、每个列的唯一值数目、平均列长度等。 (5)统计信息更新 数据的分布会随着时间和数据量的增长而发生变化,因...
- 下一篇
低代码平台如何借助Nginx实现网关服务
摘要:本文由葡萄城技术团队于OSCHINA原创并首发。转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具、解决方案和服务,赋能开发者。 前言 在典型的系统部署架构中,应用服务器是一种软件或硬件系统,它承载着应用程序的核心逻辑。它接收客户端的请求并处理相应的业务逻辑、数据操作等任务。应用服务器通常被用于支持 Web 应用程序、移动应用程序和企业应用程序等。在应用服务器之上通常是网关服务器,在其下方是数据库服务。有趣的是,在低代码平台中,同样也存在应用服务器,今天小编将以葡萄城公司的企业级低代码开发平台——活字格为例给大家介绍网关服务器对于低代码平台的辅助作用。 使用Nginx实现的应用场景 在本文中,将以网关服务器Nginx为例,展示网关服务的四个场景: 跨域访问:让多个应用共享同一个服务器的端口。 静态资源:通过微信公众平台等验证。 IP黑白名单:满足更高的安全防护要求。 访问日志:详细记录并分析系统响应能力。 1.跨域访问:让多个应用共享同一个服务器的同一个端口 将同一个系统的多个模块拆分成若干个应用,不论是开发管理还是系统运维都是很值得推荐的实践模式。但如果一个应用的前端...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS关闭SELinux安全模块
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- 设置Eclipse缩进为4个空格,增强代码规范