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

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

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

　　作為開發(fā)人員，肯定不會(huì)使用自己不了解的東西。而且，如果數(shù)據(jù)庫已經(jīng)使用了很多年，則一定有原因。有必要花時(shí)間來真正了解每天使用的這些奇怪的黑匣子。 關(guān)系型數(shù)據(jù)庫是非常有趣的，因?yàn)樗麄兪腔谟杏玫暮涂芍貜?fù)使用的概念。
 

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

　　O(1)對(duì)O(n 2)
 

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

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

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

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

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

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

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

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

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

　　例子
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　更深入給你一個(gè)想法：
 

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

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

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

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

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

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

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

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

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

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

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

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

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

　　合并排序
 

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

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

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

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

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

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

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

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

　　然后，將另一個(gè)數(shù)組的其余元素放入8元素?cái)?shù)組中。
 

　　這是可行的，因?yàn)閮蓚€(gè)4元素?cái)?shù)組都已排序，因此你無需在這些數(shù)組中“返回”。
 

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

　　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é)果(注意：這種算法稱為分治法)。如果你不了解此算法，請(qǐng)不要擔(dān)心。第一次見時(shí)我聽不懂。如果可以幫到你，我將此算法視為兩階段算法：
 

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

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

　　分割階段
 

 

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

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

　　分選階段
 

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

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

　　在第二步中，你有2個(gè)合并，每個(gè)合并花費(fèi)4個(gè)操作
 

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

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

　　合并排序的力量
 

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

　　因?yàn)椋?br />  

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

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

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

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

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

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

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

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

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

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

　　大批
 

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

 

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

　　每行代表一個(gè)主題
 

　　這些列描述主題的功能。
 

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

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

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

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

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

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

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

 

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

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

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

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

　　200 <208，所以，我看節(jié)點(diǎn)200的右子樹。但是200沒有右子樹，該值不存在(因?yàn)槿绻_實(shí)存在，它將在200的右子樹中)
 

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

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

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

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

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

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

　　回到我們的問題
 

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

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

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

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

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

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

　　B +樹索引
 

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

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

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

 

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

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

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

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

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

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

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

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

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

　　哈希表
 

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

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

　　你元素的關(guān)鍵
 

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

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

　　一個(gè)簡(jiǎn)單的例子
 

　　讓我們看一個(gè)直觀的例子：
 

 

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

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

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

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

　　…

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

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

　　哈希表計(jì)算78的哈希碼，即8。
 

　　它在存儲(chǔ)桶8中查找，找到的第一個(gè)元素是78。
 

　　它給你元素78
 

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

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

　　哈希表計(jì)算59的哈希碼，即9。
 

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

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

　　元素不存在。
 

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

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

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

　　一個(gè)簡(jiǎn)單的示例，當(dāng)鍵為：
 

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

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

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

　　…
 

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

　　數(shù)組與哈希表
 

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

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