视频推广计划,百度竞价seo排名,上海公司沪牌价格,网页游戏网页打不开基于两趟排序的其它操作 专栏内容#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发#xff0c;开发的步骤#xff0c;以及开发过程中的涉及的原理#xff0c;遇到的问题等#xff0c;让大家能跟上并且可以一起开发#xff0c;让每个需要的人成为参与者。 本专栏…基于两趟排序的其它操作 专栏内容 手写数据库toadb 本专栏主要介绍如何从零开发开发的步骤以及开发过程中的涉及的原理遇到的问题等让大家能跟上并且可以一起开发让每个需要的人成为参与者。 本专栏会定期更新对应的代码也会定期更新每个阶段的代码会打上tag方便阶段学习。 开源贡献 toadb开源库 个人主页我的主页 管理社区开源数据库 座右铭天行健君子以自强不息地势坤君子以厚德载物. 文章目录 基于两趟排序的其它操作前言概述利用排序去重利用排序进行分组和聚集基于排序的并算法基于排序的交和差算法基于排序的连接算法总结结尾 前言
随着信息技术的飞速发展数据已经渗透到各个领域成为现代社会最重要的资产之一。在这个大数据时代数据库理论在数据管理、存储和处理中发挥着至关重要的作用。然而很多读者可能对数据库理论感到困惑不知道如何选择合适的数据库如何设计有效的数据库结构以及如何处理和管理大量的数据。因此本专栏旨在为读者提供一套全面、深入的数据库理论指南帮助他们更好地理解和应用数据库技术。
数据库理论是研究如何有效地管理、存储和检索数据的学科。在现代信息化社会中数据量呈指数级增长如何高效地处理和管理这些数据成为一个重要的问题。同时随着云计算、物联网、大数据等新兴技术的不断发展数据库理论的重要性日益凸显。
概述
在前一篇博客中与大家一起了解了两趟算法的排序那么这个算法在那些地方可以应用呢
基于两趟排序算法是可以简化很多操作比如去重分组聚集并集交集差集以及连接下面我们一起来看看。
利用排序去重
在两趟算法中第一趟是将表分成M-1个子表分别进行排序然后将子表排序的结果写入磁盘。
在第二趟时采用多路归并排序的方法要实现基于排序的去重这里有就一些区别。
加载M-1个子表的第一个数据块到缓冲区中找到最小的元组将它移动到第M个缓冲区中如果有当前最小元组相同的元组忽略它重复23步骤如果第M个缓冲区满将它写到磁盘并清空如果有子表的数据块空时加载该子表的下一个数据块重复以上步骤直到所有子表处理完成
这样时间空间复杂度与代价并没有增加就可以实现去重的操作只是增加了第3步让重复元组不输出到结果中。
利用排序进行分组和聚集
利用排序实现分组和聚集的计算在第一趟子表的排序时需要用分组属性列作为排序键然后进行各子表的排序并将各子表排序结果写入磁盘中
在第二趟时同样采用多路归并排序的步骤具体如下
加载M-1个子表的第一个数据块到缓冲区中找到最小排序关键字对应的元组它作为当前的分组不断从子表中找到相同排序关键字对应的分组计算分组的聚集值如统计元组数统计聚集列的和等如果有子表的数据块空时加载该子表的下一个数据块重复以上步骤直到所有子表处理完成最后计算聚集值如求平均那么就是分组总和/分组的总行数
这样就计算出了算有分组和聚集值聚集统计时需要一直在内存中如果去除结果数据写磁盘的代价它与之前算法是一致的3倍的表数据块的IO数量。
基于排序的并算法
并的操作如前所述区分包的并和集合的并。
对于包的并一趟算法的介绍中与操作对象的大小是无关的所以用一趟算法即可。
而集合的并至少需要一个表小于可用内存才可以用一趟算法所以大多数时候更适合两趟算法。
假设表R与表S进行并集操作具体流程如下 在第一趟时同上一个算法一样分别创建表R和表S的子表的排序并将各子表排序结果写入磁盘中 在第二趟时将表R和表S的子表的第一个数据块加载到缓冲区中 找到最小的元组将它移动到结果缓冲区中将与它相同的元组从缓冲区中删除重复12步骤如果结果缓冲区满将它写到磁盘并清空如果有子表的数据块空时加载该子表的下一个数据块重复以上步骤直到所有子表处理完成 这样表R和表S就会完成并集操作在这个过程中每个有副本的元组相同元组会有3次IO产生整体代价与前面算法一致。
基于排序的交和差算法
计算交和差时也要区分包的操作还是集合的操作但是对于基于排序的交和差两者的步骤同上一算法一致只是在计算副本时有些差异。
对于集合的交计算时如果元组在表R和表S的子表中都出现时才输出到结果缓冲区中否则忽略对于包的交计算时元组在表R和表S的子表中出现的最小值就是元组输出到结果缓冲区中的次数当一方为计数减为0时忽略当前元组对于集合差仅当元组在表R中出现在表S中不出现时才会输出到结果缓冲区中对于包的差输出元组的次数是在表R中出现次数减去表S中的出现次数
这里需要特别注意对于包的操作时元组的副本不仅当前块中出现而且当副本为当前块最后一条元组时那么下一数据块上还有该元组的副本所以要统计到下一条元组改为为止
基于排序的连接算法
对于连接操作本身有会有很多实现算法如果操作的前提是排序的两张表那么如何来实现连接算法呢 下面我们一起来看下基于排序的两趟算法的连接的实现流程
假设表R(X,Y)与表S(Y,Z)进行连接操作连接属性为Y
在第一趟时将表R和表S分别按照连接属性列进行排序将排好序的子表都写入磁盘
在第二趟时表R和表S分别加载各子表的第一个数据块到缓冲区中
在子表中找到最小排序关键字对应的元组如果在另一个表中没有出现则移除该元组如果两个表都存在将它移动到输出缓冲区中按排序继续查找输出所有键值相同的元组如果结果缓冲区满将它写到磁盘并清空如果有子表的数据块空时加载该子表的下一个数据块重复以上步骤直到子表处理完成
如果当表R的子表先处理完那么表S的子表就不再需要处理相反也是一样。
总结
基于排序的去重并交差连接算法的代价磁盘IO的次数基本为3倍的表的块数量再加一倍的结果写入数量
以下是使用工厂模式编写输出Hello World的C语言代码
#include stdio.h// 声明抽象工厂接口
typedef struct {void (*print)(void);
} Factory;// 实现输出Hello World的工厂方法
void printHelloWorld(void) {printf(Hello World\n);
}// 实现抽象工厂方法返回输出Hello World的工厂对象
Factory* createHelloWorldFactory(void) {Factory* factory malloc(sizeof(Factory));factory-print printHelloWorld;return factory;
}// 使用工厂对象输出Hello World
int main(void) {Factory* factory createHelloWorldFactory();factory-print();free(factory); // 释放工厂对象内存return 0;
}在上述代码中我们定义了一个抽象工厂接口Factory其中包含一个print方法用于输出字符串。然后我们实现了一个工厂方法printHelloWorld用于输出Hello World字符串。接着我们实现了一个抽象工厂方法createHelloWorldFactory用于返回输出Hello World的工厂对象。最后在main函数中我们使用工厂对象调用print方法输出Hello World字符串。
结尾 非常感谢大家的支持在浏览的同时别忘了留下您宝贵的评论如果觉得值得鼓励请点赞收藏我会更加努力 作者邮箱studysenllang.onaliyun.com 如有错误或者疏漏欢迎指出互相学习。
