LSM 樹（Log-Structured Merge-Tree）

• 核心原理：通過將隨機寫轉換為順序寫優化寫入性能，適用于寫密集型場景。數據首先寫入內存中的 MemTable（有序結構，如跳表），當達到閾值后轉為 Immutable MemTable，再刷入磁盤形成 SSTable。通過分層合并（Compaction）清理冗余數據。
• 關鍵特點：
  • 寫放大：合并操作可能導致重復寫入，但順序寫優勢顯著（如機械盤順序寫性能是隨機寫的千倍）。
  • 讀放大：需從內存到多層級磁盤文件逐層查找，但通過布隆過濾器和索引優化。
  • 分層結構：數據從高層（熱數據）到低層（冷數據）逐步下沉，低層容量按指數級增長（如每層容量是上一層的10倍）。

---

SSTable（Sorted String Table）

• 定義：磁盤上的有序鍵值文件，不可變且全局有序（除Level 0外），每個文件包含數據塊、索引塊和布隆過濾器。
• 優化手段：
  • 索引加速：通過稀疏索引快速定位數據塊。
  • 布隆過濾器：減少無效磁盤I/O，判斷鍵是否存在于文件中。
  • 壓縮：使用Snappy/ZSTD等算法減少存儲空間和傳輸帶寬。

---

LevelDB

• 定位：Google開源的輕量級單機KV存儲引擎，基于LSM樹。
• 核心設計：
  • 內存結構：Active MemTable（寫入口）和Immutable MemTable（待刷盤）。
  • Compaction策略：分層合并，Level 0允許文件間Key重疊，其他層級全局有序。
  • 限制：單線程Compaction、無多版本控制，適合嵌入式或小規模場景。
• 典型應用：Chrome瀏覽器本地存儲、輕量級NoSQL場景。

---

RocksDB

• 定位：Facebook優化的LevelDB升級版，支持企業級高并發和大數據量。
• 關鍵優化：
  • 并行Compaction：多線程加速合并，降低寫停頓。
  • 冷熱分離：熱數據優先保留在低層，冷數據下沉至高層。
  • 靈活配置：支持多種壓縮算法、速率限制、TTL等。
  • 增量備份：支持Checkpoint和增量快照。
• 應用場景：MySQL底層存儲（如TiDB）、分布式系統（如CockroachDB）、消息隊列（如Kafka的RocksDB狀態存儲）。

---

TiDB

• 定位：國產分布式HTAP數據庫，兼容MySQL協議，底層存儲基于RocksDB。
• 架構組件：
  • TiKV：分布式KV存儲引擎，數據按Region分片，基于Raft協議保證一致性。
  • PD（Placement Driver）：全局調度器，管理元數據、負載均衡和故障恢復。
  • TiSpark：集成Spark處理復雜OLAP查詢。
• 核心優勢：
  • 水平擴展：通過添加節點實現計算和存儲分離擴容。
  • HTAP能力：行存（TiKV）支持OLTP，列存（TiFlash）支持OLAP。
  • 金融級可靠性：支持分布式事務（Percolator協議）和多副本強一致。

---

對比與關聯

維度	LevelDB	RocksDB	TiDB
架構	單機嵌入式	單機/分布式擴展	分布式HTAP
Compaction	單線程，分層合并	多線程，冷熱分離	基于RocksDB，Region分片
適用場景	小規模、低并發	高吞吐、企業級存儲	大規模OLTP+OLAP混合負載
核心優化	基礎LSM實現	多級緩存、速率控制	全局調度、行列混存

---

典型應用場景

1. LSM樹：寫密集型場景（日志存儲、時序數據）。
2. LevelDB：瀏覽器本地存儲、小型嵌入式系統。
3. RocksDB：分布式數據庫底層引擎（如TiKV）、消息隊列狀態存儲。
4. TiDB：金融級分布式事務（如支付系統）、實時分析（如電商大促監控）。