大數據中數據庫是如何工作的（一）

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

　　關系數據庫是否太老太無聊，無法在大學課程，研究論文和書籍之外進行解釋?
 

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

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

　　O(1)對O(n 2)
 

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

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

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

　　重要的不是數據量，而是當數據量增加時操作數增加的方式。時間復雜度并不能給出確切的操作數量，而是一個好主意。
 

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

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

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

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

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

　　例子
 

　　數據量少時，O(1)和O(n 2)之間的差異可以忽略不計。例如，假設你有一個需要處理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毫秒內迷失方向，只是眨眼的時間。實際上，當前的處理器每秒可以處理數億個操作。這就是為什么性能和優(yōu)化在許多IT項目中都不是問題的原因。
 

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

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

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

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

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

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

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

　　更深入給你一個想法：
 

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

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

　　數組中的搜索結果為O(n)
 

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

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

　　注意：在下一部分中，我們將看到這些算法和數據結構。
 

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

　　時間復雜度通常是最壞的情況，只談論時間復雜性，但是復雜性也適用于：算法的內存消耗，算法的磁盤I / O消耗。
 

　　當然，復雜度比n 2還差，例如：
 

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

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

　　階乘n：即使數據量很少，也永遠不會得到結果。
 

　　n n：如果你最終遇到這種復雜性，你應該問問自己，IT是否真的是你的領域……
 

　　合并排序
 

　　當你需要對集合進行排序時，你會怎么做?你可以調用sort()函數，但是對于數據庫，你必須了解sort()函數的工作方式。
 

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

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

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

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

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

　　3)并轉到數組中的下一個元素，你選擇了最低元素
 

　　并重復1,2,3，直到到達數組之一的最后一個元素。
 

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

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

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

　　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的次數。這是對數的精確定義(以2為底)。
 

　　分選階段
 

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

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

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

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

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

　　合并排序的力量
 

　　為什么此算法如此強大?
 

　　因為：
 

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

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

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

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

　　你可以修改它以在多個進程/線程/服務器上運行。
 

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

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

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

　　數組，樹和哈希表
 

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

　　大批
 

　　二維數組是最簡單的數據結構。一個表可以看作是一個數組。例如：
 

 

　　此二維數組是具有行和列的表：
 

　　每行代表一個主題
 

　　這些列描述主題的功能。
 

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

　　盡管存儲和可視化數據很棒，但是當你需要查找特定值時，它很糟糕。
 

　　樹和數據庫索引
 

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

　　大于存儲在左側子樹中的所有鍵
 

　　小于存儲在右側子樹中的所有鍵
 

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

 

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

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

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

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

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

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

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

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

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

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

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

　　回到我們的問題
 

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

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

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

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

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

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

　　B +樹索引
 

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

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

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

 

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

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

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

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

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

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

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

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

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

　　哈希表
 

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

　　哈希表是一種數據結構，可快速找到具有其鍵的元素。要構建哈希表，你需要定義：
 

　　你元素的關鍵
 

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

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

　　一個簡單的例子
 

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

 

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

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

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

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

　　…

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

　　假設你要獲取元素78：
 

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

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

　　它給你元素78
 

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

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

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

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

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

　　元素不存在。
 

　　搜索需要進行7次操作。
 

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

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

　　一個簡單的示例，當鍵為：
 

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

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

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

　　…
 

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

　　數組與哈希表
 

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

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