3.1 數(shù)據(jù)庫核心：數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)庫只需做兩件事情：向它插入數(shù)據(jù)肘，它就保存數(shù)據(jù)：之后查詢時(shí)，它應(yīng)該返回那些數(shù)據(jù)。

本章我們主要從數(shù)據(jù)庫的角度再來探討同樣的問題，即如何存儲輸入的數(shù)據(jù)，井在收到查詢請求時(shí)，怎樣重新找到數(shù)據(jù).

了解存儲引擎的底層機(jī)制。

存儲引擎用于大家比較熟悉的兩種數(shù)據(jù)庫，即傳統(tǒng)的關(guān)系數(shù)據(jù)庫和大多數(shù)所謂的NoSQL數(shù)據(jù)庫。我們將研究兩個(gè)存儲引擎家族，即日志結(jié)構(gòu)的存儲引擎和面向頁的存儲引擎，比如B-tree 。

一、數(shù)據(jù)結(jié)構(gòu)

世界上最簡單的數(shù)據(jù)庫，它由兩個(gè)Bash函數(shù)實(shí)現(xiàn)：

echo ” $1,$2”> database

grep “^$1,” database| sed -e "s/^$1", //" | tail -n 1

這兩個(gè)函數(shù)實(shí)現(xiàn)了一個(gè)key-value存儲。當(dāng)調(diào)用 db_set key value ，它將在數(shù)據(jù)庫中保存你所輸入的 key和value.

調(diào)用 db_get key ，它會查找與輸入 key相關(guān)聯(lián)的最新值并返回。

它底層的存儲格式其實(shí)非常簡單：一個(gè)純文本文件。其中每行包含一個(gè)key-value對，用逗號分隔（大致像一個(gè)csv文件，忽略轉(zhuǎn)義問題）。每次調(diào)用db set 即追加新內(nèi)容到文件末尾，因此，如果多次更新某個(gè)鍵，舊版本的值不會被覆蓋，而是需要查看文件中最后一次出現(xiàn)的鍵來找到最新的值（因此在db_get中使用tail-n1）。

對于簡單的情況，追加到文件尾部方式通常足夠高效。與db_set相似，許多數(shù)據(jù)庫內(nèi)部都使用日志（ lo g ），日志是一個(gè)僅支持追加式更新的數(shù)據(jù)文件。

雖然真正的數(shù)據(jù)庫有很多更為復(fù)雜問題需要考慮（例如并發(fā)控制、回收磁盤空間以控制日志文件大小、處理錯(cuò)誤和部分完成寫記錄等），但是基本的原理是相同的。

每次想查找一個(gè)鍵，db_get必須從頭到尾掃描整個(gè)數(shù)據(jù)庫文件來查找鍵的出現(xiàn)位置。在算能術(shù)語中，查找的開銷是 O(n ）。為了高效地查找數(shù)據(jù)庫中特定鍵的值，需要新的數(shù)據(jù)結(jié)構(gòu)：索引。背后的基本想怯都是保留一些額外的元數(shù)據(jù)，這些元數(shù)據(jù)作為路標(biāo)，幫助定位想要的數(shù)據(jù)。

索引是基于原始數(shù)據(jù)報(bào)生而來的額外數(shù)據(jù)結(jié)構(gòu)。很多數(shù)據(jù)庫允許單獨(dú)添加和刪除索引，而不影響數(shù)據(jù)庫的內(nèi)容，它只會影響查詢性能。維護(hù)額外的結(jié)構(gòu)勢必會引入開銷，特別是在新數(shù)據(jù)寫入時(shí)。對于寫人，它很難超過簡單地追加文件方式的性能，因?yàn)槟且呀?jīng)是最簡單的寫操作了。由于每次寫數(shù)據(jù)時(shí)，需要更新索引，因此任何類型的索引通常都會降低寫的速度。

涉及存儲系統(tǒng)中重要的權(quán)衡設(shè)計(jì)：適當(dāng)?shù)乃饕梢约铀僮x取查詢，但每個(gè)索引者ll會減慢寫速度。

1.1 哈希索引

以鍵－值數(shù)據(jù)的索引開始。key-value類型并不是唯一可以索引的數(shù)據(jù)，但它隨處可見，而且是其他更復(fù)雜索引的基礎(chǔ)構(gòu)造模塊。key - value存儲與大 多數(shù)編程語言所內(nèi)置的字典結(jié)構(gòu)非常相似，通常采用 hash map （或者 hash table ，哈希表）來實(shí)現(xiàn)。

既然已經(jīng)有了內(nèi)存數(shù)據(jù)結(jié)構(gòu)的 hash map ，為什么不用它們在磁盤上直接索引數(shù)據(jù)呢？

假設(shè)數(shù)據(jù)存儲全部采用追加式文件組成，如之前的例子所示 。 那么最簡單的索引策略就是 ： 保存內(nèi)存中的 hash map ，把每個(gè)鍵一一映射到數(shù)據(jù)文件中特定的字節(jié)偏移量 ，這樣就可以找到每個(gè)值的位置。

每當(dāng)在文件中追加新的key-value對，更新hash map來反映剛剛寫入數(shù)據(jù)的偏移量 （包括插入新的鍵和更新已有的鍵）。 當(dāng)查找某個(gè)值時(shí)，使用 hash map來找到文件中的偏移量 ，即存儲位置，然后讀取其內(nèi)容.Bitcask(Riak中的默認(rèn)存儲引擎）所采用的核心做法。

只追加到一個(gè)文件，那么如何避免最終用盡磁盤空間？

一個(gè)好的解決方案是將日志分解成一定大小的段，當(dāng)文件達(dá)到一定大小時(shí)就關(guān)閉它，井將后續(xù)寫入到新的段文件中。然后可以在這些段上執(zhí)行壓縮，如圖 3-2所示。壓縮意味著在日志中丟棄重復(fù)的鍵，并且只保留每個(gè)鍵最近的更新。

每個(gè)段現(xiàn)在都有自己的內(nèi)存哈希表 ，將鍵映射到文件的偏移量。 為了找到鍵的值，首先檢查最新的段的 h as h map ；如果鍵不存在，檢查第二最新的段，以此類推。由于合并過程可以維持較少的段數(shù)量 ，因此查找通常不需要檢查很多 hash map

在真正地實(shí)現(xiàn)中有以下重要問題：文件格式、刪除記錄、崩憤恢復(fù)、部分寫入的記錄、并發(fā)控制

追加的日志乍看起來似乎很油費(fèi)空間：為什么不原地更新文件，用新值覆蓋舊值？但是，結(jié)果證明追加式的設(shè)計(jì)非常不錯(cuò)，主要原因有以下幾個(gè)：追加和分段合并主要是順序?qū)?，它通常比隨機(jī)寫入快得多，特別是在旋轉(zhuǎn)式磁性硬盤上。在某種程度上，順序?qū)懭朐诨陂W存的固態(tài)硬盤（ solidstatedrives,SSD ）上也是適合的；如果段文件是追加的或不可變的，并發(fā)和崩憤恢復(fù)要簡單得多；合并舊段可以避免隨著時(shí)間的推移數(shù)據(jù)文件出現(xiàn)碎片化的問題。

===SSTable&LSM-Tree===

現(xiàn)在簡單地改變段文件的格式：要求key-value對的順序按鍵排序。乍一看，這個(gè)要求似乎打破了順序?qū)懸?guī)則，這種格式稱為排序字符串表，或簡稱為SSTable.以上描述的算怯本質(zhì)上正是LevelDBlGJ和RocksDB[?J所使用的，類似的存儲引擎還被用于Cassa n dra矛口HBase[SJ ，這兩個(gè)引擎都受到 Google的B i gtab l e論文［9］的啟發(fā)（它引入了 SSTa bl e和內(nèi)存表這兩個(gè)術(shù)語）

存儲引擎的基本工作流程如下：

1.當(dāng)寫入時(shí)，將其添加到內(nèi)存中的平衡樹數(shù)據(jù)結(jié)構(gòu)中（｛列如紅黑樹）。這個(gè)內(nèi)存中的樹有時(shí)被稱為內(nèi)存表。

2.當(dāng)內(nèi)存表大于某個(gè)鬧值（通常為幾兆字節(jié)）時(shí)，將其作為 SSTable文件寫入磁盤。由于樹已經(jīng)維護(hù)了按鍵排序的 key-value對，寫磁盤可以比較高效。新的SSTable文件成為數(shù)據(jù)庫的最新部分。當(dāng) SSTable寫磁盤的同時(shí)，寫入可以繼續(xù)添加到一個(gè)新的內(nèi)存表實(shí)例。

3.為了處理讀請求，首先嘗試在內(nèi)存表中查找鍵，然后是最新的磁盤段文件，接下來是次新的磁盤段文件，以此類推，直到找到目標(biāo)（或?yàn)榭眨?/p>

4.后臺進(jìn)程周期性地執(zhí)行段合并與壓縮過程，以合并多個(gè)段文件，并丟棄那些已被覆蓋或刪除的值。

這個(gè)索引結(jié)構(gòu) 由 Patrick 0 ’Nei l等人以日志結(jié)構(gòu)的合井樹（ Log-Structured MergeTree ，或LSM-Tree) [IOJ命名，它建立在更早期的日志結(jié)構(gòu)文件系統(tǒng)之上 l 門 l 。因此，基于合井和壓縮排序文件原理的存儲引擎通常都被稱為LSM存儲引擎。但LS M-t ree 的基本思想（保存在后臺合井的一系列SSTable ）卻足夠簡單有效

===B-tree===

最廣泛使用的索引結(jié)構(gòu)是另一種不同的： B-tree,像SSTable一樣， B-tree保留按鍵排序的ke）叫 alue對，這樣可以實(shí)現(xiàn)高效的key-value查找和區(qū)間查詢。但相似僅此而已：B-tree本質(zhì)上具有非常不同的設(shè)計(jì)理念。

日志結(jié)構(gòu)索引將數(shù)據(jù)庫分解為可變大小的段，通常大小為幾兆字節(jié)或更大，并且始終按順序?qū)懭攵?。相比之下?B-tree將數(shù)據(jù)庫分解成固定大小的塊或頁，傳統(tǒng)上大小為4KB（有時(shí)更大），頁是內(nèi)部讀／寫的最小單元。這種設(shè)計(jì)更接近底層硬件，因?yàn)榇疟P也是以固定大小的塊排列。

每個(gè)頁面都可以使用地址或位置進(jìn)行標(biāo)識，這樣可以讓一個(gè)頁面引用另一個(gè)頁面，類似指針，不過是指向磁盤地址，而不是內(nèi)存?？梢允褂眠@些頁面引用來構(gòu)造一個(gè)樹狀頁面.

某一頁被指定為 B-tree的根：每當(dāng)查找索引中的一個(gè)鍵時(shí)，總是從這里開始。該頁面包含若干個(gè)鍵和對子頁的引用。每個(gè)孩子都負(fù)責(zé)一個(gè)連續(xù)范圍內(nèi)的鍵，相鄰引用之間的鍵可以指示這些范圍之間的邊界。

B-tree中一個(gè)頁所包含的子頁引用數(shù)量稱為分支因子。例如，在圖 3-6 中，分支因子為6 。在實(shí)際中，分支因素取決于存儲頁面引用和范圍邊界所需的空間總量，通常為幾百個(gè)。

該算怯確保樹保持平衡：具有n個(gè)鍵的B-tree總是具有O(logn ） 的深度。大多數(shù)數(shù)據(jù)庫可以適合3~4層的B-tree ，因此不需要遍歷非常深的頁面層次即可找到所需的頁（分支因子為500的4KB頁的四級樹可以存儲高達(dá)256TB ）。

===使B-tree可靠

B-tree底層的基本寫操作是使用新數(shù)據(jù)覆蓋磁盤上的舊頁。它假設(shè)覆蓋不會改變頁的磁盤存儲位置，也就是說，當(dāng)頁被覆蓋時(shí)，對該頁的所有引用保持不變。這與日志結(jié)構(gòu)索引（如LSM-tree ）形成鮮明對比， LSM-tree僅追加更新文件（并最終刪除過時(shí)的文件），但不會修改文件。

Btree索引必須至少寫兩次數(shù)據(jù)：一次寫入預(yù)寫日志，－次寫入樹的頁本身（還可能發(fā)生頁分裂）。即使該頁中只有幾個(gè)字節(jié)更改，也必須承受寫整個(gè)頁的開銷。

MySQL InnoDB存儲引擎中，表的主鍵始終是聚集索引，二級索引引用主鍵。

迄今為止討論的索引只將一個(gè)鍵映射到一個(gè)值。如果需要同時(shí)查詢表的多個(gè)列（或文檔中的多個(gè)字段），那么這是不夠的。

最常見的多列索引類型稱為級聯(lián)索引，它通過將一列追加到另一列，將幾個(gè)字段簡單地組合成一個(gè)鍵（索引的定義指定宇段連接的順序）文章來源地址http://www.zghlxwxcb.cn/news/detail-821180.html

到了這里，關(guān)于數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計(jì)--3.1 數(shù)據(jù)庫核心：數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！