(給ImportNew加星标，提高Java技能)
轉自：真沒什麼邏輯，作者：Draveness
偶人為什麼這麼設計(Why's THE Design)是一系列關于計算機領域中程式設計決策的文章，我們在這個系列的每一篇文章中都會提出一個具體的問題并從不同的角度讨論這種設計的優缺點、對具體實作造成的影響。如果你有想要了解的問題，可以在文章下面留言。
為什麼 MySQL 使用 B+ 樹是面試中經常會出現的問題，很多人對于這個問題可能都有一些自己的了解，但是多數的回答都不夠完整和準确，大多數人都隻會簡單說一下 B+ 樹和 B 樹的差別，但是都沒有真正回答 MySQL 為什麼選擇使用 B+ 樹這個問題，我們在這篇文章中就會深入分析 MySQL 選擇 B+ 樹背後的一些原因。
概述
首先需要澄清的一點是，MySQL 跟 B+ 樹沒有直接的關系，真正與 B+ 樹有關系的是 MySQL 的預設存儲引擎 InnoDB，MySQL 中存儲引擎的主要作用是負責資料的存儲和提取，除了 InnoDB 之外，MySQL 中也支援 MyISAM 作為表的底層存儲引擎。
我們在使用 SQL 語句建立表時就可以為目前表指定使用的存儲引擎，你能在 MySQL 的文檔 Alternative Storage Engines 中找到它支援的全部存儲引擎，例如：MyISAM、CSV、MEMORY 等，然而預設情況下，使用如下所示的 SQL 語句來建立表就會得到 InnoDB 存儲引擎支撐的表：
t1 (
想要詳細了解 MySQL 預設存儲引擎的讀者，可以通過之前的文章 『淺入淺出』MySQL 和 InnoDB 了解包括 InnoDB 存儲方式、索引和鎖等内容，我們在這裡主要不會介紹 InnoDB 相關的過多内容。
我們今天最終将要分析的問題其實還是，為什麼 MySQL 預設的存儲引擎 InnoDB 會使用 MySQL 來存儲資料，相信對 MySQL 稍微有些了解的人都知道，無論是表中的資料(主鍵索引)還是輔助索引最終都會使用 B+ 樹來存儲資料，其中前者在表中會以 的方式存儲，而後者會以 的方式進行存儲，這其實也比較好了解：
- 在主鍵索引中，id 是主鍵，我們能夠通過 id 找到該行的全部列；
- 在輔助索引中，索引中的幾個列構成了鍵，我們能夠通過索引中的列找到 id，如果有需要的話，可以再通過 id 找到目前資料行的全部内容；
對于 InnoDB 來說，所有的資料都是以鍵值對的方式存儲的，主鍵索引和輔助索引在存儲資料時會将 id 和 index 作為鍵，将所有列和 id 作為鍵對應的值。
在具體分析 InnoDB 使用 B+ 樹背後的原因之前，我們需要為 B+ 樹找幾個『假想敵』，因為如果我們隻有一個選擇，那麼選擇 B+ 樹也并不值得讨論，找到的兩個假想敵就是 B 樹和哈希，相信這也是很多人會在面試中真實遇到的問題，我們就以這兩種資料結構為例，分析比較 B+ 樹的優點。
設計
到了這裡我們已經明确了今天待讨論的問題，也就是為什麼 MySQL 的 InnoDB 存儲引擎會選擇 B+ 樹作為底層的資料結構，而不選擇 B 樹或者哈希？在這一節中，我們将通過以下的兩個方面介紹 InnoDB 這樣選擇的原因。
InnoDB 需要支援的場景和功能需要在特定查詢上擁有較強的性能；
CPU 将磁盤上的資料加載到記憶體中需要花費大量的時間，這使得 B+ 樹成為了非常好的選擇；
資料的持久化以及持久化資料的查詢其實是一個常見的需求，而資料的持久化就需要我們與磁盤、記憶體和 CPU 打交道；MySQL 作為 OLTP 的資料庫不僅需要具備事務的處理能力，而且要保證資料的持久化并且能夠有一定的實時資料查詢能力，這些需求共同決定了 B+ 樹的選擇，接下來我們會詳細分析上述兩個原因背後的邏輯。
讀寫性能
很多人對 OLTP 這個詞可能不是特别了解，我們幫助各位讀者快速了解一下，與 OLTP 相比的還有 OLAP，它們分别是 Online Transaction Processing 和 Online Analytical Processing，從這兩個名字中我們就可以看出，前者指的就是傳統的關系型資料庫，主要用于處理基本的、日常的事務處理，而後者主要在資料倉庫中使用，用于支援一些複雜的分析和決策。
作為支撐 OLTP 資料庫的存儲引擎，我們經常會使用 InnoDB 完成以下的一些工作：
- 通過 INSERT、UPDATE 和 DELETE 語句對表中的資料進行增加、修改和删除；
- 通過 UPDATE 和 DELETE 語句對符合條件的資料進行批量的删除；
- 通過 SELECT 語句和主鍵查詢某條記錄的全部列；
- 通過 SELECT 語句在表中查詢符合某些條件的記錄并根據某些字段排序；
- 通過 SELECT 語句查詢表中資料的行數；
- 通過唯一索引保證表中某個字段或者某幾個字段的唯一性；
如果我們使用 B+ 樹作為底層的資料結構，那麼所有隻會通路或者修改一條資料的 SQL 的時間複雜度都是 O(log n)，也就是樹的高度，但是使用哈希卻有可能達到 O(1) 的時間複雜度，看起來是不是特别的美好。但是當我們使用如下所示的 SQL 時，哈希的表現就不會這麼好了：
'draven' ORDER BY created_at DESC
如果我們使用哈希作為底層的資料結構，遇到上述的場景時，使用哈希構成的主鍵索引或者輔助索引可能就沒有辦法快速處理了，它對于處理範圍查詢或者排序性能會非常差，隻能進行全表掃描并依次判斷是否滿足條件。全表掃描對于資料庫來說是一個非常糟糕的結果，這其實也就意味着我們使用的資料結構對于這些查詢沒有其他任何效果，最終的性能可能都不如從日志中順序進行比對。
使用 B+ 樹其實能夠保證資料按照鍵的順序進行存儲，也就是相鄰的所有資料其實都是按照自然順序排列的，使用哈希卻無法達到這樣的效果，因為哈希函數的目的就是讓資料盡可能被分散到不同的桶中進行存儲，是以在遇到可能存在相同鍵 author = 'draven 或者排序以及範圍查詢 comments_count > 10 時，由哈希作為底層資料結構的表可能就會面對資料庫查詢的噩夢 —— 全表掃描。
B 樹和 B+ 樹在資料結構上其實有一些類似，它們都可以按照某些順序對索引中的内容進行周遊，對于排序和範圍查詢等操作，B 樹和 B+ 樹相比于哈希會帶來更好的性能，當然如果索引建立不夠好或者 SQL 查詢非常複雜，依然會導緻全表掃描。
與 B 樹和 B+ 樹相比，哈希作為底層的資料結構的表能夠以 O(1) 的速度處理單個資料行的增删改查，但是面對範圍查詢或者排序時就會導緻全表掃描的結果，而 B 樹和 B+ 樹雖然在單資料行的增删查改上需要 O(log n) 的時間，但是它會将索引列相近的資料按順序存儲，是以能夠避免全表掃描。
資料加載
既然使用哈希無法應對我們常見的 SQL 中排序和範圍查詢等操作，而 B 樹和 B 樹和 B+ 樹都可以相對高效地執行這些查詢，那麼為什麼我們不選擇 B 樹呢？這個原因其實非常簡單 —— 計算機在讀寫檔案時會以頁為機關将資料加載到記憶體中。頁的大小可能會根據作業系統的不同而發生變化，不過在大多數的作業系統中，頁的大小都是 4KB，你可以通過如下的指令擷取作業系統上的頁大小:
$ getconf PAGE_SIZE
4096
作者使用 macOS 系統的頁大小就是 4KB，當然在不同的計算機上得到不同的結果是完全有可能的。
當我們需要在資料庫中查詢資料時，CPU 會發現目前資料位于磁盤而不是記憶體中，這時就會觸發 I/O 操作将資料加載到記憶體中進行通路，資料的加載都是以頁的次元進行加載的，然而将資料從磁盤讀取到記憶體中所需要的成本是非常大的，普通磁盤(非 SSD)加載資料需要經過隊列、尋道、旋轉以及傳輸的這些過程，大概要花費 10ms 左右的時間。
我們在估算 MySQL 的查詢時就可以使用 10ms 這個數量級對随機 I/O 占用的時間進行估算，這裡想要說的是随機 I/O 對于 MySQL 的查詢性能影響會非常大，而順序讀取磁盤中的資料時速度可以達到 40MB/s，這兩者的性能差距有幾個數量級，由此我們也應該盡量減少随機 I/O 的次數，這樣才能提高性能。
B 樹與 B+ 樹的最大差別就是，B 樹可以在非葉結點中存儲資料，但是 B+ 樹的所有資料其實都存儲在葉子節點中，當一個表底層的資料結構是 B 樹時，假設我們需要通路所有『大于 4，并且小于 9 的資料』：
如果不考慮任何優化，在上面的簡單 B 樹中我們需要進行 4 次磁盤的随機 I/O 才能找到所有滿足條件的資料行：
- 加載根節點所在的頁，發現根節點的第一個元素是 6，大于 4；
- 通過根節點的指針加載左子節點所在的頁，周遊頁面中的資料，找到 5；
- 重新加載根節點所在的頁，發現根節點不包含第二個元素；
- 通過根節點的指針加載右子節點所在的頁，周遊頁面中的資料，找到 7 和 8；
當然我們可以通過各種方式來對上述的過程進行優化，不過 B 樹能做的優化 B+ 樹基本都可以，是以我們不需要考慮優化 B 樹而帶來的收益，直接來看看什麼樣的優化 B+ 樹可以做，而 B 樹不行。
由于所有的節點都可能包含目标資料，我們總是要從根節點向下周遊子樹查找滿足條件的資料行，這個特點帶來了大量的随機 I/O，也是 B 樹最大的性能問題。
B+ 樹中就不存在這個問題了，因為所有的資料行都存儲在葉節點中，而這些葉節點可以通過『指針』依次按順序連接配接，當我們在如下所示的 B+ 樹周遊資料時可以直接在多個子節點之間進行跳轉，這樣能夠節省大量的磁盤 I/O 時間，也不需要在不同層級的節點之間對資料進行拼接和排序；通過一個 B+ 樹最左側的葉子節點，我們可以像連結清單一樣周遊整個樹中的全部資料，我們也可以引入雙向連結清單保證倒序周遊時的性能
有些讀者可能會認為使用 B+ 樹這種資料結構會增加樹的高度進而增加整體的耗時，然而高度為 3 的 B+ 樹就能夠存儲千萬級别的資料，實踐中 B+ 樹的高度最多也就 4 或者 5，是以這并不是影響性能的根本問題。
總結
任何不考慮應用場景的設計都不是最好的設計，當我們明确的定義了使用 MySQL 時的常見查詢需求并了解場景之後，再對不同的資料結構進行選擇就成了理所當然的事情，當然 B+ 樹可能無法對所有 OLTP 場景下的查詢都有着較好的性能，但是它能夠解決大多數的問題。
我們在這裡重新回顧一下 MySQL 預設的存儲引擎選擇 B+ 樹而不是哈希或者 B 樹的原因：
- 哈希雖然能夠提供 O(1) 的單資料行操作性能，但是對于範圍查詢和排序卻無法很好地支援，最終導緻全表掃描；
- B 樹能夠在非葉節點中存儲資料，但是這也導緻在查詢連續資料時可能會帶來更多的随機 I/O，而 B+ 樹的所有葉節點可以通過指針互相連接配接，能夠減少順序周遊時産生的額外随機 I/O；
如果想要追求各方面的極緻性能也不是沒有可能，隻是會帶來更高的複雜度，我們可以為一張表同時建 B+ 樹和哈希構成的存儲結構，這樣不同類型的查詢就可以選擇相對更快的資料結構，但是會導緻更新和删除時需要操作多份資料。
從今天的角度來看，B+ 樹可能不是 InnoDB 的最優選擇，但是它一定是能夠滿足當時設計場景的需要，從 B+ 樹作為資料庫底層的存儲結構到今天已經過了幾十年的時間，我們不得不說優秀的工程設計确實有足夠的生命力。而我們作為工程師，在選擇資料庫時也應該非常清楚地知道不同資料庫适合的場景，因為軟體工程中沒有銀彈。
到最後，我們還是來看一些比較開放的相關問題，有興趣的讀者可以仔細思考一下下面的問題：
- 常用于分析的 OLAP 資料庫一般會使用什麼樣的資料結構存儲資料？為什麼？
- Redis 是如何對資料進行持久化存儲的？常見的資料結構都有什麼？
如果對文章中的内容有疑問或者想要了解更多軟體工程上一些設計決策背後的原因，可以在部落格下面留言，作者會及時回複本文相關的疑問并選擇其中合适的主題作為後續的内容。
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
推薦閱讀 點選标題可跳轉
項目中常用的 19 條 MySQL 優化
資料庫選擇需要考慮的 12 個問題
MySQL 用 limit 為什麼會影響性能？
看完本文有收獲？請轉發分享給更多人
關注「ImportNew」，提升Java技能
好文章，我在看❤️