數(shù)據(jù)庫(kù)中的幾種數(shù)據(jù)結(jié)構(gòu)
陣列
- 二維陣列是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。一個(gè)表可以看做是一個(gè)陣列：
| |column 0|column 1|column 2|
|--|--|--|--|--|
|row 0|fy|4|CHN|
|row 1|ame|1|CHN|
|row 2|maybe|2|CHN|
|row 3|charles|3|CHN|
|row 4|xNova|5|CHN|
|...|..|...|..|
|row n|..|..|..|..
這個(gè)二維陣列是帶有行與列的表：
- 每個(gè)行代表一個(gè)主體
- 列用來(lái)描述主體的特征
- 每個(gè)列保存某一種類(lèi)型對(duì)數(shù)據(jù)
當(dāng)要查找特定的值時(shí)，這種數(shù)據(jù)結(jié)構(gòu)需要對(duì)每一行的值進(jìn)行判斷娶牌。這會(huì)造成N次運(yùn)算衅胀，復(fù)雜度是O(N)
樹(shù)和數(shù)據(jù)庫(kù)索引
- 二叉查找樹(shù)/二叉搜索樹(shù)：
一種帶有特殊屬性的二叉樹(shù)稚新，每個(gè)節(jié)點(diǎn)的值滿(mǎn)足：- 比保存在左子樹(shù)的任何鍵值都要大
-
比保存在右子樹(shù)的任何鍵值都要小
image
這個(gè)樹(shù)有N=15個(gè)元素。如果要找208概龄，會(huì)從根節(jié)點(diǎn)開(kāi)始尋找：
- 136 < 208 --> 去找節(jié)點(diǎn)136的右子樹(shù)
- 298 > 208 --> 去找節(jié)點(diǎn)398的左子樹(shù)
- 50>208 --> 去找節(jié)點(diǎn)250的左子樹(shù)
- 200<208 --> 去找節(jié)點(diǎn)200的右子樹(shù)丐谋。但是 200 沒(méi)有右子樹(shù)芍碧，值不存在（因?yàn)槿绻嬖冢鼤?huì)在 200 的右子樹(shù)）
一次查詢(xún)的成本基本就是樹(shù)內(nèi)部的層數(shù)号俐，這個(gè)成本是log(N)
B+樹(shù)索引
查找一個(gè)特定的值時(shí)泌豆，二叉查找樹(shù)挺好用的，但是當(dāng)我們需要查找某一個(gè)范圍之間的多個(gè)元素時(shí)吏饿，我們還是要對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行遍歷践美，以判斷它是否處于那兩個(gè)值之間,這樣你必須讀取整個(gè)樹(shù)，成本是O(N)找岖。
為了解決這個(gè)問(wèn)題陨倡，現(xiàn)代數(shù)據(jù)庫(kù)使用了一種修訂版的樹(shù)---B+樹(shù):
- 只有最底層的葉子節(jié)點(diǎn)才保存信息
-
其它節(jié)點(diǎn)只是用來(lái)指引到正確的節(jié)點(diǎn)
image
可以看到節(jié)點(diǎn)多了兩倍，同時(shí)最底層的節(jié)點(diǎn)是跟后續(xù)節(jié)點(diǎn)相連的许布。
用這個(gè)B+樹(shù)兴革，如果要找某個(gè)范圍內(nèi)(例如40到100之間)的值：
- 找到40（49不存在則找40之后最貼近的值），就像在二叉查找樹(shù)中的那樣蜜唾。
- 向后遍歷節(jié)點(diǎn)杂曲，直到找到100
找到了 M 個(gè)后續(xù)節(jié)點(diǎn)，樹(shù)總共有 N 個(gè)節(jié)點(diǎn)袁余。對(duì)指定節(jié)點(diǎn)的搜索成本是 log(N)擎勘，跟上一個(gè)樹(shù)相同。但是當(dāng)你找到這個(gè)節(jié)點(diǎn)之后颖榜，你可以通過(guò)后續(xù)節(jié)點(diǎn)的連接得到 M 個(gè)后續(xù)節(jié)點(diǎn)棚饵，這需要 M 次運(yùn)算煤裙。那么這次搜索只消耗了 M+log(N) 次運(yùn)算
這種方式方便查找，但是需要在節(jié)點(diǎn)之間保持順序噪漾，所以在插入和刪除數(shù)據(jù)時(shí)硼砰，為了維護(hù)這個(gè)B+樹(shù)，需要以每個(gè)索引O(log(N))的代價(jià)來(lái)更新索引欣硼。這樣的話(huà)就會(huì)減慢插入/更新/刪除的操作题翰。
哈希表
這個(gè)數(shù)據(jù)結(jié)構(gòu)被數(shù)據(jù)庫(kù)用來(lái)保存一些內(nèi)部的東西（比如鎖表或者緩沖池）
哈希表可以通過(guò)關(guān)鍵字來(lái)快速找到一個(gè)元素，為了構(gòu)建一個(gè)hash表诈胜，你需要定義：
- 元素的關(guān)鍵字
- 哈希函數(shù)： 根據(jù)元素的關(guān)鍵字給出對(duì)應(yīng)的hash值
- 比較函數(shù)：通過(guò)hash值在桶中找到需要的元素
例子：
對(duì)于這個(gè)存儲(chǔ)數(shù)字的hash表豹障，我們定義：
- 元素關(guān)鍵字： 數(shù)字本身
- 哈希函數(shù)： 對(duì)10取模
def hash(num): return num % 10 - 比價(jià)函數(shù)：判斷兩個(gè)整數(shù)是否相等
尋找元素78：
- hash(78) = 8
- 查找hash桶8，找到第一個(gè)元素78,
- 返回78
搜索耗費(fèi)了2次運(yùn)算
找元素 59：
哈希表計(jì)算 59 的哈希碼焦匈，等于9沼填。
查找哈希桶 9，第一個(gè)找到的元素是 99括授。因?yàn)?99 不等于 59， 那么 99 不是正確的元素岩饼。
用同樣的邏輯荚虚，查找第二個(gè)元素(9)，第三個(gè)(79)籍茧，……版述，最后一個(gè)(29)。
元素不存在寞冯。
搜索耗費(fèi)了 7 次運(yùn)算渴析。
從列子可以看出，根據(jù)查找的值吮龄，每次尋找的成本(計(jì)算次數(shù))可能并不相同俭茧。
一個(gè)好的hash函數(shù)會(huì)將所有的元素盡可能地均勻分配在hash桶中，這樣會(huì)盡可能地減少查找次數(shù)漓帚。
如果有了好的哈希函數(shù)母债，在哈希表里搜索的時(shí)間復(fù)雜度是 O(1)。
陣列 vs 哈希表
- 一個(gè)哈希表可以只裝載一半到內(nèi)存尝抖，剩下的哈希桶可以留在硬盤(pán)上毡们。
- 用陣列的話(huà)，你需要一個(gè)連續(xù)內(nèi)存空間昧辽。如果你加載一個(gè)大表衙熔，很難分配足夠的連續(xù)內(nèi)存空間。
- 用哈希表的話(huà)搅荞，你可以選擇你要的關(guān)鍵字（比如红氯，一個(gè)人的國(guó)家和姓氏）框咙。
