免费观看又色又爽又黄的小说免费_美女福利视频国产片_亚洲欧美精品_美国一级大黄大色毛片

為什么MySQL索引要用B+樹,而不是B樹?

2021-02-26    分類: 網站建設

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

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

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

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

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

  1. 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.newbst.com/news27/103077.html

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

廣告

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

營銷型網站建設