广西壮族自治区住房和城乡建设厅网站,wordpress 律师事务所模板,网站备案信息被删除,专业做淘宝网站推广基于散列的两趟算法 专栏内容#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发#xff0c;开发的步骤#xff0c;以及开发过程中的涉及的原理#xff0c;遇到的问题等#xff0c;让大家能跟上并且可以一起开发#xff0c;让每个需要的人成为参与者。 本专栏会定…基于散列的两趟算法 专栏内容 手写数据库toadb 本专栏主要介绍如何从零开发开发的步骤以及开发过程中的涉及的原理遇到的问题等让大家能跟上并且可以一起开发让每个需要的人成为参与者。 本专栏会定期更新对应的代码也会定期更新每个阶段的代码会打上tag方便阶段学习。 开源贡献 toadb开源库 个人主页我的主页 管理社区开源数据库 座右铭天行健君子以自强不息地势坤君子以厚德载物. 文章目录 基于散列的两趟算法前言概述原理流程基于散列的去重基于散列的分组聚集基于散列的并、交和差基于散列的连接代价分析总结结尾 前言
随着信息技术的飞速发展数据已经渗透到各个领域成为现代社会最重要的资产之一。在这个大数据时代数据库理论在数据管理、存储和处理中发挥着至关重要的作用。然而很多读者可能对数据库理论感到困惑不知道如何选择合适的数据库如何设计有效的数据库结构以及如何处理和管理大量的数据。因此本专栏旨在为读者提供一套全面、深入的数据库理论指南帮助他们更好地理解和应用数据库技术。
数据库理论是研究如何有效地管理、存储和检索数据的学科。在现代信息化社会中数据量呈指数级增长如何高效地处理和管理这些数据成为一个重要的问题。同时随着云计算、物联网、大数据等新兴技术的不断发展数据库理论的重要性日益凸显。
概述
前面两篇博客分享了基于排序的两趟算法那么还有其它类型的两趟算法吗
答案是肯定的当然有。
本文就来分享一种基于散列的两趟算法。
原理
如果数据量太大以至于不能一次装入内存缓冲区中基于散列的两趟算法中采用一个合适的hash算法将表划分为M-1个hash桶这样操作对象一样的元组就在相同的桶中然后就可以依次处理各桶中的数据。
实际上经过hash处理之后我们将操作对象的大小减小了减小的比例等于桶的数目它的数量大致为可用缓冲区大小M。这与我们介绍的基于排序的两趟算法有点类似有同样的因子但是两种方法执行的过程完全不同。
流程
第一趟hash散列处理
假设hash函数为h并且h将表R的整个元组作为参数同时将每个一个hash桶与一个缓冲区块联系起来。每次加载表R的一个数据块将块中的元组按hash函数h进行处理输出到桶对应的缓冲区中如查某个桶对应的缓冲区满了将它写到磁盘上重复以上步骤直到表R处理完成最后一个桶的缓冲区也写到磁盘上
第二趟处理就需要结合具体的某个操作我们之前介绍过去重分组聚集并集差集交集连接等
基于散列的去重
在第一趟hash散列结束后对于hash相同的元组都在一个桶中那么相同的元组也在一个桶中我们每次处理一个桶。
读取第一个桶的数据块到缓冲区中将第一条元组输出到结果缓冲区中对于它的副本忽略依次处理下一个桶中的数据块 直到所有桶中的数据块处理完成
基于散列的分组聚集
执行分组操作的话在第一趟将表R的数据hash成M个桶的进候hash的键值要使用分组属性列这样相同分组属性的元组会被分配到相同的桶中。
在第二趟时依次加载每个桶的数据块计算分组数据如行数求和等每个桶为一个分组直到所有桶处理完毕。
最后计算分组结果输出结果。
基于散列的并、交和差
第一趟将表R和表S分别采用相同的hash函数h分别hash到数量相等的桶中那么桶的数量为2M
第二趟时对于不同操作 对于集合的并因为相同的元组分配在相同的桶中比如表R的每i个桶记为Ri,而表S的第i个桶记为Si那么取Ri和Si执行并集操作对于两个中都出现的元组重复元组只输出一次到结果缓冲区块上这样依次对应取两个桶直到所有桶处理完毕。 对于包的并也是对应的取Ri和Si两个桶的数据块将两个桶中的数据输出到结果缓冲区中其实一趟算法就足够了 对于集合交也是对应的取Ri和Si两个桶的数据块对于两个桶中都出现的元组输出到结果缓冲区中 对于包的交加载对应的取Ri和Si两个桶的数据块对于出现次数相同的元组输出到结果缓冲区中
基于散列的连接
假设表R(X,Y)与表S(Y,Z)进行等值连接
第一趟将表R和表S分别采用相同的hash函数h分别hash到数量相等的桶中那么桶的数量为2M而hash键值采用两表的连接属性列这样对于属性列Y相同的元组都在Ri与Si桶中。
第二趟时对于对应的Ri与Si桶加载到内存中采用一趟散连连接算法就可以完成。
代价分析
将表R在第一趟hash成M个桶时会读取表R的所有数据块B然后将各个桶对应的数据块写到磁盘上写磁盘的数据块也近似为B
在第二趟中会将各桶的数据块读出数据块数为B如果不计结果的写入。
那么在整个基于散列的两趟算法中磁盘IO的数量为表R的数据块的数量的3倍。
总结
对于大表来讲不能一次性加载到内存那么我们可以采用基于散列的两趟操作实现一元操作去重分组和聚集二元操作并差交连接等。
以下是使用访问者模式编写输出Hello World的C语言代码
#include stdio.h// 定义抽象数据类型
typedef struct {void (*accept)(void *data, void (*print)(void *data));
} Visitor;// 定义具体数据类型
typedef struct {char message[100];
} Data;// 定义访问者函数
void printVisitor(void *data) {Data *myData (Data *)data;printf(%s\n, myData-message);
}// 定义具体数据类型的构造函数和访问者函数调用
Visitor visitor { .accept printVisitor };
Data data { .message Hello World };
data.accept(visitor, printVisitor);在上述代码中我们定义了一个抽象数据类型Visitor其中包含一个accept方法用于接受具体数据类型的实例并调用其访问者方法。接着我们定义了一个具体数据类型Data其中包含一个字符串消息。然后我们定义了一个访问者函数printVisitor用于输出具体数据类型的字符串消息。最后我们定义了一个具体数据类型的构造函数和访问者函数调用创建了一个Data实例并使用accept方法将其传递给访问者对象并调用访问者函数输出字符串消息。
结尾 非常感谢大家的支持在浏览的同时别忘了留下您宝贵的评论如果觉得值得鼓励请点赞收藏我会更加努力 作者邮箱studysenllang.onaliyun.com 如有错误或者疏漏欢迎指出互相学习。
