思考 1：固態(tài)硬盤的普及，是否影響到了存儲引擎的設(shè)計(jì)？

Reference: Let’s Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems

DBMSs have always dealt with the trade-off between volatile and non-volatile storage devices. In order to retain data after a loss of power, the DBMS must write that data to a non-volatile device, such as a SSD or HDD. Such devices only support slow, bulk data transfers as blocks. Contrast this with volatile DRAM, where a DBMS can quickly read and write a single byte from these devices, but all data is lost once power is lost.

在設(shè)計(jì)數(shù)據(jù)庫系統(tǒng)的時(shí)候，通常要在“易失性存儲”和“非易失性存儲”之間做權(quán)衡。為了在掉電之后仍然能夠保存數(shù)據(jù)，人們將內(nèi)存數(shù)據(jù)寫入持久化存儲中，然后用 Write-ahead log 來保持內(nèi)存和磁盤刷寫一致。在早期，持久化存儲通常是一些 HDD 設(shè)備，相比 DRAM，它們讀寫緩慢，且數(shù)據(jù)傳輸粒度通常比較大。

為了平衡內(nèi)存和磁盤的讀寫速度差異，人們做出了很多努力。比如在磁盤上維護(hù)有序結(jié)構(gòu)時(shí)采用 B-tree （將樹的高度降下來，減少磁盤 I/O 次數(shù)。3~4 層的 B-tree 已經(jīng)可以適合大多數(shù)數(shù)據(jù)庫，degree 為 500 的 4 KB 頁的四級樹可以存儲高達(dá) 256 TB）。比如在寫磁盤時(shí)，為了減少直接的原地更新（In-place Updates）帶來的效率問題，采用一些“懶”方案（例如 Copy-on-Write Updates，Log-structured Updates）。另外，在 SSD 上，固件內(nèi)部使用 Log-structured 算法將“隨機(jī)寫入”轉(zhuǎn)換為底層存儲芯片上的“順序?qū)懭搿?#xff0c;也是為了加快寫磁盤的速度。

近年來，固態(tài)硬盤的普及，一定程度上減少了內(nèi)存與磁盤之間的讀寫速度差異，它是否會對原有的存儲引擎的設(shè)計(jì)產(chǎn)生影響？

以及，未來如果非易失性存儲普及，又會對存儲引擎的設(shè)計(jì)產(chǎn)生哪些影響？

---

思考 2：B+ tree 的選型原因

Reference: Skip Lists: A Probabilistic Alternative to Balanced Trees

完整說一下吧，無論 B/B+，RB，AVL，還是 skiplist，在最開始都實(shí)際上面臨同一個(gè)問題，在數(shù)據(jù)有序的情況下，都會成為一個(gè)鏈表。最后導(dǎo)致查詢復(fù)雜度 O(N)， B/B+/RB/AVL 的采用的策略是 self adjust ，就是所謂的 rebalance。跳表的策略是做 randomize，他假定了一個(gè)概率 P，有一個(gè)“退化”描述，即，當(dāng) P =1/2 時(shí)，有百分之50%的數(shù)據(jù)在第一層，百分之25的數(shù)據(jù)在第二層，百分之12.5的數(shù)據(jù)在第三層 etc. 通過這樣讓數(shù)據(jù)分層明顯，避免全局退化。所以在這種情況下 skiplist 在期望復(fù)雜度上做到了查詢 O(logn)（實(shí)際上這也是一個(gè)統(tǒng)計(jì)上的期望計(jì)算）。skiplist 的優(yōu)勢也很明顯，實(shí)現(xiàn)簡單，性能不錯，但是缺陷也很明顯，在內(nèi)存的情況下，由于其是個(gè) randomize 的數(shù)據(jù)結(jié)構(gòu)，導(dǎo)致其 CPU cache的利用率并不是很明顯，所以可能要考慮這塊的場合還是需要去用 RB 這種數(shù)據(jù)結(jié)構(gòu)。在磁盤 I/O 的情況下，由于其 randomize 的特性，導(dǎo)致你沒法去做 Sequential reading ，而 randomize reading 對于磁盤來說一直是個(gè)大問題。在這個(gè)問題上 RB 這種數(shù)據(jù)結(jié)構(gòu)實(shí)際上面臨的問題也是一樣的，所以 B/B+ 樹用適當(dāng)?shù)臄?shù)據(jù)聚合的方式，將樹的高度降下來，方面我們做 page read，避免 randomize reading

穩(wěn)定這話實(shí)際上也沒說錯，，因?yàn)?skiplist 畢竟是個(gè) randomize 的數(shù)據(jù)結(jié)構(gòu)，他復(fù)雜度取還是概率上的描述23333（并不保障嚴(yán)格的平衡性 lol

總結(jié)

以上是生活随笔為你收集整理的思考：固态硬盘的普及，是否影响到了存储引擎的设计？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。