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

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

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

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

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

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

 select * from user where id=5;  
							

這里 id 是主鍵，我們通過(guò)這棵 B+ 樹(shù)來(lái)查找，首先找到根頁(yè)，你怎么知道 user 表的根頁(yè)在哪呢?

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

接下來(lái)我們用 hexdump 工具，查看表

總結(jié)

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

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

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

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

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

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

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

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

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

網(wǎng)頁(yè)題目：為什么MySQL索引要用B+樹(shù)，而不是B樹(shù)？
新聞來(lái)源：http://muchs.cn/news27/103077.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、微信公眾號(hào)、網(wǎng)站設(shè)計(jì)公司、網(wǎng)站改版、網(wǎng)站排名、建站公司

廣告

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