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

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

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

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

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

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

 select * from user where id=5;  
							

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

其實(shí)每張表的根頁位置在表

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

總結(jié)

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

可以看出盡管數(shù)據(jù)量差異較大，這兩個(gè)表樹的高度都是 3。換句話說這兩個(gè)表通過索引查詢效率并沒有太大差異，因?yàn)槎贾恍枰?3 次 IO。

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

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

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

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

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

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

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

文章名稱：為什么MySQL索引要用B+樹，而不是B樹？
網(wǎng)站URL：http://muchs.cn/news/103077.html

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

廣告

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