哈希索引:
key -> offset 通過(guò)文件存儲(chǔ),為了避免磁盤(pán)空間耗盡,采用合并與壓縮段文件,保留最新的鍵值.
局限: 文件需要放進(jìn)內(nèi)存,范圍查詢效率不高
SSTable(排序字符串表):
每個(gè)文件里的鍵值對(duì)有序,壓縮時(shí)可以采用歸并合并.將合并的段生成稀疏的索引,可以進(jìn)行范圍查詢.
如何保證文件里鍵值對(duì)有序?可以首先在內(nèi)存中采用樹(shù)結(jié)構(gòu)(紅黑樹(shù)或者平衡樹(shù))寫(xiě)入(也被稱為memtable),當(dāng)?shù)竭_(dá)一定閾值時(shí),作為SSTable寫(xiě)入磁盤(pán).為了避免斷電導(dǎo)致內(nèi)存中數(shù)據(jù)的丟失,可以在磁盤(pán)上保存一個(gè)日志,每次寫(xiě)先寫(xiě)入日志,日志可以用以崩潰后恢復(fù)數(shù)據(jù).
LSM
基于合并和壓縮排序文件原理的存儲(chǔ)引擎通常被稱為LSM(Log Structured Merge Tree)存儲(chǔ)引擎.由于數(shù)據(jù)按排序順序存儲(chǔ)，因此可以高效地執(zhí)行范圍查詢（掃描所有高于某些最小值和最高值的所有鍵），并且因?yàn)榇疟P(pán)寫(xiě)入是連續(xù)的，所以LSM樹(shù)可以支持非常高的寫(xiě)入吞吐量。
局限: 查詢不存在的數(shù)據(jù)時(shí),需要不斷訪問(wèn)以前舊的段文件,才能確定不存在.
解決方案:可以采用BloomFilter進(jìn)行過(guò)濾.
Lucene的倒排索引采用的是類似的方式進(jìn)行存儲(chǔ).
B樹(shù)
B樹(shù)將數(shù)據(jù)庫(kù)分解成固定大小的塊或頁(yè)面，傳統(tǒng)上大小為4KB（有時(shí)會(huì)更大），并且一次只能讀取或?qū)懭胍粋€(gè)頁(yè)面。這種設(shè)計(jì)更接近于底層硬件，因?yàn)榇疟P(pán)也被安排在固定大小的塊中。
基本底層寫(xiě)操作,不同于日志結(jié)構(gòu)索引的追加模式,是用新數(shù)據(jù)覆蓋磁盤(pán)上的頁(yè)面.因此通?？梢圆捎?code>WAL(預(yù)寫(xiě)日志,僅追加)來(lái)避免數(shù)據(jù)庫(kù)崩潰時(shí)數(shù)據(jù)的丟失.同時(shí)也需要使用輕量鎖來(lái)避免并發(fā)時(shí)數(shù)據(jù)不一致的問(wèn)題.
通常LSM樹(shù)的寫(xiě)入速度更快，而B樹(shù)的讀取速度更快.
LSM和B樹(shù)的對(duì)比
B樹(shù)缺點(diǎn):部分字節(jié)更新也需要更新整個(gè)節(jié)點(diǎn),即整個(gè)內(nèi)存頁(yè)面.存儲(chǔ)引擎寫(xiě)入磁盤(pán)的次數(shù)越多，可用磁盤(pán)帶寬內(nèi)的每秒寫(xiě)入次數(shù)越少。LSM的順序?qū)懭氡入S機(jī)寫(xiě)入快很多,同時(shí)B樹(shù)容易產(chǎn)生更多的碎片空間.
LSM缺點(diǎn):壓縮有時(shí)會(huì)干擾正在進(jìn)行的讀寫(xiě)操作--磁盤(pán)資源有限，所以很容易發(fā)生請(qǐng)求需要等待磁盤(pán)完成昂貴的壓縮操作.而壓縮率太低時(shí),會(huì)導(dǎo)致磁盤(pán)的文件越來(lái)越多,讀性能下降.B樹(shù)因?yàn)?code>key不重復(fù),也能提供很好的事務(wù)隔離功能.
其他索引
- 將其他索引存儲(chǔ)在主鍵索引中(二級(jí)索引),例如聚集索引.或者將數(shù)據(jù)引用存儲(chǔ)在主鍵索引中,例如非聚集索引.這種方式可以加快讀取速度,但是需要額外存儲(chǔ)空間以及寫(xiě)開(kāi)銷.
- 多列索引,將多個(gè)字段合成一個(gè)鍵.
- 全文搜索和模糊索引
內(nèi)存數(shù)據(jù)庫(kù)
以上提到的數(shù)據(jù)結(jié)構(gòu)都需要考慮到對(duì)磁盤(pán)的影響.內(nèi)存數(shù)據(jù)庫(kù)的發(fā)展隨著RAM價(jià)格的降低而變得可行.
反直覺(jué)的是，內(nèi)存數(shù)據(jù)庫(kù)的性能優(yōu)勢(shì)并不是因?yàn)樗鼈儾恍枰獜拇疟P(pán)讀取的事實(shí)。即使是基于磁盤(pán)的存儲(chǔ)引擎也可能永遠(yuǎn)不需要從磁盤(pán)讀取，因?yàn)椴僮飨到y(tǒng)緩存最近在內(nèi)存中使用了磁盤(pán)塊。相反，它們更快的原因在于省去了將內(nèi)存數(shù)據(jù)結(jié)構(gòu)編碼為磁盤(pán)數(shù)據(jù)結(jié)構(gòu)的開(kāi)銷。除去性能外,內(nèi)存數(shù)據(jù)庫(kù)的另一個(gè)有趣的領(lǐng)域是提供難以用基于磁盤(pán)的索引實(shí)現(xiàn)的數(shù)據(jù)模型.
OLTP和OLAP
OLTP:在線事務(wù)處理,影響業(yè)務(wù)運(yùn)作,要求高可用和低延遲.前述索引算法更適合用在此.
OLAP:在線分析處理,利用數(shù)據(jù)倉(cāng)庫(kù)(從OLTP中提取數(shù)據(jù),轉(zhuǎn)換成適合分析的模式，清理并加載到數(shù)據(jù)倉(cāng)庫(kù)中).
分析模式
在大多數(shù)OLTP數(shù)據(jù)庫(kù)中，存儲(chǔ)都是以面向行的方式進(jìn)行布局的：表格的一行中的所有值都相鄰存儲(chǔ)。雖然建立了索引,但是仍然需要將行數(shù)據(jù)加載進(jìn)內(nèi)存然后進(jìn)行篩選.面向列存儲(chǔ)應(yīng)運(yùn)而生:將來(lái)自每一列的所有值存儲(chǔ)在一起。如果每個(gè)列存儲(chǔ)在一個(gè)單獨(dú)的文件中，查詢只需要讀取和解析查詢中使用的那些列.將所有列同一行的值組裝在一起,也可以重新組裝成一行.
因?yàn)橥涣斜容^容易有相同的值, 面向列存儲(chǔ)可以很好進(jìn)行壓縮:可以使用位圖,稀疏的情況下可以進(jìn)行游程編碼.
對(duì)于專門(mén)的分析查詢，列式存儲(chǔ)可以顯著加快查詢速度.
