為什麼 MySQL 使用 B+ 樹?| StoneDB資料庫觀察

語言: CN / TW / HK

為什麼 MySQL 使用 B+ 樹是面試中經常會出現的問題,很多人對於這個問題可能都有一些自己的理解,但是多數的回答都不夠完整和準確,大多數人都只會簡單說一下 B+ 樹和 B 樹的區別,但是都沒有真正回答 MySQL 為什麼選擇使用 B+ 樹這個問題,我們在這篇文章中就會深入分析 MySQL 選擇 B+ 樹背後的一些原因。

概述

首先需要澄清的一點是,MySQL 跟 B+ 樹沒有直接的關係,真正與 B+ 樹有關係的是 MySQL 的預設儲存引擎 InnoDB,MySQL 中儲存引擎的主要作用是負責資料的儲存和提取,除了 InnoDB 之外,MySQL 中也支援 MyISAM 作為表的底層儲存引擎。

我們在使用 SQL 語句建立表時就可以為當前表指定使用的儲存引擎,你能在 MySQL 的文件 Alternative Storage Engines 中找到它支援的全部儲存引擎,例如:MyISAMCSVMEMORY 等,然而預設情況下,使用如下所示的 SQL 語句來建立表就會得到 InnoDB 儲存引擎支撐的表:

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

想要詳細瞭解 MySQL 預設儲存引擎的讀者,可以通過之前的文章 『淺入淺出』MySQL 和 InnoDB 瞭解包括 InnoDB 儲存方式、索引和鎖等內容,我們在這裡主要不會介紹 InnoDB 相關的過多內容。

我們今天最終將要分析的問題其實還是,為什麼 MySQL 預設的儲存引擎 InnoDB 會使用 MySQL 來儲存資料,相信對 MySQL 稍微有些瞭解的人都知道,無論是表中的資料(主鍵索引)還是輔助索引最終都會使用 B+ 樹來儲存資料,其中前者在表中會以 <id, row> 的方式儲存,而後者會以 <index, id> 的方式進行儲存,這其實也比較好理解:

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

  • 在輔助索引中,索引中的幾個列構成了鍵,我們能夠通過索引中的列找到 id,如果有需要的話,可以再通過 id 找到當前資料行的全部內容;

對於 InnoDB 來說,所有的資料都是以鍵值對的方式儲存的,主鍵索引和輔助索引在儲存資料時會將 idindex 作為鍵,將所有列和 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 完成以下的一些工作:

  • 通過 INSERTUPDATEDELETE 語句對錶中的資料進行增加、修改和刪除;

  • 通過 UPDATEDELETE 語句對符合條件的資料進行批量的刪除;

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

  • 通過 SELECT 語句在表中查詢符合某些條件的記錄並根據某些欄位排序;

  • 通過 SELECT 語句查詢表中資料的行數;

  • 通過唯一索引保證表中某個欄位或者某幾個欄位的唯一性;

如果我們使用 B+ 樹作為底層的資料結構,那麼所有隻會訪問或者修改一條資料的 SQL 的時間複雜度都是 O(log n),也就是樹的高度,但是使用雜湊卻有可能達到 O(1) 的時間複雜度,看起來是不是特別的美好。但是當我們使用如下所示的 SQL 時,雜湊的表現就不會這麼好了:

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'

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

使用 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 才能找到所有滿足條件的資料行:

  1. 載入根節點所在的頁,發現根節點的第一個元素是 6,大於 4;

  2. 通過根節點的指標載入左子節點所在的頁,遍歷頁面中的資料,找到 5;

  3. 重新載入根節點所在的頁,發現根節點不包含第二個元素;

  4. 通過根節點的指標載入右子節點所在的頁,遍歷頁面中的資料,找到 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

如果您對我們的原始碼感興趣,歡迎到我們的 GitHub 程式碼倉庫閱讀檢視,覺得不錯記得點個 Star 哦~

StoneDB 程式碼倉庫

https://github.com/stoneatom/stonedb

StoneDB 社群官網

https://stonedb.io/


可掃碼新增小助手

加入 StoneDB 開源社群使用者群

討論交流,共同進步


StoneDB 原始碼解讀系列|Tianmu 引擎工具類模組原始碼詳解(一)

帶你來吃瓜!Andy Pavlo教授帶您一文回顧資料庫的2022年

穩紮穩打,堅定前行 | 一文帶你回顧 StoneDB 的 2022 年

哪篇論文宣佈了 HTAP 資料庫的誕生?| StoneDB學術分享會#5

列存引擎 Tianmu 如何實現 Delete?| StoneDB 研發分享 #3

StoneDB 首席架構師李浩:如何選擇一款 HTAP 產品?

子查詢優化之 Semi-join 優化 | StoneDB 研發分享 #2


本文分享自微信公眾號 - StoneDB(StoneDB2021)。
如有侵權,請聯絡 [email protected] 刪除。
本文參與“OSC源創計劃”,歡迎正在閱讀的你也加入,一起分享。