MongoDB中使用 B樹的原因是什么

本篇文章給大家分享的是有關(guān) MongoDB中使用 B樹的原因是什么，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

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 作為默認的存儲引擎[^5]。

mongodb-architecture

作為 MongoDB 默認的存儲引擎，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 的默認存儲引擎 WiredTiger 為什么選擇使用 B 樹而不是 B+ 樹，還會對 B 樹和 LSM  樹之間的性能和應(yīng)用場景進行比較，幫助各位讀者更全面地理解今天的問題。

設(shè)計

既然要比較兩個不同數(shù)據(jù)結(jié)構(gòu)與 B 樹的差別，那么在這里我們將分兩個小節(jié)分別介紹 B+ 樹和 LSM 樹為什么沒有成為 WiredTiger  默認的數(shù)據(jù)結(jié)構(gòu)：

• 作為非關(guān)系型的數(shù)據(jù)庫，MongoDB 對于遍歷數(shù)據(jù)的需求沒有關(guān)系型數(shù)據(jù)庫那么強，它追求的是讀寫單個記錄的性能;

• 大多數(shù) OLTP 的數(shù)據(jù)庫面對的都是讀多寫少的場景，B 樹與 LSM 樹在該場景下有更大的優(yōu)勢;

上述的兩個場景都是 MongoDB 需要面對和解決的，所以我們會在這兩個常見場景下對不同的數(shù)據(jù)結(jié)構(gòu)進行比較。

非關(guān)系型

我們在上面其實已經(jīng)多次提到了 MongoDB 是非關(guān)系型的文檔數(shù)據(jù)庫，它完全拋棄了關(guān)系型數(shù)據(jù)庫那一套體系之后，在設(shè)計和實現(xiàn)上就非常自由，它不再需要遵循  SQL 和關(guān)系型數(shù)據(jù)庫的體系，可以更自由對特定場景進行優(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)之間選擇的最終目的就是減少查詢需要的隨機 IO 次數(shù)，MySQL 認為遍歷數(shù)據(jù)的查詢是常見的，所以它選擇  B+ 樹作為底層數(shù)據(jù)結(jié)構(gòu)，而舍棄了通過非葉節(jié)點存儲數(shù)據(jù)這一特性，但是 MongoDB 面對的問題就不太一樣了：

mongodb-wiredtiger-b-tree

雖然遍歷數(shù)據(jù)的查詢是相對常見的，但是 MongoDB 認為查詢單個數(shù)據(jù)記錄遠比遍歷數(shù)據(jù)更加常見，由于 B  樹的非葉結(jié)點也可以存儲數(shù)據(jù)，所以查詢一條數(shù)據(jù)所需要的平均隨機 IO 次數(shù)會比 B+ 樹少，使用 B 樹的 MongoDB 在類似場景中的查詢速度就會比  MySQL 快。這里并不是說 MongoDB 并不能對數(shù)據(jù)進行遍歷，我們在 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

上述查詢其實并不是范圍查詢，它沒有使用 >、< 等表達式，但是它卻會在 comments 表中查詢一系列的記錄，如果 comments  表上有索引 post_id，那么這個查詢可能就會在索引中遍歷相應(yīng)索引，找到滿足條件的 comment，這種查詢也會受益于 MySQL B+  樹相互連接的葉節(jié)點，因為它能減少磁盤的隨機 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ù)進行存儲時就不會遇到 db.comments.find( { post_id: 1 } ) 這樣的查詢了，我們只需要將 post  取出來就會獲得相關(guān)的全部評論，這種區(qū)別于傳統(tǒng)關(guān)系型數(shù)據(jù)庫的設(shè)計方式是需要所有使用 MongoDB 的開發(fā)者重新思考的，這也是很多人使用 MongoDB  后卻發(fā)現(xiàn)性能不如 MySQL 的最大原因 &mdash;&mdash; 使用的姿勢不對。

有些讀者到這里可能會有疑問了，既然 MongoDB 認為查詢單個數(shù)據(jù)記錄遠比遍歷數(shù)據(jù)的查詢更加常見，那為什么不使用哈希作為底層的數(shù)據(jù)結(jié)構(gòu)呢?

datastructures-and-query

如果我們使用哈希，那么對于所有單條記錄查詢的復雜度都會是 O(1)，但是遍歷數(shù)據(jù)的復雜度就是 O(n);如果使用 B+ 樹，那么單條記錄查詢的復雜度是  O(log n)，遍歷數(shù)據(jù)的復雜度就是 O(log n) +  X，這兩種不同的數(shù)據(jù)結(jié)構(gòu)一種提供了最好的單記錄查詢性能，一種提供了最好的遍歷數(shù)據(jù)的性能，但是這都不能滿足 MongoDB 面對的場景 &mdash;&mdash;  單記錄查詢非常常見，但是對于遍歷數(shù)據(jù)也需要有相對較好的性能支持，哈希這種性能表現(xiàn)較為極端的數(shù)據(jù)結(jié)構(gòu)往往只能在簡單、極端的場景下使用。

讀多寫少

LSM 樹是一個基于磁盤的數(shù)據(jù)結(jié)構(gòu)，它設(shè)計的主要目的是為長期需要高頻率寫入操作的文件提供低成本的索引機制[^8]。無論是 B 樹還是 B+  樹，向這些數(shù)據(jù)結(jié)構(gòu)組成的索引文件中寫入記錄都需要執(zhí)行的磁盤隨機寫，LSM 樹的優(yōu)化邏輯就是犧牲部分的讀性能，將隨機寫轉(zhuǎn)換成順序?qū)懸詢?yōu)化數(shù)據(jù)的寫入。

我們在這篇文章不會詳細介紹為什么 LSM 樹有著較好的寫入性能，我們只是來分析為什么 WiredTiger 使用 B  樹作為默認的數(shù)據(jù)結(jié)構(gòu)。WiredTiger 對 LSM 樹和 B  樹的性能進行了讀寫吞吐量的基準測試[^9]，通過基準測試得到了如下圖所示的結(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 樹的讀取性能是遠好于 LSM 樹的。對于大多數(shù)的 OLTP  系統(tǒng)來說，系統(tǒng)的查詢會是寫的很多倍，所以 LSM 樹在寫入方面的優(yōu)異表現(xiàn)也沒有辦法讓它成為 MongoDB 默認的數(shù)據(jù)格式。

以上就是 MongoDB中使用 B樹的原因是什么，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。