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

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

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

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

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

現(xiàn)在來看下，要查找一條數(shù)據(jù)，怎么查?如：

 select * from user where id=5;  
							

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

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

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

總結

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

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

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

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

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

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

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

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

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

文章名稱：為什么MySQL索引要用B+樹，而不是B樹？
網站URL：http://m.kartarina.com/news/103077.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、軟件開發(fā)、品牌網站設計、App開發(fā)、關鍵詞優(yōu)化、響應式網站

廣告

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