存(cun)儲(chu)(chu)引(yin)(yin)(yin)擎(qing)是數據(ju)庫(ku)的核(he)心部(bu)分。我們在設計數據(ju)庫(ku)時，需要考慮如何(he)組織(zhi)數據(ju)來提高寫入的吞吐(tu)、降低查詢(xun)的延(yan)遲，而這些都與(yu)存(cun)儲(chu)(chu)引(yin)(yin)(yin)擎(qing)息息相關。存(cun)儲(chu)(chu)引(yin)(yin)(yin)擎(qing)數不(bu)勝(sheng)數，但(dan)核(he)心的數據(ju)結構卻萬變不(bu)離其宗。用于存(cun)儲(chu)(chu)引(yin)(yin)(yin)擎(qing)的主(zhu)流數據(ju)結構有哪些呢？
B 樹（B+ 樹）
B 樹(shu)（B+樹(shu)）是(shi)為磁盤等外存儲(chu)設備設計的(de)一種(zhong)平衡(heng)查找樹(shu)。它是(shi)一種(zhong)經典的(de)數(shu)據結構，目(mu)前主流數(shu)據庫產品大都(dou)支持 B 樹(shu)。B 樹(shu)結構可以讓系統高效地找到數(shu)據所在的(de)磁盤塊。如圖(tu)所示，節點[13,16,19]擁有的(de)子(zi)節點數(shu)目(mu)最多，因此(ci)，該 B 樹(shu)為一個 4 階 B 樹(shu)。
B 樹（B+ 樹）在查詢過程中，相(xiang)比(bi)平衡二叉樹，降(jiang)低(di)了樹高(gao)，從(cong)而能夠(gou)減少 IO 次數(shu)，因(yin)此更適用于硬盤。但寫入過程中卻(que)可能導致(zhi)節點的分(fen)裂，產生大量隨機。IO，導致(zhi)寫入性能的降(jiang)低(di)。
像 SQLite , MySQL, PostgreSQL 等數據庫都使用了B/B+ 樹。
LSM 樹
LSM 樹(shu)(Log-Structured-Merge Tree)并不像 B+ 樹(shu)、紅(hong)黑樹(shu)一(yi)樣(yang)是一(yi)個(ge)嚴格的(de)樹(shu)狀數(shu)(shu)據(ju)結(jie)構(gou)，它其(qi)實是一(yi)種存(cun)儲結(jie)構(gou)，目前 HBase, LevelDB, RocksDB 這些 NoSQL 數(shu)(shu)據(ju)庫(ku)中，新(xin)一(yi)代關系(xi)型數(shu)(shu)據(ju)庫(ku) TiDB, CockroachDB 也建立在基于 LSM 樹(shu)的(de) KV 存(cun)儲上。下圖展示(shi)了 LSM 樹(shu)的(de)核心思想。
LSM 樹(shu)充分利用了(le)硬盤順序(xu) IO 速度(du)遠超隨(sui)機 IO 的特點(dian)，避免了(le)寫入過程中(zhong)節點(dian)分裂(lie)帶來(lai)的大量 IO，從(cong)而能(neng)(neng)夠發揮更強(qiang)大的寫入性(xing)能(neng)(neng)。但與此同時(shi)，LSM 樹(shu)在查詢(xun)過程中(zhong)卻可能(neng)(neng)需(xu)要(yao)遍歷多級文件，導致查詢(xun)性(xing)能(neng)(neng)的下降。
基于(yu) B 樹（B+ 樹）或(huo) LSM 樹的(de)(de)通用存(cun)(cun)(cun)儲引(yin)(yin)(yin)擎(qing)(qing)，久(jiu)經考驗能夠(gou)良好地(di)支持關(guan)系(xi)型(xing)或(huo)非關(guan)系(xi)型(xing)的(de)(de)數(shu)據(ju)(ju)(ju)庫。但時序(xu)數(shu)據(ju)(ju)(ju)庫如 TDengine、InfluxDB 等都選(xuan)擇了(le)針(zhen)對時序(xu)數(shu)據(ju)(ju)(ju)的(de)(de)特點，量身(shen)定做存(cun)(cun)(cun)儲引(yin)(yin)(yin)擎(qing)(qing)，從(cong)(cong)而在(zai)性(xing)能上(shang)遠超基于(yu)通用存(cun)(cun)(cun)儲引(yin)(yin)(yin)擎(qing)(qing)建(jian)立的(de)(de)數(shu)據(ju)(ju)(ju)庫。InfluxDB 探索了(le)基于(yu) LevelDB、BoltDB、RocksDB 等等方案(an)，但最終選(xuan)擇了(le)構建(jian)自己的(de)(de)存(cun)(cun)(cun)儲引(yin)(yin)(yin)擎(qing)(qing)。而 TDengine 從(cong)(cong)一開始就發(fa)現通用存(cun)(cun)(cun)儲引(yin)(yin)(yin)擎(qing)(qing)難以充分(fen)發(fa)揮時序(xu)數(shu)據(ju)(ju)(ju)的(de)(de)典(dian)型(xing)特征，為(wei)了(le)將(jiang)性(xing)能發(fa)揮到極致，自研了(le)用于(yu)時序(xu)數(shu)據(ju)(ju)(ju)的(de)(de)存(cun)(cun)(cun)儲引(yin)(yin)(yin)擎(qing)(qing)。
那么(me)，時序(xu)數(shu)據的典(dian)型特征是什(shen)么(me)呢？對于時序(xu)數(shu)據來說(shuo)，為什(shen)么(me)通用的 KV 存儲引擎不夠優秀？如何(he)針對時序(xu)數(shu)據，打造(zao)專用的存儲引擎，從(cong)而盡可能地提高讀寫吞吐、降低延遲呢？
2021 年(nian) 12 月 16 日（周四）20:00-21:00，我們(men)邀請到(dao)了 TDengine Database 工程師劉繼聰，和大家聊一聊數據庫的經(jing)典算法和數據結構。
劉繼聰，畢業于復旦大學，計算機科學與技術專業，曾就職于阿里云，現濤思數據存儲引擎研發工程師。
他分享的主要內容：
- 時序數據的典型特征
- 經典數據結構 B Tree（B+ Tree）
- 經典數據結構 LSM Tree
- 如何充分利用時序數據的特點，打造專用存儲引擎
歡(huan)迎(ying)大家(jia)掃描下方二(er)維碼，關(guan)注 TDengine Database 的視頻號，觀看每周(zhou)的微課堂以及直播(bo)活(huo)動(dong)。
