基于排序的兩趟算法

?專欄內(nèi)容：

• 手寫數(shù)據(jù)庫toadb
  本專欄主要介紹如何從零開發(fā)，開發(fā)的步驟，以及開發(fā)過程中的涉及的原理，遇到的問題等，讓大家能跟上并且可以一起開發(fā)，讓每個需要的人成為參與者。
  本專欄會定期更新，對應(yīng)的代碼也會定期更新，每個階段的代碼會打上tag，方便階段學(xué)習(xí)。

?開源貢獻：

• toadb開源庫

個人主頁：我的主頁
管理社區(qū)：開源數(shù)據(jù)庫
座右銘：天行健，君子以自強不息；地勢坤，君子以厚德載物.

前言

隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)已經(jīng)滲透到各個領(lǐng)域，成為現(xiàn)代社會最重要的資產(chǎn)之一。在這個大數(shù)據(jù)時代，數(shù)據(jù)庫理論在數(shù)據(jù)管理、存儲和處理中發(fā)揮著至關(guān)重要的作用。然而，很多讀者可能對數(shù)據(jù)庫理論感到困惑，不知道如何選擇合適的數(shù)據(jù)庫，如何設(shè)計有效的數(shù)據(jù)庫結(jié)構(gòu)，以及如何處理和管理大量的數(shù)據(jù)。因此，本專欄旨在為讀者提供一套全面、深入的數(shù)據(jù)庫理論指南，幫助他們更好地理解和應(yīng)用數(shù)據(jù)庫技術(shù)。

數(shù)據(jù)庫理論是研究如何有效地管理、存儲和檢索數(shù)據(jù)的學(xué)科。在現(xiàn)代信息化社會中，數(shù)據(jù)量呈指數(shù)級增長，如何高效地處理和管理這些數(shù)據(jù)成為一個重要的問題。同時，隨著云計算、物聯(lián)網(wǎng)、大數(shù)據(jù)等新興技術(shù)的不斷發(fā)展，數(shù)據(jù)庫理論的重要性日益凸顯。

概述

前面幾篇博客分享了一趟算法，但是對于較大的表或較大結(jié)果集時，一趟算法的限制比較明顯。本文重點分享兩趟算法，為什么是兩趟算法呢？

首先它對于大多數(shù)情況下的表大小基本足夠了；基次，在兩趟算法的基礎(chǔ)上擴展到多趟算法，也是很方便；下面我們就以排序為例，進行兩趟算法的原理介紹，同時在基于排序的兩趟算法基礎(chǔ)上，也可以實現(xiàn)去重，分組聚集，并集，交，差，連接等操作的算法。

基于排序的兩趟算法原理

對于表的數(shù)據(jù)塊的數(shù)量B?大于可用緩沖區(qū)塊的數(shù)量M時,我們就用到了兩階段的多路歸并排序算法，這是一種外排算法。

這里同時會用到內(nèi)排算法和外排算法，對于數(shù)據(jù)在內(nèi)存中的排序，叫做內(nèi)排算法，比如數(shù)據(jù)結(jié)構(gòu)課本上的冒泡排序，選擇排序等，不需要和磁盤進行交互。 而對于要排序的數(shù)據(jù)量非常大時，內(nèi)存中都容納不下時，就要采用外排算法，一部分數(shù)據(jù)暫進放到磁盤上，用時再加載進來。

算法流程

這里用到的算法叫做兩階段多路歸并排序算法，它有兩個階段組成，可以對非常大的表進行排序操作。它的原理介紹如下：
首先假設(shè)我們有M個緩沖區(qū)塊，表的數(shù)據(jù)塊為B，而且是大于M；我們將表的數(shù)據(jù)塊分成M-1組，每組的數(shù)據(jù)塊就是B/(M-1)；
為什么是M-1組呢，先別急，后面步驟會解答；

• 階段1， 不斷的將表的數(shù)據(jù)塊加載到M個緩沖區(qū)塊中，利用內(nèi)排算法進行排序，并將排好序的子表結(jié)果寫到磁盤上；
• 階段2，將排好序的子表進行歸并排序。先將M-1個子表的第一個數(shù)據(jù)塊加載到M-1個緩沖區(qū)塊上，第M個緩沖區(qū)塊用于結(jié)果的輸出。這里就限制了子表的數(shù)量，只能有M-1個子表，因為需要有一個緩沖區(qū)塊記錄最終排序的結(jié)果。第M個緩沖區(qū)塊放滿時，就將它寫入磁盤，再清空，重復(fù)利用。

階段二的主要步驟是這樣的：

• 找到所有子表中最小的元組；因為比較是在內(nèi)存中完成，所以搜索的執(zhí)行時間與子表的數(shù)量成線性關(guān)系。
• 將最小的元組移到結(jié)果集緩中區(qū)塊的第一個可用位置；
• 重復(fù)執(zhí)行上面兩步驟；如果結(jié)果集緩沖區(qū)塊滿，則將它輸出到磁盤，并清空后，重復(fù)利用；
• 如果剛?cè)〕鲎钚≡M的子表，當(dāng)前數(shù)據(jù)塊已經(jīng)空了，那么加載該子表的下一個數(shù)據(jù)塊；
• 重復(fù)上面的步驟，直到所有子表都處理完成；

算法限制

為了使兩階段多路歸并排序算法，能夠在兩趟內(nèi)完成，每個子表的數(shù)據(jù)塊要最大為M，這樣第一階段就可以在內(nèi)存中完成；

而第二階段，要求子表的數(shù)量不大于M-1，每個子表的數(shù)據(jù)塊為B/(M-1)；

那么表的數(shù)據(jù)塊總量不等式的運算得到 B <= M(M-1)，也就是近似于表的塊數(shù)B要小于可用緩沖區(qū)數(shù)量的平方。

這就是兩趟算法的限制，不過它已經(jīng)可以滿足大多數(shù)情況了。

算法代價估算

在兩階段多路歸并排序算法執(zhí)行過程中，第一階段讀寫IO次數(shù)為表的總數(shù)據(jù)塊數(shù)量兩倍；
在第二階段中，需要將所有子表再讀一次，然后結(jié)果集再寫一遍，也是表的數(shù)據(jù)塊數(shù)量的兩倍；

所以兩趟算法中，磁盤IO的代價是 4B，也就是表數(shù)據(jù)塊數(shù)量的4倍。

總結(jié)

兩趟算法被廣泛使用，通過對排序應(yīng)用兩趟算法的機制的分享，將它的執(zhí)行流程，以及存在的限制講解清楚，同時在代價估算時，有一定衡量標(biāo)準(zhǔn)，有利于優(yōu)化器的設(shè)計。

最后分享一段helloworld的代碼

在C語言中，實現(xiàn)單例模式通常是為了確保一個類只有一個實例，并提供一個全局訪問點。然而，C語言沒有內(nèi)置的類或?qū)ο蟮母拍?，因此我們將使用結(jié)構(gòu)體和函數(shù)來模擬單例模式。

下面是一個使用單例模式的 “Hello World” 程序：

#include <stdio.h>
#include <stdlib.h>

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 結(jié)構(gòu)體，它包含一個 printHello 函數(shù)指針。printHello 函數(shù)用于輸出 “Hello, World!”。getInstance 函數(shù)返回 Singleton 實例的指針。我們使用 static 關(guān)鍵字來確保 instance 只在程序運行期間被創(chuàng)建一次。最后，在 main 函數(shù)中，我們通過調(diào)用 getInstance 函數(shù)獲取單例，并調(diào)用 printHello 函數(shù)輸出 “Hello, World!”。

結(jié)尾

非常感謝大家的支持，在瀏覽的同時別忘了留下您寶貴的評論，如果覺得值得鼓勵，請點贊，收藏，我會更加努力！

作者郵箱：study@senllang.onaliyun.com
如有錯誤或者疏漏歡迎指出，互相學(xué)習(xí)。文章來源地址http://www.zghlxwxcb.cn/news/detail-754265.html

到了這里，關(guān)于【數(shù)據(jù)庫】執(zhí)行計劃中的兩趟算法機制原理，基于排序算法來分析，算法的限制，執(zhí)行代價以及優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！