大數(shù)據(jù)中數(shù)據(jù)庫是如何工作的（一）

　　當(dāng)涉及到關(guān)系數(shù)據(jù)庫時，我不禁會以為有些東西丟失了。它們無處不在。有許多不同的數(shù)據(jù)庫：從小型且有用的SQLite到功能強(qiáng)大的Teradata。但是，只有少數(shù)幾篇文章解釋了數(shù)據(jù)庫的工作方式。你可以自己在Google上搜索“關(guān)系數(shù)據(jù)庫的工作原理”，可以查看結(jié)果很少，而且文章簡短?，F(xiàn)在介紹它們的工作原理，看看大數(shù)據(jù)中數(shù)據(jù)庫是如何工作的。
 

　　關(guān)系數(shù)據(jù)庫是否太老太無聊，無法在大學(xué)課程，研究論文和書籍之外進(jìn)行解釋?
 

　　作為開發(fā)人員，肯定不會使用自己不了解的東西。而且，如果數(shù)據(jù)庫已經(jīng)使用了很多年，則一定有原因。有必要花時間來真正了解每天使用的這些奇怪的黑匣子。 關(guān)系型數(shù)據(jù)庫是非常有趣的，因為他們是基于有用的和可重復(fù)使用的概念。
 

　　首先，你要知道如何編寫一個簡單的聯(lián)接查詢和基本的CRUD查詢。開發(fā)人員必須確切地知道他們正在編碼的操作數(shù)。他們完全知道自己的算法和數(shù)據(jù)結(jié)構(gòu)，因為他們負(fù)擔(dān)不起浪費速度較慢的計算機(jī)的CPU和內(nèi)存。
 

　　O(1)對O(n 2)
 

　　如今，許多開發(fā)人員都不在乎時間的復(fù)雜性……他們是對的!
 

　　但是，當(dāng)你處理大量數(shù)據(jù)時，或者如果你要爭奪毫秒級的時間，那么了解此概念就變得至關(guān)重要。這個概念的時間復(fù)雜度是用來看看的算法需要多長時間為給定的數(shù)據(jù)量。為了描述這種復(fù)雜性，計算機(jī)科學(xué)家使用了數(shù)學(xué)上的大O符號。該符號與描述了算法針對給定數(shù)量的輸入數(shù)據(jù)需要進(jìn)行多少次操作的函數(shù)一起使用。
 

　　例如，當(dāng)“此算法在O(some_function())中”時，它意味著對于一定數(shù)量的數(shù)據(jù)，該算法需要some_function(a_certain_amount_of_data)操作才能完成其工作。
 

　　重要的不是數(shù)據(jù)量，而是當(dāng)數(shù)據(jù)量增加時操作數(shù)增加的方式。時間復(fù)雜度并不能給出確切的操作數(shù)量，而是一個好主意。
 

　　在此圖中，你可以看到不同類型的復(fù)雜性的演變。我用對數(shù)標(biāo)度繪制它。換句話說，數(shù)據(jù)數(shù)量正迅速從1億增加到10億。我們可以看到：
 

　　在O(1)或恒定的復(fù)雜性保持不變(否則就不叫常復(fù)雜)。
 

　　即使有數(shù)十億個數(shù)據(jù)，O(log(n))仍保持較低水平。
 

　　復(fù)雜度最差的是O(n 2)，其中操作數(shù)量迅速激增
 

　　這兩個OT ^ h鉺共米p樂喜牛逼我ES正在迅速增加
 

　　例子
 

　　數(shù)據(jù)量少時，O(1)和O(n 2)之間的差異可以忽略不計。例如，假設(shè)你有一個需要處理2000個元素的算法。
 

　　O(1)算法將花費你1次操作
 

　　O(log(n))算法將花費你7次操作
 

　　O(n)算法將花費你2000次操作
 

　　O(n * log(n))算法將花費你14000次操作
 

　　O(n 2)算法將花費你4000000次操作
 

　　O(1)和O(n 2)之間的差異似乎很大(400萬)，但是你最多會在2毫秒內(nèi)迷失方向，只是眨眼的時間。實際上，當(dāng)前的處理器每秒可以處理數(shù)億個操作。這就是為什么性能和優(yōu)化在許多IT項目中都不是問題的原因。
 

　　正如前面所說，面對大量數(shù)據(jù)時，了解這一概念仍然很重要。如果這一次該算法需要處理1 000 000個元素(對于數(shù)據(jù)庫來說這不是那么大)：
 

　　O(1)算法將花費你1次操作
 

　　O(log(n))算法將花費你14次操作
 

　　O(n)算法將花費你1000000次操作
 

　　O(n * log(n))算法將花費你14000000次操作
 

　　O(n 2)算法將花費你1000000000000次操作
 

　　沒有做數(shù)學(xué)運算，但是用O(n 2)算法，你可以有時間喝咖啡。如果你在數(shù)據(jù)量上再加上0，那么你將有時間進(jìn)行小睡。
 

　　更深入給你一個想法：
 

　　在良好的哈希表中進(jìn)行搜索可得出O(1)中的一個元素
 

　　在平衡良好的樹中進(jìn)行搜索得到的結(jié)果為O(log(n))
 

　　數(shù)組中的搜索結(jié)果為O(n)
 

　　最佳排序算法的復(fù)雜度為O(n * log(n))。
 

　　不良的排序算法具有O(n 2)復(fù)雜度
 

　　注意：在下一部分中，我們將看到這些算法和數(shù)據(jù)結(jié)構(gòu)。
 

　　時間復(fù)雜度有多種類型：平均情況，最好的情況，最壞的情況。
 

　　時間復(fù)雜度通常是最壞的情況，只談?wù)摃r間復(fù)雜性，但是復(fù)雜性也適用于：算法的內(nèi)存消耗，算法的磁盤I / O消耗。
 

　　當(dāng)然，復(fù)雜度比n 2還差，例如：
 

　　n 4：太爛了!某些算法具有這種復(fù)雜性。
 

　　3 n：更糟!有算法具有這種復(fù)雜性并且它確實在許多數(shù)據(jù)庫中得到了使用。
 

　　階乘n：即使數(shù)據(jù)量很少，也永遠(yuǎn)不會得到結(jié)果。
 

　　n n：如果你最終遇到這種復(fù)雜性，你應(yīng)該問問自己，IT是否真的是你的領(lǐng)域……
 

　　合并排序
 

　　當(dāng)你需要對集合進(jìn)行排序時，你會怎么做?你可以調(diào)用sort()函數(shù)，但是對于數(shù)據(jù)庫，你必須了解sort()函數(shù)的工作方式。
 

　　有幾種不錯的排序算法，重點介紹一種：合并排序。你可能現(xiàn)在不明白為什么排序數(shù)據(jù)很有用，但是你應(yīng)該在查詢優(yōu)化部分之后進(jìn)行。
 

　　合并：像許多有用的算法一樣，合并排序基于一個技巧：將2個大小為N / 2的排序數(shù)組合并為N個元素的排序數(shù)組僅需要N次操作。此操作稱為合并。
 

　　你可以在該圖上看到，要構(gòu)造最終的8個元素的排序數(shù)組，只需要在2個4元素數(shù)組中進(jìn)行一次迭代即可。由于兩個4元素數(shù)組均已排序：
 

　　1)比較兩個數(shù)組中的兩個當(dāng)前元素(current =第一次，第一次)
 

　　2)然后將最低的一個放入8個元素的數(shù)組中
 

　　3)并轉(zhuǎn)到數(shù)組中的下一個元素，你選擇了最低元素
 

　　并重復(fù)1,2,3，直到到達(dá)數(shù)組之一的最后一個元素。
 

　　然后，將另一個數(shù)組的其余元素放入8元素數(shù)組中。
 

　　這是可行的，因為兩個4元素數(shù)組都已排序，因此你無需在這些數(shù)組中“返回”。
 

　　現(xiàn)在我們已經(jīng)了解了這個技巧，這是我的歸類排序的偽代碼。
 

　　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;
 

　　合并排序?qū)栴}分解為較小的問題，然后找到較小問題的結(jié)果以得到初始問題的結(jié)果(注意：這種算法稱為分治法)。如果你不了解此算法，請不要擔(dān)心。第一次見時我聽不懂。如果可以幫到你，我將此算法視為兩階段算法：
 

　　分割階段，將陣列分為較小的陣列
 

　　將小數(shù)組放在一起(使用合并)以形成更大數(shù)組的排序階段。
 

　　分割階段
 

 

　　在除法階段，使用3個步驟將陣列分為單一陣列。正式的步驟數(shù)為log(N)(因為N = 8，log(N)= 3)。
 

　　一言以蔽之：數(shù)學(xué)。這個想法是，每個步驟都將初始數(shù)組的大小除以2。步驟數(shù)是可以將初始數(shù)組除以2的次數(shù)。這是對數(shù)的精確定義(以2為底)。
 

　　分選階段
 

　　在排序階段，從單一數(shù)組開始。在每個步驟中，你將應(yīng)用多個合并，并且總成本為N = 8次操作：
 

　　第一步，你有4個合并，每個合并需要2個操作
 

　　在第二步中，你有2個合并，每個合并花費4個操作
 

　　在第三步中，你有1個合并需要8次操作
 

　　由于存在log(N)個步驟，因此總成本為N * log(N)個操作。
 

　　合并排序的力量
 

　　為什么此算法如此強(qiáng)大?
 

　　因為：
 

　　你可以修改它以減少內(nèi)存占用，而不用創(chuàng)建新數(shù)組，而是直接修改輸入數(shù)組。
 

　　注意：這種算法稱為就地。
 

　　你可以對其進(jìn)行修改，以便同時使用磁盤空間和少量內(nèi)存，而不會產(chǎn)生巨大的磁盤I / O損失。這個想法是只將當(dāng)前正在處理的零件加載到內(nèi)存中。當(dāng)你需要對僅具有100 MB內(nèi)存緩沖區(qū)的多GB表進(jìn)行排序時，這一點很重要。
 

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

　　你可以修改它以在多個進(jìn)程/線程/服務(wù)器上運行。
 

　　例如，分布式合并排序是Hadoop(這是大數(shù)據(jù)中的THE框架)的關(guān)鍵組件之一。

　　該算法可以將鉛變成金(真實的事實!)。
 

　　這種排序算法已在大多數(shù)(如果不是全部)數(shù)據(jù)庫中使用，但并不是唯一的一種。如果你想了解更多信息，可以閱讀這份研究論文，其中討論了數(shù)據(jù)庫中常見排序算法的優(yōu)缺點。
 

　　數(shù)組，樹和哈希表
 

　　既然我們了解了時間復(fù)雜度和排序背后的思想，那么我必須向你介紹3種數(shù)據(jù)結(jié)構(gòu)。這很重要，因為它們是現(xiàn)代數(shù)據(jù)庫的骨干。我還將介紹數(shù)據(jù)庫索引的概念。
 

　　大批
 

　　二維數(shù)組是最簡單的數(shù)據(jù)結(jié)構(gòu)。一個表可以看作是一個數(shù)組。例如：
 

 

　　此二維數(shù)組是具有行和列的表：
 

　　每行代表一個主題
 

　　這些列描述主題的功能。
 

　　每列存儲某種類型的數(shù)據(jù)(整數(shù)，字符串，日期…)。
 

　　盡管存儲和可視化數(shù)據(jù)很棒，但是當(dāng)你需要查找特定值時，它很糟糕。
 

　　樹和數(shù)據(jù)庫索引
 

　　二進(jìn)制搜索樹是具有特殊屬性的二進(jìn)制樹，每個節(jié)點中的關(guān)鍵字必須為：
 

　　大于存儲在左側(cè)子樹中的所有鍵
 

　　小于存儲在右側(cè)子樹中的所有鍵
 

　　讓我們看一下視覺上的含義
 

 

　　這棵樹有N = 15個元素。假設(shè)我要尋找208：
 

　　我從鍵為136的根開始。由于136 <208，所以我看節(jié)點136的右子樹。
 

　　398> 208所以，我看節(jié)點398的左子樹
 

　　250> 208因此，我看一下節(jié)點250的左子樹
 

　　200 <208，所以，我看節(jié)點200的右子樹。但是200沒有右子樹，該值不存在(因為如果確實存在，它將在200的右子樹中)
 

　　現(xiàn)在假設(shè)我正在尋找40
 

　　我從鍵為136的根開始。由于136> 40，所以我看節(jié)點136的左子樹。
 

　　80> 40所以，我看節(jié)點80的左子樹
 

　　40 = 40，該節(jié)點存在。我提取節(jié)點內(nèi)部的行的ID(圖中未顯示)，并查看表中給定的行ID。
 

　　知道行ID后，我便知道數(shù)據(jù)在表上的確切位置，因此我可以立即獲取它。
 

　　最后，兩次搜索使我損失了樹內(nèi)的層數(shù)。如果你仔細(xì)閱讀合并排序中的部分，你應(yīng)該會看到存在log(N)級別。因此搜索的成本為log(N)，還不錯!
 

　　回到我們的問題
 

　　但是，這些內(nèi)容非常抽象，讓我們回到我們的問題上來。想象一個代表上表中某人所在國家的字符串，而不是一個愚蠢的整數(shù)。假設(shè)你有一棵包含表的“國家”列的樹：
 

　　如果你想知道誰在英國工作
 

　　你看樹得到代表英國的節(jié)點
 

　　在“英國節(jié)點”內(nèi)，你將找到英國工人行的位置。
 

　　如果你直接使用數(shù)組，則此搜索僅花費你log(N)個操作，而不是N個操作。你剛剛想象的是一個數(shù)據(jù)庫索引。
 

　　你可以為任何一組列(一個字符串，一個整數(shù)，2個字符串，一個整數(shù)和一個字符串，一個日期……)構(gòu)建樹索引，只要你具有比較鍵(即列組)的功能即可，你可以在鍵之間建立順序 (數(shù)據(jù)庫中的任何基本類型都是這種情況)。
 

　　B +樹索引
 

　　盡管此樹可以很好地獲取特定值，但是當(dāng)你需要在兩個值之間獲取多個元素 時，仍然存在BIG問題。這將花費O(N)，因為你必須查看樹中的每個節(jié)點，并檢查它是否在這兩個值之間(例如，按順序遍歷樹)。此外，此操作不是磁盤I / O友好的，因為你必須閱讀完整的樹。我們需要找到一種有效地進(jìn)行范圍查詢的方法。為了解決此問題，現(xiàn)代數(shù)據(jù)庫使用了以前的樹(稱為B + Tree)的修改版本。在B +樹中：
 

　　只有最低的節(jié)點(葉子)存儲信息(相關(guān)表中行的位置)
 

　　其他節(jié)點只是在搜索過程中路由到正確的節(jié)點。
 

 

　　如你所見，有更多的節(jié)點(更多的節(jié)點)。實際上，你還有其他節(jié)點，即“決策節(jié)點”，可以幫助你找到合適的節(jié)點(該節(jié)點將行的位置存儲在關(guān)聯(lián)表中)。但是搜索的復(fù)雜度仍然在O(log(N))中(只有一個級別)。最大的區(qū)別是最低的節(jié)點鏈接到其后繼節(jié)點。
 

　　使用此B + Tree，如果要查找40到100之間的值：
 

　　你只需要像前一棵樹一樣查找40(如果不存在40，則查找40之后的最接近值)。
 

　　然后使用到后繼者的直接鏈接收集40個后繼者，直到達(dá)到100。
 

　　假設(shè)你找到了M個后繼節(jié)點，并且樹上有N個節(jié)點。像上一棵樹一樣，搜索特定節(jié)點的成本為log(N)。但是，一旦有了該節(jié)點，就可以在M個操作中獲得M個后繼者，并帶有指向其后繼者的鏈接。該搜索僅花費M + log(N)個操作，而前一個樹則花費N個操作。而且，你不需要讀取完整的樹(僅需M + log(N)個節(jié)點)，這意味著磁盤使用量更少。如果M低(例如200行)而N大(1 000萬行)，則會產(chǎn)生很大的差異。
 

　　但是又有新的問題!如果你在數(shù)據(jù)庫中(因此在關(guān)聯(lián)的B + Tree索引中)添加或刪除行：
 

　　你必須保持B + Tree內(nèi)部節(jié)點之間的順序，否則你將無法在混亂中找到節(jié)點。
 

　　你必須在B + Tree中保持盡可能少的級別數(shù)，否則O(log(N))中的時間復(fù)雜度將變?yōu)镺(N)。
 

　　換句話說，B +樹需要自我排序和自我平衡。幸運的是，這可以通過智能刪除和插入操作實現(xiàn)。但這要付出代價：B +樹中的插入和刪除在O(log(N))中。這就是為什么有些人聽說使用太多索引不是一個好主意的原因。確實，你正在減慢表中行的快速插入/更新/刪除的速度，因為數(shù)據(jù)庫需要使用每個索引的昂貴O(log(N))操作來更新表的索引。而且，添加索引意味著事務(wù)管理器會增加工作量(我們將在本文結(jié)尾看到該管理器)。
 

　　哈希表
 

　　我們最后一個重要的數(shù)據(jù)結(jié)構(gòu)是哈希表。當(dāng)你想快速尋找價值時，這非常有用。此外，了解哈希表將有助于我們稍后理解稱為哈希聯(lián)接的常見數(shù)據(jù)庫聯(lián)接操作。數(shù)據(jù)庫還使用此數(shù)據(jù)結(jié)構(gòu)來存儲一些內(nèi)部內(nèi)容(例如鎖表或緩沖池，稍后將介紹這兩個概念)
 

　　哈希表是一種數(shù)據(jù)結(jié)構(gòu)，可快速找到具有其鍵的元素。要構(gòu)建哈希表，你需要定義：
 

　　你元素的關(guān)鍵
 

　　鍵的哈希函數(shù)。計算得出的鍵的哈希值給出了元素(稱為buckets)的位置。
 

　　比較鍵的功能。找到正確的存儲桶后，你必須使用此比較在存儲桶中查找要查找的元素。
 

　　一個簡單的例子
 

　　讓我們看一個直觀的例子：
 

 

　　該哈希表有10個存儲桶。由于我很懶，我只抽了5個水桶，但我知道你很聰明，所以讓你想象另外5個水桶。我使用的哈希函數(shù)是密鑰的模10。換句話說，我只保留元素鍵的最后一位來查找其存儲桶：
 

　　如果最后一位數(shù)字為0，則該元素最終出現(xiàn)在存儲區(qū)0中，
 

　　如果最后一位數(shù)字為1，則該元素最終出現(xiàn)在存儲桶1中，
 

　　如果最后一位數(shù)字為2，則該元素最終出現(xiàn)在存儲桶2中，
 

　　…

　　我使用的比較函數(shù)只是2個整數(shù)之間的相等。
 

　　假設(shè)你要獲取元素78：
 

　　哈希表計算78的哈希碼，即8。
 

　　它在存儲桶8中查找，找到的第一個元素是78。
 

　　它給你元素78
 

　　的 搜索成本只有2個操作(1計算散列值，而另一個用于求出鏟斗內(nèi)的元件)。
 

　　現(xiàn)在，假設(shè)你要獲取元素59：
 

　　哈希表計算59的哈希碼，即9。
 

　　它在存儲桶9中查找，找到的第一個元素是99。由于99!= 59，因此元素99不是正確的元素。
 

　　使用相同的邏輯，它查看第二個元素(9)，第三個元素(79)，…和最后一個元素(29)。
 

　　元素不存在。
 

　　搜索需要進(jìn)行7次操作。
 

　　良好的哈希函數(shù)，根據(jù)你所尋找的價值，成本是不一樣的!
 

　　如果現(xiàn)在我用鍵的模數(shù)1 000 000更改哈希函數(shù)(即取最后6位數(shù)字)，則第二次搜索僅花費1次操作，因為存儲桶000059中沒有元素。真正的挑戰(zhàn)是找到一個好的散列函數(shù)，該函數(shù)將創(chuàng)建包含少量元素的存儲桶。
 

　　一個簡單的示例，當(dāng)鍵為：
 

　　字符串(例如某個人的姓氏)
 

　　2個字符串(例如，一個人的姓氏和名字)
 

　　2個字符串和一個日期(例如，一個人的姓，名和出生日期)
 

　　…
 

　　有了良好的哈希函數(shù)， 哈希表中的搜索就在O(1)中。
 

　　數(shù)組與哈希表
 

　　為什么不使用數(shù)組?哈希表可以一半加載到內(nèi)存中，而其他存儲桶可以保留在磁盤上。對于數(shù)組，你必須在內(nèi)存中使用連續(xù)的空間。如果要加載大表，則很難有足夠的連續(xù)空間。使用哈希表，你可以選擇所需的鍵(例如國家/地區(qū)和一個人的姓氏)。
 

　　以上是數(shù)據(jù)庫內(nèi)部的基本組件。大數(shù)據(jù)中數(shù)據(jù)庫如何工作我們分成幾個部分介紹，今天就先到這里了，對大數(shù)據(jù)分析感興趣的朋友可以到AAA教育官網(wǎng)了解一下。