為什么MySQL索引要用B+樹，而不是B樹？

一個面試題：InnoDB 一棵 B+ 樹可以存放多少行數據?這個問題的簡單回答是：約 2 千萬。

我們先將數據記錄按主鍵進行排序，分別存放在不同的頁中(為了便于理解我們這里一個頁中只存放 3 條記錄，實際情況可以存放很多)。

除了存放數據的頁以外，還有存放鍵值+指針的頁，如圖中 page number=3 的頁，該頁存放鍵值和指向數據頁的指針，這樣的頁由 N 個鍵值+指針組成。

當然它也是排好序的。這樣的數據組織形式，我們稱為索引組織表。

現在來看下，要查找一條數據，怎么查?如：

 select * from user where id=5;  
							

這里 id 是主鍵，我們通過這棵 B+ 樹來查找，首先找到根頁，你怎么知道 user 表的根頁在哪呢?

其實每張表的根頁位置在表

接下來我們用 hexdump 工具，查看表

總結

lineitem 表的數據行數為 600 多萬，B+ 樹高度為 3，customer 表數據行數只有 15 萬，B+ 樹高度也為 3。

可以看出盡管數據量差異較大，這兩個表樹的高度都是 3。換句話說這兩個表通過索引查詢效率并沒有太大差異，因為都只需要做 3 次 IO。

那么如果有一張表行數是一千萬，那么他的 B+ 樹高度依舊是 3，查詢效率仍然不會相差太大。region 表只有 5 行數據，當然他的 B+ 樹高度為 1。

最后回顧一道 MySQL 面試題：為什么 MySQL 的索引要使用 B+ 樹而不是其他樹形結構?比如 B 樹?現在這個問題的復雜版本可以參考本文。

他的簡單版本回答是：因為 B 樹不管葉子節點還是非葉子節點，都會保存數據，這樣導致在非葉子節點中能保存的指針數量變少(有些資料也稱為扇出)。

指針少的情況下要保存大量數據，只能增加樹的高度，導致 IO 操作變多，查詢性能變低。

本文從一個問題出發，逐步介紹了 InnoDB 索引組織表的原理、查詢方式，并結合已有知識，回答該問題，結合實踐來證明。

當然為了表述簡單易懂，文中忽略了一些細枝末節，比如一個頁中不可能所有空間都用于存放數據，它還會存放一些少量的其他字段比如 page level，index number 等等。

另外還有頁的填充因子也導致一個頁不可能全部用于保存數據。關于二級索引數據存取方式可以參考 MySQL 相關書籍，他的要點是結合主鍵索引進行回表查詢。

網頁題目：為什么MySQL索引要用B+樹，而不是B樹？
新聞來源：http://m.kartarina.com/news27/103077.html

成都網站建設公司_創新互聯，為您提供動態網站、微信公眾號、網站設計公司、網站改版、網站排名、建站公司

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯