嘿哈布爾！ 我提請您注意這篇文章的翻譯
“關係資料庫是如何運作的”.

當談到關係資料庫時，我情不自禁地認為缺少了一些東西。 它們隨處可見。 有許多不同的資料庫可用，從小型實用的 SQLite 到功能強大的 Teradata。 但只有幾篇文章解釋了資料庫的工作原理。 您可以使用“howdoesarelationaldatabasework”自行搜索，看看結果有多少。 而且，這些文章都很短。 如果您正在尋找最新的熱門技術（BigData、NoSQL 或 JavaScript），您會找到更多深入的文章來解釋它們的工作原理。

關係資料庫是否太古老、太無聊而無法在大學課程、研究論文和書籍之外進行解釋？

作為一名開發人員，我討厭使用我不理解的東西。 如果資料庫已經使用了 40 多年，那一定是有原因的。 多年來，我花了數百個小時來真正理解我每天使用的這些奇怪的黑盒子。 關係數據庫 很有趣，因為他們 基於有用且可重複使用的概念。 如果您有興趣了解資料庫，但從未有時間或意願深入研究這個廣泛的主題，那麼您應該喜歡這篇文章。

雖然這篇文章的標題很明確， 本文的目的不是要了解如何使用資料庫。 因此， 您應該已經知道如何編寫簡單的連接請求和基本查詢 欺詐; 否則你可能看不懂這篇文章。 這是你唯一需要知道的事情，其餘的我會解釋。

我將從一些電腦科學基礎知識開始，例如演算法的時間複雜度 (BigO)。 我知道你們中的一些人討厭這個概念，但如果沒有它，你將無法理解資料庫內部的複雜性。 由於這是一個很大的話題， 我將重點放在 我認為重要的事情: 資料庫如何處理 的SQL 詢問。 我簡單介紹一下 基本資料庫概念這樣在文章的最後您就可以了解幕後發生的事情。

由於這是一篇很長的技術性文章，涉及大量演算法和資料結構，請花點時間閱讀它。 有些概念可能很難理解； 您可以跳過它們，但仍能了解整體思路。

為了方便大家了解更多，本文分為 3 部分：

• 低級和高級資料庫元件概述
• 查詢最佳化過程概述
• 事務和緩衝池管理概述

回歸本源

幾年前（在一個遙遠的星系...），開發人員必須準確地知道他們正在編碼的操作數量。 他們對演算法和資料結構瞭如指掌，因為他們不能浪費慢速電腦的 CPU 和記憶體。

在這一部分中，我將提醒您其中一些概念，因為它們對於理解資料庫至關重要。 我也來介紹一下這個概念 資料庫索引.

O(1) 與 O(n2)

如今，許多開發人員並不關心演算法的時間複雜度……他們是對的！

但是，當您處理大量資料（我不是說數千個）或如果您在毫秒內掙扎時，理解這個概念就變得至關重要。 正如您可以想像的那樣，資料庫必須處理這兩種情況！ 我不會讓你花更多的時間來理解要點。 這將有助於我們稍後理解基於成本的最佳化的概念（成本 基於 優化).

概念

演算法的時間複雜度 用於查看演算法完成給定資料量所需的時間。 為了描述這種複雜性，我們使用大 O 數學符號。該符號與一個函數一起使用，該函數描述了演算法對於給定數量的輸入需要多少次操作。

例如，當我說「這個演算法的複雜度為 O(some_function())」時，這表示演算法需要 some_function(a_certain_amount_of_data) 運算來處理一定量的資料。

在這種情況下， 重要的不是數據量**， 否則 ** 操作數量如何隨著資料量的增加而增加。 時間複雜度不提供確切的操作數量，但它是估計執行時間的好方法。

在此圖中，您可以看到不同類型演算法時間複雜度的操作數量與輸入資料量的關係。 我使用對數刻度來顯示它們。 也就是說，資料量從1快速成長到1億，我們可以看到：

• O(1) 或常數複雜度保持不變（否則就不會稱為常數複雜度）。
• O(登錄(n)) 即使有數十億數據仍然很低.
• 最難的是—— O(n2)，操作數量快速成長.
• 另外兩種併發症也同樣迅速增加。

Примеры

對於少量數據，O(1) 和 O(n2) 之間的差異可以忽略不計。 例如，假設您有一個需要處理 2000 個元素的演算法。

• O(1) 演算法將花費您 1 次操作
• O(log(n)) 演算法將花費您 7 次操作
• O(n) 演算法將花費您 2 次操作
• O(n*log(n)) 演算法將花費您 14 次操作
• O(n2) 演算法將花費您 4 次操作

O(1) 和 O(n2) 之間的差異似乎很大（4 萬次操作），但您最多會損失 2 毫秒，只是眨眼的時間。 事實上，現代處理器可以處理 每秒數億次操作。 這就是為什麼效能和優化在許多 IT 專案中不是問題。

正如我所說，在處理大量數據時了解這個概念仍然很重要。 如果這次演算法必須處理 1 個元素（這對資料庫來說並不算多）：

• O(1) 演算法將花費您 1 次操作
• O(log(n)) 演算法將花費您 14 次操作
• O(n) 演算法將花費您 1 次操作
• O(n*log(n)) 演算法將花費您 14 次操作
• O(n2) 演算法將花費您 1 次操作

我沒有做過數學計算，但我想說，使用 O(n2) 演算法，你有時間喝咖啡（甚至兩杯！）。 如果數據量再加0，你就有時間小睡了。

讓我們更深入地了解一下

為了您的信息：

• 良好的哈希表查找在 O(1) 中找到一個元素。
• 搜尋平衡良好的樹會產生 O(log(n)) 的結果。
• 搜尋數組會在 O(n) 內產生結果。
• 最好的排序演算法的複雜度為 O(n*log(n))。
• 糟糕的排序演算法的複雜度為 O(n2)。

注意：在下面的部分中我們將看到這些演算法和資料結構。

演算法時間複雜度有以下幾種類型：

• 平均狀況
• 最好的情況
• 和最壞的情況

時間複雜度通常是最糟的情況。

我只是談論演算法的時間複雜度，但複雜度也適用於：

• 算法的記憶體消耗
• 磁碟I/O消耗演算法

當然，還有比n2更糟糕的併發症，例如：

• n4：這太可怕了！ 提到的一些演算法具有這種複雜性。
• 3n：這更糟！ 我們將在本文中間看到的演算法之一具有這種複雜性（並且它實際上在許多資料庫中使用）。
• 階乘 n：即使資料量很小，您也永遠無法得到結果。
• nn：如果你遇到這種複雜性，你應該問問自己這是否真的是你的活動領域...

注意：我沒有給你大 O 名稱的實際定義，只是一個想法。 您可以在以下位置閱讀這篇文章 維基百科 為實數（漸近）定義。

歸併排序

當你需要對集合進行排序時你會做什麼？ 什麼？ 你呼叫 sort() 函數...好吧，很好的答案...但是對於資料庫，你必須了解這個 sort() 函數是如何運作的。

有幾種很好的排序演算法，所以我將重點放在最重要的： 歸併排序。 現在您可能不明白為什麼對資料進行排序很有用，但是在查詢最佳化部分之後您應該明白。 此外，理解歸併排序將有助於我們以後理解常見的資料庫連接操作，稱為 合併 加入 （合併協會）.

合併

與許多有用的演算法一樣，合併排序依賴於一個技巧：將 2 個大小為 N/2 的排序數組組合成 N 元素排序數組只需要 N 次操作。 這個操作稱為合併。

讓我們透過一個簡單的例子來看看這意味著什麼：

此圖顯示，要建立最終排序的 8 元素數組，您只需對 2 個 4 元素數組迭代一次。 由於兩個 4 元素數組都已排序：

• 1）比較兩個數組中的兩個當前元素（在開始時當前=第一個）
• 2）然後取最小的一個放入8元素數組中
• 3) 並移動到陣列中取出最小元素的下一個元素
• 並重複 1,2,3、XNUMX、XNUMX，直到到達其中一個陣列的最後一個元素。
• 然後，將另一個陣列的剩餘元素放入 8 元素陣列中。

這是可行的，因為兩個 4 元素數組都已排序，因此您不必在這些數組中「返回」。

現在我們了解了這個技巧，這是我的合併偽代碼：

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

歸併排序將一個問題分解成更小的問題，然後找到更小的問題的結果，得到原始問題的結果（註：這個演算法稱為分而治之）。 如果你不明白這個演算法，不用擔心； 我第一次看到的時候沒看懂。 如果它可以幫助你，我認為這個演算法是一個兩階段演算法：

• 劃分階段，將陣列分成更小的數組
• 排序階段是將小數組組合（使用並集）以形成更大的數組。

分裂階段

在劃分階段，陣列分3步驟被劃分為單一陣列。 正式的步驟數是 log(N)（因為 N=8，log(N) = 3）。

我怎麼知道這個？

我是天才！ 一句話—數學。 這個想法是，每一步將原始數組的大小除以 2。步數就是可以將原始數組一分為二的次數。 這是對數（以 2 為底）的精確定義。

排序階段

在排序階段，您從單一（單元素）陣列開始。 在每個步驟中，您套用多個合併操作，總成本為 N = 8 個操作：

• 在第一階段，您有 4 次合併，每次需要 2 次操作
• 在第二步驟中，您有 2 次合併，每次需要 4 次操作
• 在第三步驟中，您有 1 次合併，需要 8 次操作

由於有 log(N) 個步驟， 總成本N * 記錄 (N) 次操作.

歸併排序的優點

為什麼這個演算法如此強大？

因為：

• 您可以更改它以減少記憶體佔用，這樣您就不會建立新數組而是直接修改輸入數組。

注意：這種演算法稱為 in - 地點 （無需額外記憶體即可排序）。

• 您可以將其變更為同時使用磁碟空間和少量內存，而不會產生大量磁碟 I/O 開銷。 這個想法是僅將當前正在處理的那些部分載入到記憶體中。 當您需要對僅具有 100 MB 記憶體緩衝區的多 GB 表進行排序時，這一點非常重要。

注意：這種演算法稱為 外部排序.

• 您可以將其變更為在多個進程/執行緒/伺服器上運行。

例如，分散式歸併排序是關鍵元件之一 Hadoop的 （這是大數據中的一種結構）。

• 這個演算法可以把鉛變成金（真的！）。

大多數（如果不是全部）資料庫都使用這種排序演算法，但它並不是唯一的一種。 如果你想了解更多，你可以閱讀這篇文章 研究工作，討論了常見資料庫排序演算法的優缺點。

數組、樹和哈希表

現在我們了解了時間複雜度和排序的思想，我應該告訴你3種資料結構。 這很重要，因為他們 是現代資料庫的基礎。 我也來介紹一下這個概念 資料庫索引.

排列

二維數組是最簡單的資料結構。 可以將表視為數組。 例如：

這個二維數組是一個包含行和列的表：

• 每行代表一個實體
• 列儲存描述實體的屬性。
• 每列儲存特定類型的資料（整數、字串、日期...）。

這對於儲存和視覺化資料很方便，但是，當您需要查找特定值時，這並不合適。

例如，如果您想查找在英國工作的所有人員，則需要查看每一行以確定該行是否屬於英國。 這將花費你N筆交易哪裡 N - 行數，這還不錯，但是有沒有更快的方法？ 現在是我們熟悉樹木的時候了。

注意：大多數現代資料庫都提供擴展數組來有效地儲存表：堆組織表和索引組織表。 但這並不能改變在一組列中快速找出特定條件的問題。

資料庫樹和索引

二元搜尋樹是一種具有特殊性質的二元樹，每個節點的鍵必須是：

• 大於左子樹中儲存的所有鍵
• 小於右子樹中儲存的所有鍵

讓我們看看這在視覺上意味著什麼

想法

這棵樹有 N = 15 個元素。 假設我正在尋找 208：

• 我從鍵為 136 的根開始。由於 136<208，我查看節點 136 的右子樹。
• 398>208 因此我正在查看節點 398 的左子樹
• 250>208 因此我正在查看節點 250 的左子樹
• 200<208，因此我正在查看節點 200 的右子樹。但是 200 沒有右子樹， 值不存在 （因為如果存在的話，它將在右子樹200中）。

現在假設我正在尋找 40

• 我從鍵為 136 的根開始。由於 136 > 40，我查看節點 136 的左子樹。
• 80 > 40，因此我正在查看節點 80 的左子樹
• 40=40， 節點存在。 我檢索節點內的行 ID（圖中未顯示）並在表中尋找給定的行 ID。
• 知道行 ID 可以讓我準確地知道資料在表中的位置，這樣我就可以立即檢索它。

最後，這兩次搜尋都會花費我樹內的層數。 如果您仔細閱讀有關合併排序的部分，您應該會看到有 log(N) 個層級。 事實證明， 搜尋成本日誌(N)， 不錯！

讓我們回到我們的問題

但這非常抽象，所以讓我們回到我們的問題。 想像一個代表上表中某人所在國家的字串，而不是簡單的整數。 假設您有一棵樹，其中包含表格的「國家」欄位（第 3 列）：

• 如果你想知道誰在英國工作
• 你查看樹來取得代表英國的節點
• 在「UKnode」內，您將找到英國工人記錄的位置。

如果直接使用數組，此搜尋將花費 log(N) 次操作，而不是 N 次操作。 你剛才介紹的是 資料庫索引.

您可以為任何欄位組（字串、數字、2 行、數字和字串、日期...）建立索引樹，只要您有一個比較鍵（即欄位組）的函數，以便您可以設定 鍵之間的順序 （資料庫中的任何基本類型都是這種情況）。

B+樹索引

雖然這棵樹可以很好地獲得特定值，但當您需要時就會出現一個大問題 取得兩個值之間的多個元素。 這將花費 O(N)，因為您必須查看樹中的每個節點並檢查它是否在這兩個值之間（例如，對樹進行有序遍歷）。 此外，此操作對磁碟 I/O 不友好，因為您必須讀取整個樹。 我們需要找到一種高效率執行的方法 範圍請求。 為了解決這個問題，現代資料庫使用了先前樹的修改版本，稱為 B+Tree。 在 B+Tree 樹​​中：

• 僅最低節點（葉子） 儲存資訊 （相關表格中行的位置）
• 其餘的節點都在這裡 用於路由 到正確的節點 搜尋期間.

正如您所看到的，這裡有更多的節點（兩次）。 事實上，您還有其他節點，即“決策節點”，它將幫助您找到正確的節點（它儲存關聯表中行的位置）。 但搜尋複雜度還是O(log(N))（只多了一層）。 最大的差別在於 較低層級的節點與其後繼節點相連.

使用這個 B+Tree，如果您要尋找 40 到 100 之間的值：

• 您只需查找 40（如果 40 不存在，則查找 40 之後最接近的值），就像處理前一棵樹一樣。
• 然後使用直接繼承人連結收集 40 個繼承人，直到達到 100 個。

假設您找到 M 個後繼者，且樹有 N 個節點。 與先前的樹一樣，尋找特定節點的成本為 log(N)。 但是一旦你得到了這個節點，你就會在M次操作中得到M個後繼者，並引用他們的後繼者。 本次搜尋僅需花費M+log(N) 與前一棵樹上的 N 個操作進行比較。 此外，您不必讀取完整的樹（只需 M+log(N) 個節點），這意味著更少的磁碟使用量。 如果 M 很小（例如 200 行）而 N 很大（1 行），則會有很大的差異。

但這裡又出現了新問題（再次！）。 如果您在資料庫中（以及關聯的 B+Tree 索引中）新增或刪除一行：

• 您必須維護 B+Tree 內節點之間的順序，否則您將無法找到未排序樹內的節點。
• B+Tree 必須保持盡可能少的層數，否則 O(log(N)) 時間複雜度將變成 O(N)。

換句話說，B+Tree必須是自序且平衡的。 幸運的是，這可以透過智慧刪除和插入操作來實現。 但這是有代價的：B+ 樹中的插入和刪除成本為 O(log(N))。 這就是為什麼你們有些人聽說過 使用太多索引不是一個好主意。 真的嗎， 您正在減慢表中行的快速插入/更新/刪除速度因為資料庫需要對每個索引使用昂貴的 O(log(N)) 操作來更新資料表的索引。 而且，增加索引意味著更多的工作量 交易經理 （將在文末介紹）。

有關更多詳細信息，您可以查看維基百科文章 B+樹。 如果您想要在資料庫中實作 B+Tree 的範例，請查看 本文 и 本文 來自領先的 MySQL 開發人員。 它們都專注於 InnoDB（MySQL 引擎）如何處理索引。

註：一位讀者告訴我，由於低階優化，B+樹應該是完全平衡的。

哈希表

我們最後一個重要的資料結構是哈希表。 當您想要快速查找值時，這非常有用。 而且，理解哈希表將有助於我們以後理解一種常見的資料庫連接操作，稱為雜湊連接（ 散列連接）。 資料庫也使用此資料結構來儲存一些內部內容（例如 鎖表 或 緩衝池，我們稍後會看到這兩個概念）。

哈希表是一種根據鍵快速找到元素的資料結構。 要建立哈希表，您需要定義：

• 關鍵 為你的元素
• 哈希函數 用於鑰匙。 計算出的密鑰哈希給出了元素的位置（稱為 段 ).
• 比較按鍵的功能。 找到正確的段落後，您必須使用此比較在該段中找到您要尋找的元素。

簡單的例子

讓我們舉一個明顯的例子：

該哈希表有 10 個段落。 因為我比較懶，所以只畫了5段，但我知道你很聰明，所以我就讓你自己畫另外5段。 我使用了密鑰以 10 為模的雜湊函數。 換句話說，我只儲存元素鍵的最後一位數字來尋找其段落：

• 如果最後一位為0，則該元素屬於段0，
• 如果最後一位為1，則該元素屬於段1，
• 如果最後一位是2，則該元素落入區域2，
• ...

我使用的比較函數只是兩個整數之間的相等性。

假設您想要取得第 78 號元素：

• 哈希表計算出78的雜湊碼，即8。
• 哈希表查看段 8，找到的第一個元素是 78。
• 她將物品 78 退還給你
• 搜尋僅需 2 次操作 （一個用於計算哈希值，另一個用於查找段內的元素）。

現在假設您想要取得元素 59：

• 哈希表計算出59的雜湊碼，即9。
• 哈希表在段 9 中查找，找到的第一個元素是 99。由於 99!=59，所以元素 99 不是有效元素。
• 使用相同的邏輯，取第二個元素 (9)、第三個元素 (79)、...、最後一個元素 (29)。
• 未找到元素。
• 搜尋花了 7 次操作.

良好的哈希函數

正如你所看到的，根據你所尋找的價值，成本是不一樣的！

如果我現在更改密鑰的雜湊函數模 1（即取最後 000 位數字），則第二次查找只需要 000 次操作，因為段 6 中沒有元素。 真正的挑戰是找到一個好的雜湊函數來創建包含極少數元素的儲存桶.

在我的範例中，找到一個好的雜湊函數很容易。 但這是一個簡單的例子，當關鍵是：時找到一個好的雜湊函數會更困難：

• 字串（例如 - 姓氏）
• 2 行（例如 - 姓氏和名字）
• 2 行和日期（例如 - 姓氏、名字和出生日期）
• ...

有了好的雜湊函數，哈希表查找的成本為 O(1).

數組與哈希表

為什麼不使用陣列呢？

嗯，好問題。

• 哈希表可以是 部分載入到記憶體中，其餘段可以保留在磁碟上。
• 對於數組，您必須使用記憶體中的連續空間。 如果您正在加載一個大表 很難找到足夠的連續空間.
• 對於哈希表，您可以選擇所需的按鍵（例如，國家/地區和人員的姓氏）。

欲了解更多信息，您可以閱讀有關的文章 Java的哈希圖，這是哈希表的有效實作； 您無需了解 Java 即可理解本文中介紹的概念。

來源： www.habr.com