基于排序的两趟算法

专栏内容

  • 手写数据库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 #include typedef 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!”。

结尾

非常感谢大家的支持,在浏览的同时别忘了留下您宝贵的评论,如果觉得值得鼓励,请点赞,收藏,我会更加努力!

作者邮箱:study@senllang.onaliyun.com
如有错误或者疏漏欢迎指出,互相学习。