自己公司内网网站和外网怎么做同步,做网站推广的公司,苏州网站的优化,怎么看一个网站做没做优化基于排序的两趟算法 专栏内容#xff1a; 手写数据库toadb 本专栏主要介绍如何从零开发#xff0c;开发的步骤#xff0c;以及开发过程中的涉及的原理#xff0c;遇到的问题等#xff0c;让大家能跟上并且可以一起开发#xff0c;让每个需要的人成为参与者。 本专栏会定…基于排序的两趟算法 专栏内容 手写数据库toadb 本专栏主要介绍如何从零开发开发的步骤以及开发过程中的涉及的原理遇到的问题等让大家能跟上并且可以一起开发让每个需要的人成为参与者。 本专栏会定期更新对应的代码也会定期更新每个阶段的代码会打上tag方便阶段学习。 开源贡献 toadb开源库 个人主页我的主页 管理社区开源数据库 座右铭天行健君子以自强不息地势坤君子以厚德载物. 文章目录 基于排序的两趟算法前言概述基于排序的两趟算法原理算法流程算法限制算法代价估算 总结结尾 前言
随着信息技术的飞速发展数据已经渗透到各个领域成为现代社会最重要的资产之一。在这个大数据时代数据库理论在数据管理、存储和处理中发挥着至关重要的作用。然而很多读者可能对数据库理论感到困惑不知道如何选择合适的数据库如何设计有效的数据库结构以及如何处理和管理大量的数据。因此本专栏旨在为读者提供一套全面、深入的数据库理论指南帮助他们更好地理解和应用数据库技术。
数据库理论是研究如何有效地管理、存储和检索数据的学科。在现代信息化社会中数据量呈指数级增长如何高效地处理和管理这些数据成为一个重要的问题。同时随着云计算、物联网、大数据等新兴技术的不断发展数据库理论的重要性日益凸显。
概述
前面几篇博客分享了一趟算法但是对于较大的表或较大结果集时一趟算法的限制比较明显。本文重点分享两趟算法为什么是两趟算法呢
首先它对于大多数情况下的表大小基本足够了基次在两趟算法的基础上扩展到多趟算法也是很方便下面我们就以排序为例进行两趟算法的原理介绍同时在基于排序的两趟算法基础上也可以实现去重分组聚集并集交差连接等操作的算法。
基于排序的两趟算法原理
对于表的数据块的数量B®大于可用缓冲区块的数量M时,我们就用到了两阶段的多路归并排序算法这是一种外排算法。
这里同时会用到内排算法和外排算法对于数据在内存中的排序叫做内排算法比如数据结构课本上的冒泡排序选择排序等不需要和磁盘进行交互。 而对于要排序的数据量非常大时内存中都容纳不下时就要采用外排算法一部分数据暂进放到磁盘上用时再加载进来。
算法流程
这里用到的算法叫做两阶段多路归并排序算法它有两个阶段组成可以对非常大的表进行排序操作。它的原理介绍如下 首先假设我们有M个缓冲区块表的数据块为B而且是大于M我们将表的数据块分成M-1组每组的数据块就是B/(M-1) 为什么是M-1组呢先别急后面步骤会解答
阶段1 不断的将表的数据块加载到M个缓冲区块中利用内排算法进行排序并将排好序的子表结果写到磁盘上阶段2将排好序的子表进行归并排序。先将M-1个子表的第一个数据块加载到M-1个缓冲区块上第M个缓冲区块用于结果的输出。这里就限制了子表的数量只能有M-1个子表因为需要有一个缓冲区块记录最终排序的结果。第M个缓冲区块放满时就将它写入磁盘再清空重复利用。
阶段二的主要步骤是这样的
找到所有子表中最小的元组因为比较是在内存中完成所以搜索的执行时间与子表的数量成线性关系。将最小的元组移到结果集缓中区块的第一个可用位置重复执行上面两步骤如果结果集缓冲区块满则将它输出到磁盘并清空后重复利用如果刚取出最小元组的子表当前数据块已经空了那么加载该子表的下一个数据块重复上面的步骤直到所有子表都处理完成
算法限制
为了使两阶段多路归并排序算法能够在两趟内完成每个子表的数据块要最大为M这样第一阶段就可以在内存中完成
而第二阶段要求子表的数量不大于M-1每个子表的数据块为B/(M-1)
那么表的数据块总量不等式的运算得到 B M(M-1)也就是近似于表的块数B要小于可用缓冲区数量的平方。
这就是两趟算法的限制不过它已经可以满足大多数情况了。
算法代价估算
在两阶段多路归并排序算法执行过程中第一阶段读写IO次数为表的总数据块数量两倍 在第二阶段中需要将所有子表再读一次然后结果集再写一遍也是表的数据块数量的两倍
所以两趟算法中磁盘IO的代价是 4B也就是表数据块数量的4倍。
总结
两趟算法被广泛使用通过对排序应用两趟算法的机制的分享将它的执行流程以及存在的限制讲解清楚同时在代价估算时有一定衡量标准有利于优化器的设计。
最后分享一段helloworld的代码
在C语言中实现单例模式通常是为了确保一个类只有一个实例并提供一个全局访问点。然而C语言没有内置的类或对象的概念因此我们将使用结构体和函数来模拟单例模式。
下面是一个使用单例模式的 “Hello World” 程序
#include stdio.h
#include stdlib.htypedef struct Singleton {void (*printHello)(void);
} Singleton;void printHello(void) {printf(Hello, World!\n);
}Singleton* getInstance(void) {static Singleton instance { .printHello printHello };return instance;
}int main(void) {Singleton* singleton getInstance();singleton-printHello();return 0;
}在这个程序中我们定义了一个 Singleton 结构体它包含一个 printHello 函数指针。printHello 函数用于输出 “Hello, World!”。getInstance 函数返回 Singleton 实例的指针。我们使用 static 关键字来确保 instance 只在程序运行期间被创建一次。最后在 main 函数中我们通过调用 getInstance 函数获取单例并调用 printHello 函数输出 “Hello, World!”。
结尾 非常感谢大家的支持在浏览的同时别忘了留下您宝贵的评论如果觉得值得鼓励请点赞收藏我会更加努力 作者邮箱studysenllang.onaliyun.com 如有错误或者疏漏欢迎指出互相学习。
