基于排序的两趟算法

​专栏内容：

  • 手写数据库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
如有错误或者疏漏欢迎指出，互相学习。