??此篇記錄數(shù)據(jù)庫的文件存儲(chǔ)結(jié)構(gòu)及索引相關(guān)的知識(shí)雌芽。
1.最簡(jiǎn)單原始的結(jié)構(gòu):追加式日志文件存儲(chǔ)
??這個(gè)應(yīng)該是最簡(jiǎn)單無腦存儲(chǔ)結(jié)構(gòu)啊央，每一行都是一個(gè)key-value對(duì)——key當(dāng)然就是物理主鍵——每次有新的寫入則直接在文件尾部追加寫入（不管是insert還是update）河哑，同時(shí)檢索是也是從尾部開始檢索（為了避免查詢update過后的數(shù)據(jù)拿到舊的）咏连，而刪除時(shí)則對(duì)對(duì)應(yīng)行的數(shù)據(jù)增加一個(gè)墓碑搭幻。
??為了保證檢索的效率姆吭，可以根據(jù)數(shù)據(jù)表所定義的結(jié)構(gòu)而規(guī)定每一行的長(zhǎng)度都是固定的已艰，則檢索時(shí)指針只需要移動(dòng)固定的位置痊末，而不需要進(jìn)行動(dòng)態(tài)的計(jì)算。
??如下兩個(gè)圖哩掺，下圖數(shù)據(jù)行不定長(zhǎng)凿叠，需要一個(gè)*號(hào)作為每行的分隔符，確定一行數(shù)據(jù)需要單個(gè)字符去掃描以確定一行完整的數(shù)據(jù)：
??數(shù)據(jù)行長(zhǎng)度固定嚼吞，則不需要分隔符盒件，且可以進(jìn)行跳躍式掃描，同時(shí)節(jié)省大量的邏輯運(yùn)算誊薄。
??追加式寫的存儲(chǔ)效率很高履恩，因?yàn)榕c磁盤的物理特征有關(guān)系，順序往下寫恰巧對(duì)應(yīng)磁頭的順序移動(dòng)呢蔫；而如果使用覆蓋式update切心，硬盤需要進(jìn)行隨機(jī)寫入的話反而會(huì)影響效率飒筑，算是一種空間換時(shí)間的做法。
??但是追加式寫會(huì)帶來文件無限制變大绽昏，冗余數(shù)據(jù)過多的問題协屡，為了解決這兩個(gè)問題，需要將文件分段存儲(chǔ)全谤，規(guī)定每個(gè)分段文件的大小肤晓，滿了之后則順序創(chuàng)建新的存儲(chǔ)文件；另外考慮到數(shù)據(jù)大量更新后占據(jù)過多的冗余空間认然，所以需要定時(shí)（或定量补憾，根據(jù)段文件的數(shù)量考慮等）對(duì)段文件進(jìn)行合并壓縮，合并時(shí)相同的key只保留最近寫入的行卷员，而丟棄所有相同key的舊行以及被墓碑（刪除標(biāo)記）所標(biāo)記的行盈匾。
2.最基礎(chǔ)的索引結(jié)構(gòu):哈希索引
??哈希索引即最基礎(chǔ)的key-value索引，效率很高毕骡，但索引只能再內(nèi)存中維護(hù)削饵，如果放入磁盤中維護(hù)會(huì)因?yàn)樾枰罅康碾S機(jī)IO而影響效率，同時(shí)服務(wù)重啟是需要全表掃描重新維護(hù)索引未巫，如果表體積太大則會(huì)影響開機(jī)時(shí)間窿撬。
3.日志式存儲(chǔ)升級(jí)版，排序字符串表SSTable（LSM-TREE日志結(jié)構(gòu)的合并樹）
??SSTable其實(shí)也是日志追加式存儲(chǔ)叙凡，只是在寫文件的時(shí)候是對(duì)key進(jìn)行排序后寫入的劈伴。
??①按序?qū)懭霂淼囊粋€(gè)好處是，合并段的時(shí)候更加高效狭姨，不需要整段讀入內(nèi)存宰啦，只需要為需要合并的兩個(gè)或多個(gè)段各分配一個(gè)指針按行順序掃描，每一輪將多個(gè)指針中最小且最新的一個(gè)取出饼拍，寫入到新的段文件尾部赡模。需要注意的是需要對(duì)多個(gè)相同key的輸入端篩選出最新的寫入，合并過程參考下圖师抄。
??②檢索特定的key時(shí)效率更高漓柑，不需要掃描全部文件，將每個(gè)段記錄自己key的開始與結(jié)束叨吮，然后直接通過二分法檢索到對(duì)應(yīng)的段文件辆布，然后同樣在相應(yīng)區(qū)間的段文件使用二分法檢索，時(shí)間復(fù)雜度僅為O(log2 N)茶鉴。
??值得注意的是锋玲，寫入請(qǐng)求是無序的，如果想要持久化后有序涵叮，則寫磁盤之前需要在內(nèi)存中建立一個(gè)緩沖塊惭蹂，在某段時(shí)間內(nèi)的寫入維護(hù)在內(nèi)存中的一個(gè)有序的數(shù)據(jù)集合（常用紅黑樹或AVL樹）伞插，達(dá)到一定的大小后再整塊寫入磁盤；為了避免這塊緩沖區(qū)丟失盾碗，會(huì)在寫內(nèi)存同時(shí)媚污，寫入到磁盤中單獨(dú)維護(hù)的一塊持久化緩存區(qū)按請(qǐng)求順序維護(hù)，作為恢復(fù)的備份廷雅。
P.S.目前使用上述存儲(chǔ)算法作為引擎的有LevelDB和RocksDB耗美。
3.B-trees存儲(chǔ)/索引結(jié)構(gòu)
??B-tree(平衡樹)是目前最廣泛的數(shù)據(jù)庫存儲(chǔ)結(jié)構(gòu)。
??與平時(shí)在一般場(chǎng)景編程時(shí)一個(gè)數(shù)據(jù)對(duì)象作為一個(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中除了存儲(chǔ)數(shù)據(jù)行之外甸私，還會(huì)存儲(chǔ)子節(jié)點(diǎn)的指針（磁盤指針而不是一般說的內(nèi)存指針），當(dāng)一頁寫滿后飞傀，會(huì)根據(jù)情況將本頁分裂成2個(gè)新的頁，或?qū)⑿碌臄?shù)據(jù)行寫入本頁的某個(gè)子節(jié)點(diǎn)頁中诬烹。
??由于該樹屬于一個(gè)平衡樹砸烦，因此總是能保持很高的檢索效率，大多數(shù)數(shù)據(jù)庫會(huì)保持樹維持3~4層的高度绞吁，來保證效率幢痘。當(dāng)分支因子為500的4KB也的四級(jí)樹，可以存儲(chǔ)高達(dá)256TB的數(shù)據(jù)家破。
可靠性保證
??B-tree存儲(chǔ)結(jié)構(gòu)與LSM-tree不一樣的另一個(gè)地方是颜说，B-tree在寫入時(shí)會(huì)對(duì)定位到的頁進(jìn)行原地覆蓋式寫入，因此也需要不一樣的意外預(yù)防手段汰聋。
??1）由于寫數(shù)據(jù)頁的時(shí)候有可能因?yàn)楦鞣N原因?qū)е卤罎⒚欧啵酝ǔ?huì)在真正寫入頁之間將數(shù)據(jù)寫到【預(yù)寫日志（write-ahead log,WAL）】,用于作為系統(tǒng)在數(shù)據(jù)庫崩潰后恢復(fù)的依據(jù)。
??2）另外由于是原地更新頁烹困，所以并發(fā)寫時(shí)需要對(duì)也加鎖玄妈。
其他一些有意思的優(yōu)化
??1）有部分?jǐn)?shù)據(jù)庫不對(duì)頁使用覆蓋寫（因此也無需WAL預(yù)防崩潰），而是使用寫時(shí)覆蓋方案髓梅。修改的頁會(huì)在新的位置創(chuàng)建寫入拟蜻，并修改指針指向新的頁（詳細(xì)得看后面了）。
??2）保存鍵的縮略信息以節(jié)省空間（大概是用了什么方法壓縮）枯饿。
B-tree與LSM-tree的一些對(duì)比
??簡(jiǎn)單從算法上來理解的話酝锅，普遍認(rèn)為B-tree讀取更快，而LSM-寫入更快奢方，這是基于它們的實(shí)現(xiàn)上的特點(diǎn)而推理的：
1）對(duì)于B-tree來說搔扁，每次寫入需要寫WAL之后覆蓋寫整個(gè)頁爸舒，因此會(huì)造成較大的寫放大；盡管LSM-tree也有類似于WAL的備份日志阁谆，但LSM-tree每次僅寫一行碳抄，開銷比B-tree小得多，同時(shí)也因?yàn)樗捻樞驅(qū)懛洗疟P硬件的運(yùn)作方式场绿。
2）對(duì)于LSM-tree來說剖效，盡管后臺(tái)需要周期性地進(jìn)行排序與合并，但讀取時(shí)也可能需要在多個(gè)不同的數(shù)據(jù)塊進(jìn)行檢索焰盗。而B-tree只需要在樹上進(jìn)行檢索即可讀取到需要的信息璧尸。
3）另一方面，盡管LSM-tree可以承受更高的寫入吞吐量熬拒，但由于其需要周期性合并的特性爷光，合并段的時(shí)候需要與寫入的請(qǐng)求競(jìng)爭(zhēng)磁盤的寫入帶寬，加入在高負(fù)載的情況下澎粟，寫入請(qǐng)求被分配了更高的優(yōu)先級(jí)蛀序，長(zhǎng)時(shí)間的高負(fù)載則會(huì)造成磁盤上大量的段無法被分配帶寬進(jìn)行讀取合并，最終有耗盡磁盤空間的風(fēng)險(xiǎn)活烙。
