在大規模數據存儲中，實現索引查詢也是一個重難點，由于樹節點存儲的元素數量有限，因此就會導致在應用二叉搜索樹結構時，會因為樹深度過大而造成磁盤 I/O 讀寫過于頻繁，進而導致查詢效率低下。那不同的索引區別在哪里？時序數據庫（Time Series Database）又應該如何選擇索引方式實現科學的數據結構？本文將以 TDengine 為例為大家展開分析。
B樹、B+樹、LSM樹
B樹即平衡多路查找樹，也稱為B-樹。通常我們描述一棵B樹時需要指定它的階數，階數表示一個節點最多有多少個孩子節點，一般用字母 m 表示階數。當 m 取 2 時，就是我們常見的二叉搜索樹。B樹是一種自平衡樹狀數據結構，能對存儲的數據進行 O(log n) 的時間復雜度進行查找、插入和刪除，一般較多用在存儲系統上，比如數據庫或文件系統。
B+樹是B樹的一種變體，也屬于平衡多路查找樹，大體結構與B樹相同，包含根節點、內部節點和葉子節點，多用于數據庫和操作系統的文件系統中，由于B+樹內部節點不保存數據，所以能在內存中存放更多索引，增加緩存命中率。另外因為葉子節點相連遍歷操作很方便，而且數據也具有順序性，便于區間查找。
B+樹每個非葉子節點存放的元素只用于索引作用，所有數據保存在葉子節點中。一個 m 階的B+樹規定了：
- 有 k 個子樹的中間節點包含有 k 個元素（B樹中是 k-1 個元素），每個元素不保存數據，只用來索引，所有數據都保存在葉子節點；
- 所有的葉子節點中包含了全部元素的信息，及指向包含這些元素記錄的指針，且葉子節點本身以關鍵字的大小自小而大的順序鏈接；
- 所有的中間節點元素都同時存在于子節點，在子節點元素中是最大（或最小）元素。
因為非葉子節點中存放的元素不存放數據，所以每一層可以容納更多的元素，即磁盤中的每一頁可以存放更多元素，這樣在查找時，磁盤 IO 的次數也會減少。另外，B+樹的查找要更穩定一些，因為其所有的數據都在葉子節點，而每個葉子節點通過指針構成了一種鏈表結構，因此遍歷數據也會簡單很多。
B+樹的插入和刪除與B樹類似，它們的區別主要有以下幾點：
- B+樹內節點不存儲數據，所有數據存儲在葉節點(非葉子節點并不存儲真正的 data)，也因此導致查詢時間復雜度固定為 log（n）。而B樹可以在內部節點同時存儲鍵和值，因此，我們把頻繁訪問的數據放在靠近根節點的地方將會大大提高熱點數據的查詢效率，這種特性使得B樹在特定數據重復多次查詢的場景中更加高效。B樹查詢時間復雜度不固定，與 key 在樹中的位置有關，最好的情況下時間復雜度為 O(1)。
- B+樹的葉子節點有一條鏈相連，而B樹的葉子節點各自獨立。B+樹葉節點兩兩相連可大大增加區間訪問性，可使用在一定范圍內查詢等，而B樹每個節點 key 和 data 在一起，則無法區間查找。
- B+樹更適合外部存儲，由于內節點無 data 域，每個節點能索引的范圍更大更精確。B樹節點內部每個 key 都帶著 data 域，B+樹節點只存儲 key 的副本，真實的 key 和 data 域都在葉子節點存儲，而磁盤是分 block 的，一次磁盤 IO 會讀取若干個 block，具體和操作系統有關，那么由于磁盤 IO 數據大小是固定的，在一次 IO 中，單個元素越小量就越大。這就意味著B+樹單次磁盤 IO 的信息量大于B樹，從這點來看B+樹相對B樹磁盤 IO 次數少。
B樹最大的好處在于它對數據持續高漲讀性能的處理上，即使數據量級增大，它的讀也沒有放大，其奧秘在于對數據進行終極持久存儲時，B樹是以有規律的數據結構保存在硬盤上的。這樣隨著數據越來越大，它依然保持著有序有規律的特性，即便面對成千上萬的讀操作，都可以遵循條件運行，減少或避免讀放大的行為。
B樹/B+樹在數據庫存儲中應用非常廣泛，它能對數據進行有效地查找，避免了讀放大。此外，B樹和LSM經常一起使用。數據庫底層可以分為B樹機制、LSM機制，兩種機制各有各的優點和缺點。與B樹機制截然相反，LSM機制則是減少避免了寫放大。LSM機制充分利用了內存，在內存里面開辟了一個空間，寫數據優先往內存里放，寫進去直接返回用戶成功，而不是像B樹那樣寫一個，要找出誰更大誰更小，只要內存足夠，就直接往內存里面填就好，當內存達到一定的閾值后就會將內存中的數據以批量、順序的方式一次寫入硬盤上，內存則重置清零再服務新的寫要求。
傳統數據庫 MySQL、Oracle 使用的都是B樹機制，而 TiDB、OceanBase 一類的數據庫使用的則是優化后的 LSM 機制。TDengine 使用的是B樹 + LSM機制的方式，B樹存儲的是元數據（主要是時間戳+指標數據），LSM機制存儲的是具體的數據，元數據以有序表結構方式進行存儲，而具體數據則是追加的方式寫入，這樣既避免了讀放大又避免了寫放大。
時序數據庫如何構建索引？
以 TDengine 為例，針對時序數據的特點，我們專門研發了 TSDB 存儲和查詢引擎。在 TDengine 2.0 中，TSDB 存儲了一個 Vnode 中表的元數據以及時序數據（采集信息），后者以行和列兩種結構存儲（2.0開始引入行存儲），時序數據在內存中以 SkipList 方式進行索引，在硬盤中以 Block Range INdex（BRIN）方式進行索引。
TSDB 啟動時會事先分配一個BUFFER POOL 作為寫入緩沖（默認16MB*6=96MB），緩沖區塊大小和個數可配，區塊個數可修改。元數據和時序數據從緩沖塊申請寫入空間，寫入引擎向 BUFFER POOL 申請緩沖區塊，寫滿的緩沖區塊占總緩沖區塊的三分之一時觸發落盤操作。落盤時，緩沖區塊中的數據寫入到 META 等文件中，落盤結束后緩沖區塊歸還給 BUFFER POOL，形成循環機制。查詢時，對 MEM、IMEM 以及數據文件中的數據進行合并查詢。如下圖所示：
這種設計的優勢在于：
- 對于單表按照時間段的查詢效率很高
- 內存行存儲充分利用內存，緩存更多數據
- 文件中列存儲充分發揮壓縮算法優勢
- 避免 LSM 過多的文件合并
- 標簽數據與時序數據分離存儲
但也存在一些不足之處。在元數據存儲這塊，此前的 1.0 和 2.0 采取的都是比較簡單的存儲機制，即全內存存儲，數據在內存中以 hash 表的方式存儲，并輔以跳表索引，在 hash 表中有一個 Backup Storage Engine，它可以保證數據的持久化。該方式的優點是全內存、效率高，但缺點也很明顯，當啟動時，這部分數據就會全部加載到內存之中，不僅內存占用無法精準控制，還會導致開機啟動時間長。
因此，為了解決這些問題，我們在 TDengine 3.0 中研發了 TDB（一個 B+ 樹格式的的存儲引擎），來存儲元數據及元數據索引。TDB 的 B+ 樹存儲適合元數據讀多寫少的場景，能夠支持百億時間線的存儲，避免了元數據全內存存儲以及長時間的加載，同時解決了在有限內存下，表數量膨脹的問題。對于 TDB 是如何實現的，大家如果感興趣，可以去 上看一下源代碼。
TDB 的優點是內存可以精確控制，開機啟動速度快，在有限內存下也可以存儲海量的元數據，此外如果 TDB 外加 Cache 輔助的話，在一定程度上可以提供接近全內存 hash 表的查詢速度。事實上，關于 TDengine 3.0 存儲引擎的更新可以分為三大塊，首先是 TQ，基于 WAL 的消息隊列；其次是 META，基于 TDB 的元數據存儲引擎；第三是 TSDB，用來存儲時序數據的類 LSM 存儲引擎（TSDB SE）。關于 TQ 和 TSDB 的具體更新感興趣的小伙伴可以進入《支持消息隊列和流式計算背后，TDengine 3.0 存儲引擎的優化與升級》一文查看。
結語
在對時序數據特點進行挖掘和總結的前提下，TDengine 設計了存儲模型和查詢模型，摸索到了最適合進行時序數據處理的索引結構，正因為這些創新設計，TDengine 才表現出強勁的存儲性能和查詢性能。如果你也面臨著時序數據處理難題或想要和我們的核心研發人員進行交流和溝通，歡迎添加小T（tdengine），和一眾志同道合的開發者共同進步。
