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 的模块化架构和设计意味着它可以以灵活且可扩展的方式支持多种功能。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144225.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

java生成PDF的Util

java使用itext生成pdf-CSDN博客 接上文 支持绘制表格 支持表格中的文本 字体加粗、字体上色、单元格背景上色, 支持拼接文本 支持单行文本 多种背景颜色、字体上色 支持自定义水印 废话不说先上效果图 工具类代码 package com.zxw.文件.PDF.util;import com.…

本地搭建kafka并用java实现发送消费消息

1、下载kafka的jar包文件 https://www.apache.org/dyn/closer.cgi?path/kafka/3.1.0/kafka_2.12-3.1.0.tgz2、下载完成直接操作命令启动 1、打开新的terminal(终端)窗口,进入kafka的bin目录 启动zk./zookeeper-server-start.sh ../config/zookeeper.properties2、…

LinkedList与链表

目录 一、Arraylist的缺陷 二、链表 2.1 链表的概念和结构 2.2 链表的实现 三、链表面试题 3.1 删除链表中所有值为val的节点 3.2 反转一个单链表 3.3 链表的中间节点 3.4 将有序链表合并 3.5 输出倒数第k个节点 3.6 链表分割 3.7 链表的回文结构 3.8 找两个链表的公共节…

现场直击|亚数TrustAsia精彩亮相IOTE深圳物联网展,CSA联盟展台等你来!

2023年9月20日,IOTE 2023第二十届深圳国际物联网展在深圳国际会展中心(宝安)顺利开幕。作为物联网领域年度最重要的行业盛会之一,本次展会汇聚全球来自工业、物流、基建、智慧城市、智慧零售等领域的600企业、10万行业人士&#x…

严重影响Windows使用体验的一些建议

1内存不够用:通过观察我发现我的电脑已经评价到了90%的内存使用率 没有内存什么程序运行起来都会卡的,所以一定要把不用的PROGRAME给他删除掉。特别是那些自动启动的软件,如果实在不行,就把杀毒也给他卸载掉。 不良具体表现&…

Java基础面试题精选:深入探讨哈希表、链表和接口等

目录 1.ArrayList和LinkedList有什么区别?🔒 2.ArrayList和Vector有什么区别?🔒 3.抽象类和普通类有什么区别?🔒 4.抽象类和接口有什么区别?🔒 5.HashMap和Hashtable有什么区别&…

Ubuntu为什么键盘会出现乱字符

今天上午起来只是要简单打一个命令,需要输入一个"双引号,但是总是显示,我一开始以为是中了病毒,把键盘给改了,后来发现虚惊一场:出现这个原因是因为ubuntu的键盘设置有问题。 我把键盘设置为英国英语…

【C++进阶(六)】STL大法--栈和队列深度剖析优先级队列适配器原理

💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C   🔝🔝 栈和队列 1. 前言2. 栈和队列的接口函数熟悉3. …

欧伟杰博士:突破算力边界,YashanDB实现理论与工程双重突围

作者介绍 *全文4767个字,阅读时长约12分钟。 背景 随着数字化进程的加速,数据处理的规模和速度需求持续攀升。传统数据库系统在处理大规模数据时,存在单表记录数不超过500万条的限制,这已成为业务发展的瓶颈。为了解决此问题&…

No146.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

MySQL5.7高级函数:JSON_ARRAYAGG和JSON_OBJECT的使用

前置准备 DROP TABLE IF EXISTS t_user; CREATE TABLE t_user (id bigint(20) NOT NULL,name varchar(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci …

杀掉进程但是fastapi程序还在运行

两个脚本,一个运行fastapi服务,一个重启服务: 启动服务先: 发现问题,杀掉 server.sh 后,依旧有: 不知道为什么会出现这个,直接kill吧: server.sh: #!/bin/bashparpath/…

led灯什么牌子的质量好?Led护眼台灯排行榜

现在我们很多家长对自己孩子的视力十分关心,生怕自己的孩子是近视、远视、弱视等等。对于父母而言,在孩子读书压力大课业重的关键时期,为孩子选择合适的桌椅,保护灯具从而保护孩子的眼睛是非常重要的事情!那么买给孩子读书做功课的…

Matlab绘图函数subplot、tiledlayout、plot和scatter

一、绘图函数subplot subplot(m,n,p)将当前图窗划分为 mn 网格,并在 p 指定的位置创建坐标区。MATLAB按行号对子图位置进行编号。第一个子图是第一行的第一列,第二个子图是第一行的第二列,依此类推。如果指定的位置已存在坐标区,…

基于Java的音乐网站管理系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&…

前端uniapp防止页面整体滑动页面顶部以上,设置固定想要固定区域宽高

解决:设置固定想要固定区域宽高 目录 未改前图未改样式改后图改后样式 未改前图 未改样式 .main {display: flex;flex-direction: row;// justify-content: space-between;width: 100vw;// 防止全部移动到上面位置!!!&#xff01…

No147.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

【在Ubuntu部署Docker项目】— PROJECT#1

一、说明 让我们深入了解 Docker。用docker构建web服务器。我们正在计划开发JavaScript API,建立MySQL数据库,并创建一个 PHP 网站使用 API 服务。Php Node.js Mysql — DockerSeries — Episode#1 二、系统架构概述 我们要构建的容器,是三…

Qt_C++读写NFC标签Ntag支持windows国产linux操作系统

本示例使用的发卡器&#xff1a;Android Linux RFID读写器NFC发卡器WEB可编程NDEF文本/智能海报/-淘宝网 (taobao.com) ntag2标签存储结构说明 #include "mainwindow.h" #include "./ui_mainwindow.h" #include <QDebug> #include "QLibrary&…

队列的使用以及模拟实现(C++版本)

&#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;强烈推荐优质专栏: &#x1f354;&#x1f35f;&#x1f32f;C的世界(持续更新中) &#x1f43b;推荐专栏1: &#x1f354;&#x1f35f;&#x1f32f;C语言初阶 &#x1f43b;推荐专栏2: &#x1f354;…