存儲(chǔ)引擎是數(shù)據(jù)庫的核心部分。我們在設(shè)計(jì)數(shù)據(jù)庫時(shí)，需要考慮如何組織數(shù)據(jù)來提高寫入的吞吐、降低查詢的延遲，而這些都與存儲(chǔ)引擎息息相關(guān)。存儲(chǔ)引擎數(shù)不勝數(shù)，但核心的數(shù)據(jù)結(jié)構(gòu)卻萬變不離其宗。用于存儲(chǔ)引擎的主流數(shù)據(jù)結(jié)構(gòu)有哪些呢？

B 樹（B+ 樹）

B 樹（B+樹）是為磁盤等外存儲(chǔ)設(shè)備設(shè)計(jì)的一種平衡查找樹。它是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，目前主流數(shù)據(jù)庫產(chǎn)品大都支持 B 樹。B 樹結(jié)構(gòu)可以讓系統(tǒng)高效地找到數(shù)據(jù)所在的磁盤塊。如圖所示，節(jié)點(diǎn)[13,16,19]擁有的子節(jié)點(diǎn)數(shù)目最多，因此，該 B 樹為一個(gè) 4 階 B 樹。

B 樹（B+ 樹）在查詢過程中，相比平衡二叉樹，降低了樹高，從而能夠減少 IO 次數(shù)，因此更適用于硬盤。但寫入過程中卻可能導(dǎo)致節(jié)點(diǎn)的分裂，產(chǎn)生大量隨機(jī)。IO，導(dǎo)致寫入性能的降低。

像 SQLite , MySQL,  PostgreSQL 等數(shù)據(jù)庫都使用了B/B+ 樹。

LSM 樹

LSM 樹(Log-Structured-Merge Tree)并不像 B+ 樹、紅黑樹一樣是一個(gè)嚴(yán)格的樹狀數(shù)據(jù)結(jié)構(gòu)，它其實(shí)是一種存儲(chǔ)結(jié)構(gòu)，目前 HBase, LevelDB, RocksDB 這些 NoSQL 數(shù)據(jù)庫中，新一代關(guān)系型數(shù)據(jù)庫 TiDB, CockroachDB 也建立在基于 LSM 樹的 KV 存儲(chǔ)上。下圖展示了 LSM 樹的核心思想。

LSM 樹充分利用了硬盤順序 IO 速度遠(yuǎn)超隨機(jī) IO 的特點(diǎn)，避免了寫入過程中節(jié)點(diǎn)分裂帶來的大量 IO，從而能夠發(fā)揮更強(qiáng)大的寫入性能。但與此同時(shí)，LSM 樹在查詢過程中卻可能需要遍歷多級(jí)文件，導(dǎo)致查詢性能的下降。

基于 B 樹（B+ 樹）或 LSM 樹的通用存儲(chǔ)引擎，久經(jīng)考驗(yàn)?zāi)軌蛄己玫刂С株P(guān)系型或非關(guān)系型的數(shù)據(jù)庫。但時(shí)序數(shù)據(jù)庫如 TDengine、InfluxDB 等都選擇了針對(duì)時(shí)序數(shù)據(jù)的特點(diǎn)，量身定做存儲(chǔ)引擎，從而在性能上遠(yuǎn)超基于通用存儲(chǔ)引擎建立的數(shù)據(jù)庫。InfluxDB 探索了基于 LevelDB、BoltDB、RocksDB 等等方案，但最終選擇了構(gòu)建自己的存儲(chǔ)引擎。而 TDengine 從一開始就發(fā)現(xiàn)通用存儲(chǔ)引擎難以充分發(fā)揮時(shí)序數(shù)據(jù)的典型特征，為了將性能發(fā)揮到極致，自研了用于時(shí)序數(shù)據(jù)的存儲(chǔ)引擎。

那么，時(shí)序數(shù)據(jù)的典型特征是什么呢？對(duì)于時(shí)序數(shù)據(jù)來說，為什么通用的 KV 存儲(chǔ)引擎不夠優(yōu)秀？如何針對(duì)時(shí)序數(shù)據(jù)，打造專用的存儲(chǔ)引擎，從而盡可能地提高讀寫吞吐、降低延遲呢？

2021 年 12 月 16 日（周四）20:00-21:00，我們邀請到了 TDengine Database 工程師劉繼聰，和大家聊一聊數(shù)據(jù)庫的經(jīng)典算法和數(shù)據(jù)結(jié)構(gòu)。

劉繼聰，畢業(yè)于復(fù)旦大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)，曾就職于阿里云，現(xiàn)濤思數(shù)據(jù)存儲(chǔ)引擎研發(fā)工程師。

他分享的主要內(nèi)容：

1. 時(shí)序數(shù)據(jù)的典型特征
2. 經(jīng)典數(shù)據(jù)結(jié)構(gòu) B Tree（B+ Tree）
3. 經(jīng)典數(shù)據(jù)結(jié)構(gòu) LSM Tree
4. 如何充分利用時(shí)序數(shù)據(jù)的特點(diǎn)，打造專用存儲(chǔ)引擎

歡迎大家掃描下方二維碼，關(guān)注 TDengine Database 的視頻號(hào)，觀看每周的微課堂以及直播活動(dòng)。