當(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ù)雜度是用來看看的算法需要多長時(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í)使用磁盤空間和少量內(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)部內(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)了解一下。
填寫下面表單即可預(yù)約申請(qǐng)免費(fèi)試聽!怕錢不夠?可先就業(yè)掙錢后再付學(xué)費(fèi)! 怕學(xué)不會(huì)?助教全程陪讀,隨時(shí)解惑!擔(dān)心就業(yè)?一地學(xué)習(xí),可推薦就業(yè)!
?2007-2022/ 5wd995.cn 北京漫動(dòng)者數(shù)字科技有限公司 備案號(hào): 京ICP備12034770號(hào) 監(jiān)督電話:010-53672995 郵箱:bjaaa@aaaedu.cc