為什么 MongoDB 使用 B 樹？
為什么這么設(shè)計(Why's THE Design)是一系列關(guān)于計算機(jī)領(lǐng)域中程序設(shè)計決策的文章，我們在這個系列的每一篇文章中都會提出一個具體的問題并從不同的角度討論這種設(shè)計的優(yōu)缺點、對具體實現(xiàn)造成的影響。
概述
MongoDB 是一個通用的、面向文檔的分布式數(shù)據(jù)庫[^1]，這是官方對 MongoDB 介紹。區(qū)別于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫 MySQL、Oracle 和 SQL Server，MongoDB 最重要的一個特點就是『面向文檔』，由于數(shù)據(jù)存儲方式的不同，對外提供的接口不再是被大家熟知的 SQL，所以被劃分成了 NoSQL，NoSQL 是相對 SQL 而言的，很多我們耳熟能詳?shù)拇鎯ο到y(tǒng)都被劃分成了 NoSQL，例如：Redis、DynamoDB[^2] 和 Elasticsearch 等。
sql-and-nosq
NoSQL 經(jīng)常被理解成沒有 SQL(Non-SQL)或者非關(guān)系型(Non-Relational)[^3]，不過也有人將其理解成不只是 SQL(Not Only SQL)[^4]，深挖這個詞的含義和起源可能沒有太多意義，這種二次解讀很多時候都是為營銷服務(wù)的，我們只需要知道 MongoDB 對數(shù)據(jù)的存儲方式與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫完全不同。
MongoDB 的架構(gòu)與 MySQL 非常類似，它們底層都使用了可插拔的存儲引擎以滿足用戶的不同需求，用戶可以根據(jù)數(shù)據(jù)特征選擇不同的存儲引擎，最新版本的 MongoDB 使用了 WiredTiger 作為默認(rèn)的存儲引擎[^5]。
mongodb-architecture
作為 MongoDB 默認(rèn)的存儲引擎，WiredTiger 使用 B 樹作為索引底層的數(shù)據(jù)結(jié)構(gòu)，但是除了 B 樹之外，它還支持 LSM 樹作為可選的底層存儲結(jié)構(gòu)，LSM 樹的全稱是 Log-structured merge-tree，你可以在 MongoDB 中使用如下所示的命令創(chuàng)建一個基于 LSM 樹的集合(Collection)[^6]:
- db.createCollection(
- "posts",
- { storageEngine: { wiredTiger: {configString: "type=lsm"}}}
- )
我們在這篇文章中不僅會介紹 MongoDB 的默認(rèn)存儲引擎 WiredTiger 為什么選擇使用 B 樹而不是 B+ 樹，還會對 B 樹和 LSM 樹之間的性能和應(yīng)用場景進(jìn)行比較，幫助各位讀者更全面地理解今天的問題。
設(shè)計
既然要比較兩個不同數(shù)據(jù)結(jié)構(gòu)與 B 樹的差別，那么在這里我們將分兩個小節(jié)分別介紹 B+ 樹和 LSM 樹為什么沒有成為 WiredTiger 默認(rèn)的數(shù)據(jù)結(jié)構(gòu)：
- 作為非關(guān)系型的數(shù)據(jù)庫，MongoDB 對于遍歷數(shù)據(jù)的需求沒有關(guān)系型數(shù)據(jù)庫那么強(qiáng)，它追求的是讀寫單個記錄的性能;
- 大多數(shù) OLTP 的數(shù)據(jù)庫面對的都是讀多寫少的場景，B 樹與 LSM 樹在該場景下有更大的優(yōu)勢;
上述的兩個場景都是 MongoDB 需要面對和解決的，所以我們會在這兩個常見場景下對不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行比較。
非關(guān)系型
我們在上面其實已經(jīng)多次提到了 MongoDB 是非關(guān)系型的文檔數(shù)據(jù)庫，它完全拋棄了關(guān)系型數(shù)據(jù)庫那一套體系之后，在設(shè)計和實現(xiàn)上就非常自由，它不再需要遵循 SQL 和關(guān)系型數(shù)據(jù)庫的體系，可以更自由對特定場景進(jìn)行優(yōu)化，而在 MongoDB 假設(shè)的場景中遍歷數(shù)據(jù)并不是常見的需求。
mysql-innodb-b-plus-tree
MySQL 中使用 B+ 樹是因為 B+ 樹只有葉節(jié)點會存儲數(shù)據(jù)，將樹中的每一個葉節(jié)點通過指針連接起來就能實現(xiàn)順序遍歷，而遍歷數(shù)據(jù)在關(guān)系型數(shù)據(jù)庫中非常常見，所以這么選擇是完全沒有問題的[^7]。
MongoDB 和 MySQL 在多個不同數(shù)據(jù)結(jié)構(gòu)之間選擇的最終目的就是減少查詢需要的隨機(jī) IO 次數(shù)，MySQL 認(rèn)為遍歷數(shù)據(jù)的查詢是常見的，所以它選擇 B+ 樹作為底層數(shù)據(jù)結(jié)構(gòu)，而舍棄了通過非葉節(jié)點存儲數(shù)據(jù)這一特性，但是 MongoDB 面對的問題就不太一樣了：
mongodb-wiredtiger-b-tree
雖然遍歷數(shù)據(jù)的查詢是相對常見的，但是 MongoDB 認(rèn)為查詢單個數(shù)據(jù)記錄遠(yuǎn)比遍歷數(shù)據(jù)更加常見，由于 B 樹的非葉結(jié)點也可以存儲數(shù)據(jù)，所以查詢一條數(shù)據(jù)所需要的平均隨機(jī) IO 次數(shù)會比 B+ 樹少，使用 B 樹的 MongoDB 在類似場景中的查詢速度就會比 MySQL 快。這里并不是說 MongoDB 并不能對數(shù)據(jù)進(jìn)行遍歷，我們在 MongoDB 中也可以使用范圍來查詢一批滿足對應(yīng)條件的記錄，只是需要的時間會比 MySQL 長一些。
- SELECT * FROM comments WHERE created_at > '2019-01-01'
很多人看到遍歷數(shù)據(jù)的查詢想到的可能都是如上所示的范圍查詢，然而在關(guān)系型數(shù)據(jù)庫中更常見的其實是如下所示的 SQL —— 查詢外鍵或者某字段等于某一個值的全部記錄：
- SELECT * FROM comments WHERE post_id = 1
上述查詢其實并不是范圍查詢，它沒有使用 >、< 等表達(dá)式，但是它卻會在 comments 表中查詢一系列的記錄，如果 comments 表上有索引 post_id，那么這個查詢可能就會在索引中遍歷相應(yīng)索引，找到滿足條件的 comment，這種查詢也會受益于 MySQL B+ 樹相互連接的葉節(jié)點，因為它能減少磁盤的隨機(jī) IO 次數(shù)。
MongoDB 作為非關(guān)系型的數(shù)據(jù)庫，它從集合的設(shè)計上就使用了完全不同的方法，如果我們?nèi)匀皇褂脗鹘y(tǒng)的關(guān)系型數(shù)據(jù)庫的表設(shè)計思路來思考 MongoDB 中集合的設(shè)計，寫出類似如上所示的查詢會帶來相對比較差的性能：
- db.comments.find( { post_id: 1 } )
因為 B 樹的所有節(jié)點都能存儲數(shù)據(jù)，各個連續(xù)的節(jié)點之間沒有很好的辦法通過指針相連，所以上述查詢在 B 樹中性能會比 B+ 樹差很多，但是這并不是一個 MongoDB 中推薦的設(shè)計方法，更合適的做法其實是使用嵌入文檔，將 post 和屬于它的所有 comments 都存儲到一起：
- {
- "_id": "...",
- "title": "為什么 MongoDB 使用 B 樹",
- "author": "draven",
- "comments": [
- {
- "_id": "...",
- "content": "你這寫的不行"
- },
- {
- "_id": "...",
- "content": "一樓說的對"
- }
- ]
- }
使用上述方式對數(shù)據(jù)進(jìn)行存儲時就不會遇到 db.comments.find( { post_id: 1 } ) 這樣的查詢了，我們只需要將 post 取出來就會獲得相關(guān)的全部評論，這種區(qū)別于傳統(tǒng)關(guān)系型數(shù)據(jù)庫的設(shè)計方式是需要所有使用 MongoDB 的開發(fā)者重新思考的，這也是很多人使用 MongoDB 后卻發(fā)現(xiàn)性能不如 MySQL 的最大原因 —— 使用的姿勢不對。
有些讀者到這里可能會有疑問了，既然 MongoDB 認(rèn)為查詢單個數(shù)據(jù)記錄遠(yuǎn)比遍歷數(shù)據(jù)的查詢更加常見，那為什么不使用哈希作為底層的數(shù)據(jù)結(jié)構(gòu)呢?
datastructures-and-query
如果我們使用哈希，那么對于所有單條記錄查詢的復(fù)雜度都會是 O(1)，但是遍歷數(shù)據(jù)的復(fù)雜度就是 O(n);如果使用 B+ 樹，那么單條記錄查詢的復(fù)雜度是 O(log n)，遍歷數(shù)據(jù)的復(fù)雜度就是 O(log n) + X，這兩種不同的數(shù)據(jù)結(jié)構(gòu)一種提供了最好的單記錄查詢性能，一種提供了最好的遍歷數(shù)據(jù)的性能，但是這都不能滿足 MongoDB 面對的場景 —— 單記錄查詢非常常見，但是對于遍歷數(shù)據(jù)也需要有相對較好的性能支持，哈希這種性能表現(xiàn)較為極端的數(shù)據(jù)結(jié)構(gòu)往往只能在簡單、極端的場景下使用。
讀多寫少
LSM 樹是一個基于磁盤的數(shù)據(jù)結(jié)構(gòu)，它設(shè)計的主要目的是為長期需要高頻率寫入操作的文件提供低成本的索引機(jī)制[^8]。無論是 B 樹還是 B+ 樹，向這些數(shù)據(jù)結(jié)構(gòu)組成的索引文件中寫入記錄都需要執(zhí)行的磁盤隨機(jī)寫，LSM 樹的優(yōu)化邏輯就是犧牲部分的讀性能，將隨機(jī)寫轉(zhuǎn)換成順序?qū)懸詢?yōu)化數(shù)據(jù)的寫入。
我們在這篇文章不會詳細(xì)介紹為什么 LSM 樹有著較好的寫入性能，我們只是來分析為什么 WiredTiger 使用 B 樹作為默認(rèn)的數(shù)據(jù)結(jié)構(gòu)。WiredTiger 對 LSM 樹和 B 樹的性能進(jìn)行了讀寫吞吐量的基準(zhǔn)測試[^9]，通過基準(zhǔn)測試得到了如下圖所示的結(jié)果，從圖中的結(jié)果我們能發(fā)現(xiàn)：
LSM_btree_Throughput
在不限制寫入的情況下;
- LSM 樹的寫入性能是 B 樹的 1.5 ~ 2 倍;
- LSM 樹的讀取性能是 B 樹的 1/6 ~ 1/3;
在限制寫入的情況下;
- LSM 樹的寫入性能與 B 樹的性能基本持平;
- LSM 樹的讀取性能是 B 樹的 1/4 ~ 1/2;
在限制寫入的情況下，每秒會寫入 30,000 條數(shù)據(jù)，從這里的分析結(jié)果來看，無論那種情況下 B 樹的讀取性能是遠(yuǎn)好于 LSM 樹的。對于大多數(shù)的 OLTP 系統(tǒng)來說，系統(tǒng)的查詢會是寫的很多倍，所以 LSM 樹在寫入方面的優(yōu)異表現(xiàn)也沒有辦法讓它成為 MongoDB 默認(rèn)的數(shù)據(jù)格式。
總結(jié)
應(yīng)用場景永遠(yuǎn)都是系統(tǒng)設(shè)計時首先需要考慮的問題，作為 NoSQL 的 MongoDB，其目標(biāo)場景就與更早的數(shù)據(jù)庫就有著比較大的差異，我們來簡單總結(jié)一下 MongoDB 最終選擇使用 B 樹的兩個原因：
MySQL 使用 B+ 樹是因為數(shù)據(jù)的遍歷在關(guān)系型數(shù)據(jù)庫中非常常見，它經(jīng)常需要處理各個表之間的關(guān)系并通過范圍查詢一些數(shù)據(jù);但是 MongoDB 作為面向文檔的數(shù)據(jù)庫，與數(shù)據(jù)之間的關(guān)系相比，它更看重以文檔為中心的組織方式，所以選擇了查詢單個文檔性能較好的 B 樹，這個選擇對遍歷數(shù)據(jù)的查詢也可以保證可以接受的時延;
LSM 樹是一種專門用來優(yōu)化寫入的數(shù)據(jù)結(jié)構(gòu)，它將隨機(jī)寫變成了順序?qū)戯@著地提高了寫入性能，但是卻犧牲了讀的效率，這與大多數(shù)場景需要的特點是不匹配的，所以 MongoDB 最終還是選擇讀取性能更好的 B 樹作為默認(rèn)的數(shù)據(jù)結(jié)構(gòu);
到最后，我們還是來看一些比較開放的相關(guān)問題，有興趣的讀者可以仔細(xì)思考一下下面的問題：
BigTable、LevelDB 和 HBase 的應(yīng)用場景都是什么?它們的讀寫比例有多少?為什么使用 LSM 樹作為底層的數(shù)據(jù)結(jié)構(gòu)?
在設(shè)計表結(jié)構(gòu)時，MongoDB 與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫有哪些區(qū)別?
如果對文章中的內(nèi)容有疑問或者想要了解更多軟件工程上一些設(shè)計決策背后的原因，可以在博客下面留言，作者會及時回復(fù)本文相關(guān)的疑問并選擇其中合適的主題作為后續(xù)的內(nèi)容。
[^1]: MongoDB 官方網(wǎng)站 The database for modern applications https://www.mongodb.com/
[^2]: 分布式鍵值存儲 Dynamo 的實現(xiàn)原理 https://draveness.me/dynamo
[^3]: NoSQL 維基百科 https://en.wikipedia.org/wiki/NoSQL
[^4]: NoSQL (Not Only SQL database) https://searchdatamanagement.techtarget.com/definition/NoSQL-Not-Only-SQL
[^5]: 『淺入淺出』MongoDB 和 WiredTiger https://draveness.me/mongodb-wiredtiger
[^6]: MongoDB 中的集合(Collection)與 MySQL 中的表(Table)是差不多的概念
[^7]: 為什么 MySQL 使用 B+ 樹 · Why's THE Design? https://draveness.me/whys-the-design-mysql-b-plus-tree
[^8]: The Log-Structured Merge-Tree (LSM-Tree), Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil https://www.cs.umb.edu/~poneil/lsmtree.pdf
[^9]: Btree vs LSM https://github.com/wiredtiger/wiredtiger/wiki/Btree-vs-LSM
