編者薦語：

本文作者對 MySQL 中 B+ 樹的講解可謂是深入淺出，推薦同學們閱讀。

以下文章來源于真沒什么邏輯?，作者Draveness

為什么 MySQL 使用 B+ 樹是面試中經(jīng)常會出現(xiàn)的問題，很多人對于這個問題可能都有一些自己的理解，但是多數(shù)的回答都不夠完整和準確，大多數(shù)人都只會簡單說一下 B+ 樹和 B 樹的區(qū)別，但是都沒有真正回答 MySQL 為什么選擇使用 B+ 樹這個問題，我們在這篇文章中就會深入分析 MySQL 選擇 B+ 樹背后的一些原因。

概述

首先需要澄清的一點是，MySQL 跟 B+ 樹沒有直接的關系，真正與 B+ 樹有關系的是 MySQL 的默認存儲引擎 InnoDB，MySQL 中存儲引擎的主要作用是負責數(shù)據(jù)的存儲和提取，除了 InnoDB 之外，MySQL 中也支持 MyISAM 作為表的底層存儲引擎。

我們在使用 SQL 語句創(chuàng)建表時就可以為當前表指定使用的存儲引擎，你能在 MySQL 的文檔 Alternative Storage Engines 中找到它支持的全部存儲引擎，例如：MyISAM、CSV、MEMORY?等，然而默認情況下，使用如下所示的 SQL 語句來創(chuàng)建表就會得到 InnoDB 存儲引擎支撐的表：

CREATE TABLE t1 (
? ?a INT,
? ?b CHAR (20
), PRIMARY KEY (a)) ENGINE=InnoDB;


想要詳細了解 MySQL 默認存儲引擎的讀者，可以通過之前的文章 『淺入淺出』MySQL 和 InnoDB 了解包括 InnoDB 存儲方式、索引和鎖等內(nèi)容，我們在這里主要不會介紹 InnoDB 相關的過多內(nèi)容。

我們今天最終將要分析的問題其實還是，為什么 MySQL 默認的存儲引擎 InnoDB 會使用 MySQL 來存儲數(shù)據(jù)，相信對 MySQL 稍微有些了解的人都知道，無論是表中的數(shù)據(jù)（主鍵索引）還是輔助索引最終都會使用 B+ 樹來存儲數(shù)據(jù)，其中前者在表中會以?<id, row>?的方式存儲，而后者會以?<index, id>?的方式進行存儲，這其實也比較好理解：

• 在主鍵索引中，id?是主鍵，我們能夠通過?id?找到該行的全部列；

• 在輔助索引中，索引中的幾個列構成了鍵，我們能夠通過索引中的列找到?id，如果有需要的話，可以再通過?id?找到當前數(shù)據(jù)行的全部內(nèi)容；

對于 InnoDB 來說，所有的數(shù)據(jù)都是以鍵值對的方式存儲的，主鍵索引和輔助索引在存儲數(shù)據(jù)時會將?id?和?index?作為鍵，將所有列和?id?作為鍵對應的值。

在具體分析 InnoDB 使用 B+ 樹背后的原因之前，我們需要為 B+ 樹找?guī)讉€『假想敵』，因為如果我們只有一個選擇，那么選擇 B+ 樹也并不值得討論，找到的兩個假想敵就是 B 樹和哈希，相信這也是很多人會在面試中真實遇到的問題，我們就以這兩種數(shù)據(jù)結構為例，分析比較 B+ 樹的優(yōu)點。

設計

到了這里我們已經(jīng)明確了今天待討論的問題，也就是為什么 MySQL 的 InnoDB 存儲引擎會選擇 B+ 樹作為底層的數(shù)據(jù)結構，而不選擇 B 樹或者哈希？在這一節(jié)中，我們將通過以下的兩個方面介紹 InnoDB 這樣選擇的原因。

• InnoDB 需要支持的場景和功能需要在特定查詢上擁有較強的性能；

• CPU 將磁盤上的數(shù)據(jù)加載到內(nèi)存中需要花費大量的時間，這使得 B+ 樹成為了非常好的選擇；

數(shù)據(jù)的持久化以及持久化數(shù)據(jù)的查詢其實是一個常見的需求，而數(shù)據(jù)的持久化就需要我們與磁盤、內(nèi)存和 CPU 打交道；MySQL 作為 OLTP 的數(shù)據(jù)庫不僅需要具備事務的處理能力，而且要保證數(shù)據(jù)的持久化并且能夠有一定的實時數(shù)據(jù)查詢能力，這些需求共同決定了 B+ 樹的選擇，接下來我們會詳細分析上述兩個原因背后的邏輯。

讀寫性能

很多人對 OLTP 這個詞可能不是特別了解，我們幫助各位讀者快速理解一下，與 OLTP 相比的還有 OLAP，它們分別是 Online Transaction Processing 和 Online Analytical Processing，從這兩個名字中我們就可以看出，前者指的就是傳統(tǒng)的關系型數(shù)據(jù)庫，主要用于處理基本的、日常的事務處理，而后者主要在數(shù)據(jù)倉庫中使用，用于支持一些復雜的分析和決策。

作為支撐 OLTP 數(shù)據(jù)庫的存儲引擎，我們經(jīng)常會使用 InnoDB 完成以下的一些工作：

• 通過?INSERT、UPDATE?和?DELETE?語句對表中的數(shù)據(jù)進行增加、修改和刪除；

• 通過?UPDATE?和?DELETE?語句對符合條件的數(shù)據(jù)進行批量的刪除；

• 通過?SELECT?語句和主鍵查詢某條記錄的全部列；

• 通過?SELECT?語句在表中查詢符合某些條件的記錄并根據(jù)某些字段排序；

• 通過?SELECT?語句查詢表中數(shù)據(jù)的行數(shù)；

• 通過唯一索引保證表中某個字段或者某幾個字段的唯一性；

如果我們使用 B+ 樹作為底層的數(shù)據(jù)結構，那么所有只會訪問或者修改一條數(shù)據(jù)的 SQL 的時間復雜度都是?O(log n)，也就是樹的高度，但是使用哈希卻有可能達到?O(1)?的時間復雜度，看起來是不是特別的美好。但是當我們使用如下所示的 SQL 時，哈希的表現(xiàn)就不會這么好了：

SELECT * FROM posts WHERE author = 'draven' ORDER BY created_at DESC
SELECT * FROM posts WHERE comments_count > 10
UPDATE posts SET github = 'github.com/draveness' WHERE author = 'draven'
DELETE FROM posts WHERE author = 'draven'


如果我們使用哈希作為底層的數(shù)據(jù)結構，遇到上述的場景時，使用哈希構成的主鍵索引或者輔助索引可能就沒有辦法快速處理了，它對于處理范圍查詢或者排序性能會非常差，只能進行全表掃描并依次判斷是否滿足條件。全表掃描對于數(shù)據(jù)庫來說是一個非常糟糕的結果，這其實也就意味著我們使用的數(shù)據(jù)結構對于這些查詢沒有其他任何效果，最終的性能可能都不如從日志中順序進行匹配。

使用 B+ 樹其實能夠保證數(shù)據(jù)按照鍵的順序進行存儲，也就是相鄰的所有數(shù)據(jù)其實都是按照自然順序排列的，使用哈希卻無法達到這樣的效果，因為哈希函數(shù)的目的就是讓數(shù)據(jù)盡可能被分散到不同的桶中進行存儲，所以在遇到可能存在相同鍵?author = 'draven?或者排序以及范圍查詢?comments_count > 10?時，由哈希作為底層數(shù)據(jù)結構的表可能就會面對數(shù)據(jù)庫查詢的噩夢 —— 全表掃描。

B 樹和 B+ 樹在數(shù)據(jù)結構上其實有一些類似，它們都可以按照某些順序對索引中的內(nèi)容進行遍歷，對于排序和范圍查詢等操作，B 樹和 B+ 樹相比于哈希會帶來更好的性能，當然如果索引建立不夠好或者 SQL 查詢非常復雜，依然會導致全表掃描。

與 B 樹和 B+ 樹相比，哈希作為底層的數(shù)據(jù)結構的表能夠以?O(1)?的速度處理單個數(shù)據(jù)行的增刪改查，但是面對范圍查詢或者排序時就會導致全表掃描的結果，而 B 樹和 B+ 樹雖然在單數(shù)據(jù)行的增刪查改上需要?O(log n)?的時間，但是它會將索引列相近的數(shù)據(jù)按順序存儲，所以能夠避免全表掃描。

數(shù)據(jù)加載

既然使用哈希無法應對我們常見的 SQL 中排序和范圍查詢等操作，而 B 樹和 B 樹和 B+ 樹都可以相對高效地執(zhí)行這些查詢，那么為什么我們不選擇 B 樹呢？這個原因其實非常簡單 —— 計算機在讀寫文件時會以頁為單位將數(shù)據(jù)加載到內(nèi)存中。頁的大小可能會根據(jù)操作系統(tǒng)的不同而發(fā)生變化，不過在大多數(shù)的操作系統(tǒng)中，頁的大小都是?4KB，你可以通過如下的命令獲取操作系統(tǒng)上的頁大小:

$ getconf PAGE_SIZE
4096


作者使用 macOS 系統(tǒng)的頁大小就是?4KB，當然在不同的計算機上得到不同的結果是完全有可能的。

當我們需要在數(shù)據(jù)庫中查詢數(shù)據(jù)時，CPU 會發(fā)現(xiàn)當前數(shù)據(jù)位于磁盤而不是內(nèi)存中，這時就會觸發(fā) I/O 操作將數(shù)據(jù)加載到內(nèi)存中進行訪問，數(shù)據(jù)的加載都是以頁的維度進行加載的，然而將數(shù)據(jù)從磁盤讀取到內(nèi)存中所需要的成本是非常大的，普通磁盤（非 SSD）加載數(shù)據(jù)需要經(jīng)過隊列、尋道、旋轉以及傳輸?shù)倪@些過程，大概要花費?10ms?左右的時間。

我們在估算 MySQL 的查詢時就可以使用?10ms?這個數(shù)量級對隨機 I/O 占用的時間進行估算，這里想要說的是隨機 I/O 對于 MySQL 的查詢性能影響會非常大，而順序讀取磁盤中的數(shù)據(jù)時速度可以達到 40MB/s，這兩者的性能差距有幾個數(shù)量級，由此我們也應該盡量減少隨機 I/O 的次數(shù)，這樣才能提高性能。

B 樹與 B+ 樹的最大區(qū)別就是，B 樹可以在非葉結點中存儲數(shù)據(jù)，但是 B+ 樹的所有數(shù)據(jù)其實都存儲在葉子節(jié)點中，當一個表底層的數(shù)據(jù)結構是 B 樹時，假設我們需要訪問所有『大于 4，并且小于 9 的數(shù)據(jù)』：

如果不考慮任何優(yōu)化，在上面的簡單 B 樹中我們需要進行 4 次磁盤的隨機 I/O 才能找到所有滿足條件的數(shù)據(jù)行：

1. 加載根節(jié)點所在的頁，發(fā)現(xiàn)根節(jié)點的第一個元素是 6，大于 4；

2. 通過根節(jié)點的指針加載左子節(jié)點所在的頁，遍歷頁面中的數(shù)據(jù)，找到 5；

3. 重新加載根節(jié)點所在的頁，發(fā)現(xiàn)根節(jié)點不包含第二個元素；

4. 通過根節(jié)點的指針加載右子節(jié)點所在的頁，遍歷頁面中的數(shù)據(jù)，找到 7 和 8；

當然我們可以通過各種方式來對上述的過程進行優(yōu)化，不過 B 樹能做的優(yōu)化 B+ 樹基本都可以，所以我們不需要考慮優(yōu)化 B 樹而帶來的收益，直接來看看什么樣的優(yōu)化 B+ 樹可以做，而 B 樹不行。

由于所有的節(jié)點都可能包含目標數(shù)據(jù)，我們總是要從根節(jié)點向下遍歷子樹查找滿足條件的數(shù)據(jù)行，這個特點帶來了大量的隨機 I/O，也是 B 樹最大的性能問題。

B+ 樹中就不存在這個問題了，因為所有的數(shù)據(jù)行都存儲在葉節(jié)點中，而這些葉節(jié)點可以通過『指針』依次按順序連接，當我們在如下所示的 B+ 樹遍歷數(shù)據(jù)時可以直接在多個子節(jié)點之間進行跳轉，這樣能夠節(jié)省大量的磁盤 I/O 時間，也不需要在不同層級的節(jié)點之間對數(shù)據(jù)進行拼接和排序；通過一個 B+ 樹最左側的葉子節(jié)點，我們可以像鏈表一樣遍歷整個樹中的全部數(shù)據(jù)，我們也可以引入雙向鏈表保證倒序遍歷時的性能

有些讀者可能會認為使用 B+ 樹這種數(shù)據(jù)結構會增加樹的高度從而增加整體的耗時，然而高度為 3 的 B+ 樹就能夠存儲千萬級別的數(shù)據(jù)，實踐中 B+ 樹的高度最多也就 4 或者 5，所以這并不是影響性能的根本問題。

總結

任何不考慮應用場景的設計都不是最好的設計，當我們明確的定義了使用 MySQL 時的常見查詢需求并理解場景之后，再對不同的數(shù)據(jù)結構進行選擇就成了理所當然的事情，當然 B+ 樹可能無法對所有 OLTP 場景下的查詢都有著較好的性能，但是它能夠解決大多數(shù)的問題。

我們在這里重新回顧一下 MySQL 默認的存儲引擎選擇 B+ 樹而不是哈?；蛘?B 樹的原因：

• 哈希雖然能夠提供?O(1)?的單數(shù)據(jù)行操作性能，但是對于范圍查詢和排序卻無法很好地支持，最終導致全表掃描；

• B 樹能夠在非葉節(jié)點中存儲數(shù)據(jù)，但是這也導致在查詢連續(xù)數(shù)據(jù)時可能會帶來更多的隨機 I/O，而 B+ 樹的所有葉節(jié)點可以通過指針相互連接，能夠減少順序遍歷時產(chǎn)生的額外隨機 I/O；

如果想要追求各方面的極致性能也不是沒有可能，只是會帶來更高的復雜度，我們可以為一張表同時建 B+ 樹和哈希構成的存儲結構，這樣不同類型的查詢就可以選擇相對更快的數(shù)據(jù)結構，但是會導致更新和刪除時需要操作多份數(shù)據(jù)。

從今天的角度來看，B+ 樹可能不是 InnoDB 的最優(yōu)選擇，但是它一定是能夠滿足當時設計場景的需要，從 B+ 樹作為數(shù)據(jù)庫底層的存儲結構到今天已經(jīng)過了幾十年的時間，我們不得不說優(yōu)秀的工程設計確實有足夠的生命力。而我們作為工程師，在選擇數(shù)據(jù)庫時也應該非常清楚地知道不同數(shù)據(jù)庫適合的場景，因為軟件工程中沒有銀彈。

到最后，我們還是來看一些比較開放的相關問題，有興趣的讀者可以仔細思考一下下面的問題：

• 常用于分析的 OLAP 數(shù)據(jù)庫一般會使用什么樣的數(shù)據(jù)結構存儲數(shù)據(jù)？為什么？

• Redis 是如何對數(shù)據(jù)進行持久化存儲的？常見的數(shù)據(jù)結構都有什么？

Reference

• B+ tree · Wikipedia

• What is the difference between Mysql InnoDB B+ tree index and hash index? Why does MongoDB use B-tree?

• B+Trees and why I love them, part I

• What are the main differences between INNODB and MYISAM

• B+ Tree File Organization

• Database Index: A Re-visit to B+ Tree

• Fundamentals of database systems