在大規(guī)模數(shù)據(jù)存儲(chǔ)中，實(shí)現(xiàn)索引查詢也是一個(gè)重難點(diǎn)，由于樹(shù)節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量有限，因此就會(huì)導(dǎo)致在應(yīng)用二叉搜索樹(shù)結(jié)構(gòu)時(shí)，會(huì)因?yàn)闃?shù)深度過(guò)大而造成磁盤(pán) I/O 讀寫(xiě)過(guò)于頻繁，進(jìn)而導(dǎo)致查詢效率低下。那不同的索引區(qū)別在哪里？時(shí)序數(shù)據(jù)庫(kù)（Time Series Database）又應(yīng)該如何選擇索引方式實(shí)現(xiàn)科學(xué)的數(shù)據(jù)結(jié)構(gòu)？本文將以 TDengine 為例為大家展開(kāi)分析。

B樹(shù)、B+樹(shù)、LSM樹(shù)

B樹(shù)即平衡多路查找樹(shù)，也稱為B-樹(shù)。通常我們描述一棵B樹(shù)時(shí)需要指定它的階數(shù)，階數(shù)表示一個(gè)節(jié)點(diǎn)最多有多少個(gè)孩子節(jié)點(diǎn)，一般用字母 m 表示階數(shù)。當(dāng) m 取 2 時(shí)，就是我們常見(jiàn)的二叉搜索樹(shù)。B樹(shù)是一種自平衡樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，能對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行 O(log n) 的時(shí)間復(fù)雜度進(jìn)行查找、插入和刪除，一般較多用在存儲(chǔ)系統(tǒng)上，比如數(shù)據(jù)庫(kù)或文件系統(tǒng)。

B+樹(shù)是B樹(shù)的一種變體，也屬于平衡多路查找樹(shù)，大體結(jié)構(gòu)與B樹(shù)相同，包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)，多用于數(shù)據(jù)庫(kù)和操作系統(tǒng)的文件系統(tǒng)中，由于B+樹(shù)內(nèi)部節(jié)點(diǎn)不保存數(shù)據(jù)，所以能在內(nèi)存中存放更多索引，增加緩存命中率。另外因?yàn)槿~子節(jié)點(diǎn)相連遍歷操作很方便，而且數(shù)據(jù)也具有順序性，便于區(qū)間查找。

B+樹(shù)每個(gè)非葉子節(jié)點(diǎn)存放的元素只用于索引作用，所有數(shù)據(jù)保存在葉子節(jié)點(diǎn)中。一個(gè) m 階的B+樹(shù)規(guī)定了：

1. 有 k 個(gè)子樹(shù)的中間節(jié)點(diǎn)包含有 k 個(gè)元素（B樹(shù)中是 k-1 個(gè)元素），每個(gè)元素不保存數(shù)據(jù)，只用來(lái)索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)；
2. 所有的葉子節(jié)點(diǎn)中包含了全部元素的信息，及指向包含這些元素記錄的指針，且葉子節(jié)點(diǎn)本身以關(guān)鍵字的大小自小而大的順序鏈接；
3. 所有的中間節(jié)點(diǎn)元素都同時(shí)存在于子節(jié)點(diǎn)，在子節(jié)點(diǎn)元素中是最大（或最?。┰?。

因?yàn)榉侨~子節(jié)點(diǎn)中存放的元素不存放數(shù)據(jù)，所以每一層可以容納更多的元素，即磁盤(pán)中的每一頁(yè)可以存放更多元素，這樣在查找時(shí)，磁盤(pán) IO 的次數(shù)也會(huì)減少。另外，B+樹(shù)的查找要更穩(wěn)定一些，因?yàn)槠渌械臄?shù)據(jù)都在葉子節(jié)點(diǎn)，而每個(gè)葉子節(jié)點(diǎn)通過(guò)指針構(gòu)成了一種鏈表結(jié)構(gòu)，因此遍歷數(shù)據(jù)也會(huì)簡(jiǎn)單很多。

B+樹(shù)的插入和刪除與B樹(shù)類(lèi)似，它們的區(qū)別主要有以下幾點(diǎn)：

• B+樹(shù)內(nèi)節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，所有數(shù)據(jù)存儲(chǔ)在葉節(jié)點(diǎn)(非葉子節(jié)點(diǎn)并不存儲(chǔ)真正的 data)，也因此導(dǎo)致查詢時(shí)間復(fù)雜度固定為 log（n）。而B(niǎo)樹(shù)可以在內(nèi)部節(jié)點(diǎn)同時(shí)存儲(chǔ)鍵和值，因此，我們把頻繁訪問(wèn)的數(shù)據(jù)放在靠近根節(jié)點(diǎn)的地方將會(huì)大大提高熱點(diǎn)數(shù)據(jù)的查詢效率，這種特性使得B樹(shù)在特定數(shù)據(jù)重復(fù)多次查詢的場(chǎng)景中更加高效。B樹(shù)查詢時(shí)間復(fù)雜度不固定，與 key 在樹(shù)中的位置有關(guān)，最好的情況下時(shí)間復(fù)雜度為 O(1)。
• B+樹(shù)的葉子節(jié)點(diǎn)有一條鏈相連，而B(niǎo)樹(shù)的葉子節(jié)點(diǎn)各自獨(dú)立。B+樹(shù)葉節(jié)點(diǎn)兩兩相連可大大增加區(qū)間訪問(wèn)性，可使用在一定范圍內(nèi)查詢等，而B(niǎo)樹(shù)每個(gè)節(jié)點(diǎn) key 和 data 在一起，則無(wú)法區(qū)間查找。
• B+樹(shù)更適合外部存儲(chǔ)，由于內(nèi)節(jié)點(diǎn)無(wú) data 域，每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確。B樹(shù)節(jié)點(diǎn)內(nèi)部每個(gè) key 都帶著 data 域，B+樹(shù)節(jié)點(diǎn)只存儲(chǔ) key 的副本，真實(shí)的 key 和 data 域都在葉子節(jié)點(diǎn)存儲(chǔ)，而磁盤(pán)是分 block 的，一次磁盤(pán) IO 會(huì)讀取若干個(gè) block，具體和操作系統(tǒng)有關(guān)，那么由于磁盤(pán) IO 數(shù)據(jù)大小是固定的，在一次 IO 中，單個(gè)元素越小量就越大。這就意味著B(niǎo)+樹(shù)單次磁盤(pán) IO 的信息量大于B樹(shù)，從這點(diǎn)來(lái)看B+樹(shù)相對(duì)B樹(shù)磁盤(pán) IO 次數(shù)少。

B樹(shù)最大的好處在于它對(duì)數(shù)據(jù)持續(xù)高漲讀性能的處理上，即使數(shù)據(jù)量級(jí)增大，它的讀也沒(méi)有放大，其奧秘在于對(duì)數(shù)據(jù)進(jìn)行終極持久存儲(chǔ)時(shí)，B樹(shù)是以有規(guī)律的數(shù)據(jù)結(jié)構(gòu)保存在硬盤(pán)上的。這樣隨著數(shù)據(jù)越來(lái)越大，它依然保持著有序有規(guī)律的特性，即便面對(duì)成千上萬(wàn)的讀操作，都可以遵循條件運(yùn)行，減少或避免讀放大的行為。

B樹(shù)/B+樹(shù)在數(shù)據(jù)庫(kù)存儲(chǔ)中應(yīng)用非常廣泛，它能對(duì)數(shù)據(jù)進(jìn)行有效地查找，避免了讀放大。此外，B樹(shù)和LSM經(jīng)常一起使用。數(shù)據(jù)庫(kù)底層可以分為B樹(shù)機(jī)制、LSM機(jī)制，兩種機(jī)制各有各的優(yōu)點(diǎn)和缺點(diǎn)。與B樹(shù)機(jī)制截然相反，LSM機(jī)制則是減少避免了寫(xiě)放大。LSM機(jī)制充分利用了內(nèi)存，在內(nèi)存里面開(kāi)辟了一個(gè)空間，寫(xiě)數(shù)據(jù)優(yōu)先往內(nèi)存里放，寫(xiě)進(jìn)去直接返回用戶成功，而不是像B樹(shù)那樣寫(xiě)一個(gè)，要找出誰(shuí)更大誰(shuí)更小，只要內(nèi)存足夠，就直接往內(nèi)存里面填就好，當(dāng)內(nèi)存達(dá)到一定的閾值后就會(huì)將內(nèi)存中的數(shù)據(jù)以批量、順序的方式一次寫(xiě)入硬盤(pán)上，內(nèi)存則重置清零再服務(wù)新的寫(xiě)要求。

傳統(tǒng)數(shù)據(jù)庫(kù) MySQL、Oracle 使用的都是B樹(shù)機(jī)制，而 TiDB、OceanBase 一類(lèi)的數(shù)據(jù)庫(kù)使用的則是優(yōu)化后的 LSM 機(jī)制。TDengine 使用的是B樹(shù) + LSM機(jī)制的方式，B樹(shù)存儲(chǔ)的是元數(shù)據(jù)（主要是時(shí)間戳+指標(biāo)數(shù)據(jù)），LSM機(jī)制存儲(chǔ)的是具體的數(shù)據(jù)，元數(shù)據(jù)以有序表結(jié)構(gòu)方式進(jìn)行存儲(chǔ)，而具體數(shù)據(jù)則是追加的方式寫(xiě)入，這樣既避免了讀放大又避免了寫(xiě)放大。

時(shí)序數(shù)據(jù)庫(kù)如何構(gòu)建索引？

以 TDengine 為例，針對(duì)時(shí)序數(shù)據(jù)的特點(diǎn)，我們專門(mén)研發(fā)了 TSDB 存儲(chǔ)和查詢引擎。在 TDengine 2.0 中，TSDB 存儲(chǔ)了一個(gè) Vnode 中表的元數(shù)據(jù)以及時(shí)序數(shù)據(jù)（采集信息），后者以行和列兩種結(jié)構(gòu)存儲(chǔ)（2.0開(kāi)始引入行存儲(chǔ)），時(shí)序數(shù)據(jù)在內(nèi)存中以 SkipList 方式進(jìn)行索引，在硬盤(pán)中以 Block Range INdex（BRIN）方式進(jìn)行索引。

TSDB 啟動(dòng)時(shí)會(huì)事先分配一個(gè)BUFFER POOL 作為寫(xiě)入緩沖（默認(rèn)16MB*6=96MB），緩沖區(qū)塊大小和個(gè)數(shù)可配，區(qū)塊個(gè)數(shù)可修改。元數(shù)據(jù)和時(shí)序數(shù)據(jù)從緩沖塊申請(qǐng)寫(xiě)入空間，寫(xiě)入引擎向 BUFFER POOL 申請(qǐng)緩沖區(qū)塊，寫(xiě)滿的緩沖區(qū)塊占總緩沖區(qū)塊的三分之一時(shí)觸發(fā)落盤(pán)操作。落盤(pán)時(shí)，緩沖區(qū)塊中的數(shù)據(jù)寫(xiě)入到 META 等文件中，落盤(pán)結(jié)束后緩沖區(qū)塊歸還給 BUFFER POOL，形成循環(huán)機(jī)制。查詢時(shí)，對(duì) MEM、IMEM 以及數(shù)據(jù)文件中的數(shù)據(jù)進(jìn)行合并查詢。如下圖所示：

這種設(shè)計(jì)的優(yōu)勢(shì)在于：

• 對(duì)于單表按照時(shí)間段的查詢效率很高
• 內(nèi)存行存儲(chǔ)充分利用內(nèi)存，緩存更多數(shù)據(jù)
• 文件中列存儲(chǔ)充分發(fā)揮壓縮算法優(yōu)勢(shì)
• 避免 LSM 過(guò)多的文件合并
• 標(biāo)簽數(shù)據(jù)與時(shí)序數(shù)據(jù)分離存儲(chǔ)

但也存在一些不足之處。在元數(shù)據(jù)存儲(chǔ)這塊，此前的 1.0 和 2.0 采取的都是比較簡(jiǎn)單的存儲(chǔ)機(jī)制，即全內(nèi)存存儲(chǔ)，數(shù)據(jù)在內(nèi)存中以 hash 表的方式存儲(chǔ)，并輔以跳表索引，在 hash 表中有一個(gè) Backup Storage Engine，它可以保證數(shù)據(jù)的持久化。該方式的優(yōu)點(diǎn)是全內(nèi)存、效率高，但缺點(diǎn)也很明顯，當(dāng)啟動(dòng)時(shí)，這部分?jǐn)?shù)據(jù)就會(huì)全部加載到內(nèi)存之中，不僅內(nèi)存占用無(wú)法精準(zhǔn)控制，還會(huì)導(dǎo)致開(kāi)機(jī)啟動(dòng)時(shí)間長(zhǎng)。

因此，為了解決這些問(wèn)題，我們?cè)?TDengine 3.0 中研發(fā)了 TDB（一個(gè) B+ 樹(shù)格式的的存儲(chǔ)引擎），來(lái)存儲(chǔ)元數(shù)據(jù)及元數(shù)據(jù)索引。TDB 的 B+ 樹(shù)存儲(chǔ)適合元數(shù)據(jù)讀多寫(xiě)少的場(chǎng)景，能夠支持百億時(shí)間線的存儲(chǔ)，避免了元數(shù)據(jù)全內(nèi)存存儲(chǔ)以及長(zhǎng)時(shí)間的加載，同時(shí)解決了在有限內(nèi)存下，表數(shù)量膨脹的問(wèn)題。對(duì)于 TDB 是如何實(shí)現(xiàn)的，大家如果感興趣，可以去 GitHub 上看一下源代碼。

TDB 的優(yōu)點(diǎn)是內(nèi)存可以精確控制，開(kāi)機(jī)啟動(dòng)速度快，在有限內(nèi)存下也可以存儲(chǔ)海量的元數(shù)據(jù)，此外如果 TDB 外加 Cache 輔助的話，在一定程度上可以提供接近全內(nèi)存 hash 表的查詢速度。事實(shí)上，關(guān)于 TDengine 3.0 存儲(chǔ)引擎的更新可以分為三大塊，首先是 TQ，基于 WAL 的消息隊(duì)列；其次是 META，基于 TDB 的元數(shù)據(jù)存儲(chǔ)引擎；第三是 TSDB，用來(lái)存儲(chǔ)時(shí)序數(shù)據(jù)的類(lèi) LSM 存儲(chǔ)引擎（TSDB SE）。關(guān)于 TQ 和 TSDB 的具體更新感興趣的小伙伴可以進(jìn)入《支持消息隊(duì)列和流式計(jì)算背后，TDengine 3.0 存儲(chǔ)引擎的優(yōu)化與升級(jí)》一文查看。

結(jié)語(yǔ)

在對(duì)時(shí)序數(shù)據(jù)特點(diǎn)進(jìn)行挖掘和總結(jié)的前提下，TDengine 設(shè)計(jì)了存儲(chǔ)模型和查詢模型，摸索到了最適合進(jìn)行時(shí)序數(shù)據(jù)處理的索引結(jié)構(gòu)，正因?yàn)檫@些創(chuàng)新設(shè)計(jì)，TDengine 才表現(xiàn)出強(qiáng)勁的存儲(chǔ)性能和查詢性能。如果你也面臨著時(shí)序數(shù)據(jù)處理難題或想要和我們的核心研發(fā)人員進(jìn)行交流和溝通，歡迎添加小T（tdengine），和一眾志同道合的開(kāi)發(fā)者共同進(jìn)步。