本文主要整理了數據庫常用的算法。 我們雖然沒有必要從頭開始了解數據庫的底層算法是什么，但是了解大概原理是必要的。 其實現在很多技術都可以從經典算法中找到原型，比如Hadoop其實就是合并算法演變過來了。 這樣說來算法相當于**內功**，如果能理解了這些算法，再學其他的技術，就是**一鞭一條痕 一摑一掌血** 在了解所有算法之前，需要先了解算法復雜度，這里的算法復雜度主要指的是**時間復雜度**，是當數據量增加時運算如何增加的一種**度量**。相當于給算法一把**標尺**，這樣我們才好比較那種算法更優。同時當數據量已經到了海量的級別，我們必須盡可能的扣性能，這樣才能保證整個架構的可用性。 # 算法復雜度 這里的復雜度主要指的算法的**時間復雜度**，是當數據量增加時運算如何增加。 下圖標識了幾種常用算法的復雜度，我們可以有個直觀的認識。  面臨海量數據時 - 哈希表：O(1) - 搜索均衡樹:O(log(n)) - 搜索陣列：O(n) - 最好的排序算法O(n*log(n)) - 糟糕的排序：O(n^2) 正因為哈希表、均衡樹以及好的排序算法的時間復雜度是這個樣子，我們才會選用它。  # 常用排序算法:合并排序 ## 原理 數據庫里面最常用的排序算法莫過于**合并排序**，它主要用在**對查詢優化、數據庫聯接**上。 假設現在給了我們兩個數量為4的序列，要把他們按照從小到大的順序合并成一個8元素的序列，應該怎么做。 可以雙方都出一個元素過來比較，誰小則放到8元素序列中。比如下圖中： - 第一輪：1比2小，所以把1放到序列中。  - 第二輪：左邊的1已經放到下面去了，右邊的2還沒有動。所以要比較的是3和2，當然2小 。  - 第三輪：比較3和4  - 重復 全部過程可以看如下的Gif  總結一下： - 比較當前元素，所謂當前元素，指的是序列中的第一個。 - 小的元素放入8元素序列 - 繼續比較 仔細看上面的算法，是不是兩個序列合并之后就成了有序的呢。 不過要執行這種算法，有個必要條件是**要合并的序列必須是有序的**，這樣才可以只比較當前元素完成排序。 但是對**任意一個序列**來說不可能是完全有序的。那么此時就陷入了僵局。 那么我們可不可以這樣想，單個元素肯定是有序的吧，所以我們如果把兩個1元素的序列合并，肯定是可以用這種算法的，這樣就得到一個2元素的有序序列，如果此時還有一個2元素的有序序列，是不是可以再合并。然后是4元素序列合并，接下來是8元素序列合并。 大概是下圖這個樣子  那要怎么得到這樣1元素的序列呢？當然是拆分。8元素拆分為4，4拆分為2，拆分為1 。 好了，這個算法就完整了。 首先為了獲得1元素的序列 ，我們需要把要排序的序列進行拆分，拆分以后再進行合并。 - 拆分階段，將序列分為更小的序列 - 排序階段，把小的序列合在一起（使用合并算法）來構成更大的序列 ## 拆分階段  使用3個步驟將序列分為一元序列。步驟數量的值是 log(N) ,比如現在是 N=8, log(N)=3 為什么呢？因為拆分的每一步都是把**原序列長度除以2**，所以要執行多少步就是能把原序列除2多少次，正好就是**對數**的定義嘛。 ## 排序階段  同樣，排序階段也有log(N)個步驟，理由與上面拆分階段的相同。 而每次個步驟，所有的元素都需要動一下才能移到下一個序列里面，所以每個步驟都需要執行N次運算。 也就是說**整體成本是 N*log(N) 次運算。** 完整過程如下：  ## 合并排序的應用 如果熟悉Hadoop就知道，里面的MapReduce其實就是這種思想，**分而治之**，把一個大的任務拆分成若干小的任務，最后再各個擊破，合并即可。 可以說MapReduce就是合并算法修改后的結果，它可以運行在多處理、多服務器這種架構上罷了。  # 常用數據結構 ## 數組 說到數據庫的數據結構，我們最容易想到就是的類似于Excel那樣的數據表了。 如下圖  每一行表示一個主體，而每一列則是若干屬性或者說叫字段。 優點是非常的直觀，缺點是太過簡單，當數據量太大的時候，查找不易。 那么為了優化查找，主要有兩種方法一是構建查找樹，一是Hash表。下面我們分別介紹。 ## 樹 如果直接在數組或者陣列上進行查找，而且如果碰巧它又是有序的，自然好辦，可以使用折半、插值等方法。但是實際上，大部分的數組不大可能是有序的，所以需要在進行排序，需要消耗大量的資源和時間。 那么有沒有辦法可以插入和刪除效率還不錯，而且又比較高效的進行查找呢？ 如果我們束手無策的話，不妨從最簡單的情況入手，如果現在只有{62}，然后需要把88插入進來，就成了{62,88}，如果現在要插入58，同時還保持有序，自然需要把88往后挪一下。可以不挪嗎？ 我們知道樹這種結構，可以方便的插入和刪除，然后引伸出**二叉樹**結構了。 首先將62定為根結點，88比62大，所以做為62的右子樹，同理，58成為左子樹。  下圖就是一棵**二叉排序樹**，只要對它進行中序遍歷就可以獲得一個有序的序列  比如此時我們要查詢93，則可以像下面一樣查詢。  我們只要查到了93，就可以知道它再哪一行，然后在這一行里面去查找，范圍自然小了許多。 那么查詢的成本呢？自然就是樹的層數，即$log(N)$ 那么設想這樣一個例子。 如果數據庫中的一張表含有一個country的字段，現在要找誰在China工作。如果是陣列的話，我們需要將整張表都掃一下 但是如果把country字段中所有的元素建立一個二叉查找樹，則最多使用$log(N)$就可以查找代表China的節點，然后通過這個節點就知道有哪些行需要考慮了。 這就是**索引**，索引就是用其他的數據結構來表示某些列，**可以加速對此列的查找。** 但是新的問題又來了，查找某個值用二叉查找樹挺好的，但是如果要**查找兩個值之間的多個元素**怎么辦？使用二叉查找樹需要查找每個樹的節點才能判斷是否在兩個值之間。 于是我們引入了一種改進的樹——**B+樹** 其特征為： - 只有葉節點才保存相關表的行位置信息 - 其他節點只是用來指路的，也就是在搜索中指引到正確的節點而已。  可以看出，多了一整行用來保存信息的，此時如果要找40~100之間的值， 只需要先找到40，然后遍歷后續節點即可。 比如找了M個后續節點，則需要$M+log(N)$次即可。 但是B+節點需要保持順序，如果在數據庫里面增加或者刪除一行，則需要B+樹進行較大的變化，查入和刪除也是O(logN)復雜度的。 所以索引不能太多，它會減慢插入、更新、刪除行的操作。  ## Hash 前面說過使用Hash表進行查找，其時間復雜度只有O(1)，應該是最快的查找方法了。 不管是普通的序列還是順序表，我們都需要拿要查找的值與序列中的元素進行**比較**，那么能否只根據關鍵字key就能查找到對應的內存位置呢？ 也就是存在這樣一種函數： $$存儲位置 = f (關鍵字)$$ 這就是所謂的散列技術，這個 $f$就是散列函數，又稱為哈希函數。 > 采用散列數據將記錄存儲在一塊連續的空間里面，這塊空間就叫散列表或者哈希表。 存儲的時候，通過散列函數可以計算記錄的散列地址，并按照此地址進行存儲。 在查找的時候，也同樣使用此散列函數計算相應的地址進行查找。 也就是在哪存的就去哪找，那么**散列技術既是一種存儲技術，又是一種查找技術** **散列技術最適合的場景是查找與給定值相等的記錄。**因為不需要比較，效率大大提高。 但是如果遇到**一個key對應多條記錄**，就不適合用散列表了。比如使用關鍵字“男”去查找一個班的學生，明顯是不合適的。 同樣，散列表也不適合**范圍查找**，也就是查找40~100學號的同學。 另外，我們還會經常遇到兩個關鍵字使用散列函數卻得到同樣的地址，這樣就**沖突**了，可以可以把這個key稱為**散列函數的同義詞**，所以還需要設計方法來避免沖突。 ### 構造哈希函數 上面說過一個好的哈希函數最關鍵的是讓散列地址**均勻**的分布在存儲空間里面，這樣可以減少**沖突**，一般來說常用的散列函數都是將原來的數字按照某種規律變成另一種數字的。 - 對數字進行抽取。如果我們獲得的數字都是很長一串，也就是key的位數很大，而且里面若干位比較平均，可以將其抽取出來，進行反轉、右環位移等等讓關鍵更為平均。 也就是說這里面的散列函數實際上是抽取關鍵字的一部分。 比如手機號，就可以抽取其中幾位  - 如果不知道關鍵字的分布，位數又不大，可以進行平方，然后取中間3位做為散列地址。比如1234，平方就是1522756，取中間3位227作為散列地址。 - 上面說的都有點特殊，實際上**最常用**的是對key進行**取模**，或者說對關鍵字進行平方取中、折疊后再取模 $$f(key)=key \qquad mod \qquad p (p<=m)$$ 那么如果$p$選得不好，沖突就會比較多了。 根據經驗，如果表長為$m$，則$p$為小于或等于$m$的最小**質數**或不包含小于20質因子的合數。 ### 解決沖突 解決沖突我們只介紹一種，就是**鏈地址法** 我們可以將所有關鍵字為**同義詞**的記錄存儲在一個**單鏈表**中，這樣每個鏈表就叫**哈希桶** 所以散列表只存儲所有同義詞子表的**頭指針**，這樣無論有多少沖突 ，只需要在當前位置給**單鏈表**增加結點。  那么一個好的哈希函數應該讓哈希桶里面的元素非常少才對，這樣就可以直接在表里面查找到，時間復雜度為O(1)  # 參考 [如果有人問你數據庫的原理，叫他看這篇文章](http://blog.csdn.net/albertfly/article/details/51318995#t0)