??此篇記錄數(shù)據(jù)庫的文件存儲結(jié)構(gòu)及索引相關(guān)的知識。
1.最簡單原始的結(jié)構(gòu):追加式日志文件存儲
??這個(gè)應(yīng)該是最簡單無腦存儲結(jié)構(gòu)，每一行都是一個(gè)key-value對——key當(dāng)然就是物理主鍵——每次有新的寫入則直接在文件尾部追加寫入（不管是insert還是update），同時(shí)檢索是也是從尾部開始檢索（為了避免查詢update過后的數(shù)據(jù)拿到舊的），而刪除時(shí)則對對應(yīng)行的數(shù)據(jù)增加一個(gè)墓碑。
??為了保證檢索的效率，可以根據(jù)數(shù)據(jù)表所定義的結(jié)構(gòu)而規(guī)定每一行的長度都是固定的，則檢索時(shí)指針只需要移動固定的位置，而不需要進(jìn)行動態(tài)的計(jì)算。
??如下兩個(gè)圖，下圖數(shù)據(jù)行不定長，需要一個(gè)*號作為每行的分隔符，確定一行數(shù)據(jù)需要單個(gè)字符去掃描以確定一行完整的數(shù)據(jù)：
??數(shù)據(jù)行長度固定，則不需要分隔符，且可以進(jìn)行跳躍式掃描，同時(shí)節(jié)省大量的邏輯運(yùn)算。
??追加式寫的存儲效率很高，因?yàn)榕c磁盤的物理特征有關(guān)系，順序往下寫恰巧對應(yīng)磁頭的順序移動；而如果使用覆蓋式update，硬盤需要進(jìn)行隨機(jī)寫入的話反而會影響效率，算是一種空間換時(shí)間的做法。
??但是追加式寫會帶來文件無限制變大，冗余數(shù)據(jù)過多的問題，為了解決這兩個(gè)問題，需要將文件分段存儲，規(guī)定每個(gè)分段文件的大小，滿了之后則順序創(chuàng)建新的存儲文件；另外考慮到數(shù)據(jù)大量更新后占據(jù)過多的冗余空間，所以需要定時(shí)（或定量，根據(jù)段文件的數(shù)量考慮等）對段文件進(jìn)行合并壓縮，合并時(shí)相同的key只保留最近寫入的行，而丟棄所有相同key的舊行以及被墓碑（刪除標(biāo)記）所標(biāo)記的行。
2.最基礎(chǔ)的索引結(jié)構(gòu):哈希索引
??哈希索引即最基礎(chǔ)的key-value索引，效率很高，但索引只能再內(nèi)存中維護(hù)，如果放入磁盤中維護(hù)會因?yàn)樾枰罅康碾S機(jī)IO而影響效率，同時(shí)服務(wù)重啟是需要全表掃描重新維護(hù)索引，如果表體積太大則會影響開機(jī)時(shí)間。
3.日志式存儲升級版，排序字符串表SSTable（LSM-TREE日志結(jié)構(gòu)的合并樹）
??SSTable其實(shí)也是日志追加式存儲，只是在寫文件的時(shí)候是對key進(jìn)行排序后寫入的。
??①按序?qū)懭霂淼囊粋€(gè)好處是，合并段的時(shí)候更加高效，不需要整段讀入內(nèi)存，只需要為需要合并的兩個(gè)或多個(gè)段各分配一個(gè)指針按行順序掃描，每一輪將多個(gè)指針中最小且最新的一個(gè)取出，寫入到新的段文件尾部。需要注意的是需要對多個(gè)相同key的輸入端篩選出最新的寫入，合并過程參考下圖。
??②檢索特定的key時(shí)效率更高，不需要掃描全部文件，將每個(gè)段記錄自己key的開始與結(jié)束，然后直接通過二分法檢索到對應(yīng)的段文件，然后同樣在相應(yīng)區(qū)間的段文件使用二分法檢索，時(shí)間復(fù)雜度僅為O(log2 N)。
??值得注意的是，寫入請求是無序的，如果想要持久化后有序，則寫磁盤之前需要在內(nèi)存中建立一個(gè)緩沖塊，在某段時(shí)間內(nèi)的寫入維護(hù)在內(nèi)存中的一個(gè)有序的數(shù)據(jù)集合（常用紅黑樹或AVL樹），達(dá)到一定的大小后再整塊寫入磁盤；為了避免這塊緩沖區(qū)丟失，會在寫內(nèi)存同時(shí)，寫入到磁盤中單獨(dú)維護(hù)的一塊持久化緩存區(qū)按請求順序維護(hù)，作為恢復(fù)的備份。
P.S.目前使用上述存儲算法作為引擎的有LevelDB和RocksDB。
3.B-trees存儲/索引結(jié)構(gòu)
??B-tree(平衡樹)是目前最廣泛的數(shù)據(jù)庫存儲結(jié)構(gòu)。
??與平時(shí)在一般場景編程時(shí)一個(gè)數(shù)據(jù)對象作為一個(gè)節(jié)點(diǎn)不一樣的是，在數(shù)據(jù)庫使用B-tree作為索引時(shí)是使用一個(gè)一個(gè)小型的數(shù)據(jù)集作為一個(gè)節(jié)點(diǎn)的，通常稱為一頁或一塊（平時(shí)與他人討論時(shí)大多習(xí)慣叫頁）。一頁內(nèi)通常也是一個(gè)有序的list，list中除了存儲數(shù)據(jù)行之外，還會存儲子節(jié)點(diǎn)的指針（磁盤指針而不是一般說的內(nèi)存指針），當(dāng)一頁寫滿后，會根據(jù)情況將本頁分裂成2個(gè)新的頁，或?qū)⑿碌臄?shù)據(jù)行寫入本頁的某個(gè)子節(jié)點(diǎn)頁中。
??由于該樹屬于一個(gè)平衡樹，因此總是能保持很高的檢索效率，大多數(shù)數(shù)據(jù)庫會保持樹維持3~4層的高度，來保證效率。當(dāng)分支因子為500的4KB也的四級樹，可以存儲高達(dá)256TB的數(shù)據(jù)。
可靠性保證
??B-tree存儲結(jié)構(gòu)與LSM-tree不一樣的另一個(gè)地方是，B-tree在寫入時(shí)會對定位到的頁進(jìn)行原地覆蓋式寫入，因此也需要不一樣的意外預(yù)防手段。
??1）由于寫數(shù)據(jù)頁的時(shí)候有可能因?yàn)楦鞣N原因?qū)е卤罎?，所以通常會在真正寫入頁之間將數(shù)據(jù)寫到【預(yù)寫日志（write-ahead log,WAL）】,用于作為系統(tǒng)在數(shù)據(jù)庫崩潰后恢復(fù)的依據(jù)。
??2）另外由于是原地更新頁，所以并發(fā)寫時(shí)需要對也加鎖。
其他一些有意思的優(yōu)化
??1）有部分?jǐn)?shù)據(jù)庫不對頁使用覆蓋寫（因此也無需WAL預(yù)防崩潰），而是使用寫時(shí)覆蓋方案。修改的頁會在新的位置創(chuàng)建寫入，并修改指針指向新的頁（詳細(xì)得看后面了）。
??2）保存鍵的縮略信息以節(jié)省空間（大概是用了什么方法壓縮）。
B-tree與LSM-tree的一些對比
??簡單從算法上來理解的話，普遍認(rèn)為B-tree讀取更快，而LSM-寫入更快，這是基于它們的實(shí)現(xiàn)上的特點(diǎn)而推理的：
1）對于B-tree來說，每次寫入需要寫WAL之后覆蓋寫整個(gè)頁，因此會造成較大的寫放大；盡管LSM-tree也有類似于WAL的備份日志，但LSM-tree每次僅寫一行，開銷比B-tree小得多，同時(shí)也因?yàn)樗捻樞驅(qū)懛洗疟P硬件的運(yùn)作方式。
2）對于LSM-tree來說，盡管后臺需要周期性地進(jìn)行排序與合并，但讀取時(shí)也可能需要在多個(gè)不同的數(shù)據(jù)塊進(jìn)行檢索。而B-tree只需要在樹上進(jìn)行檢索即可讀取到需要的信息。
3）另一方面，盡管LSM-tree可以承受更高的寫入吞吐量，但由于其需要周期性合并的特性，合并段的時(shí)候需要與寫入的請求競爭磁盤的寫入帶寬，加入在高負(fù)載的情況下，寫入請求被分配了更高的優(yōu)先級，長時(shí)間的高負(fù)載則會造成磁盤上大量的段無法被分配帶寬進(jìn)行讀取合并，最終有耗盡磁盤空間的風(fēng)險(xiǎn)。
