MySQL中 B-Tree和B+Tree的區(qū)別是什么

這篇文章給大家介紹MySQL中 B-Tree和B+Tree的區(qū)別是什么，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

B-Tree 的節(jié)點是一個二元數組 [key,data]，key 是記錄的鍵，data 是鍵對應的數據，B-Tree中的每個節(jié)點根據實際情況可以包含大量的關鍵字信息和分支，每個節(jié)點的每個 key 左右各有一個指針，非葉子節(jié)點的指針分別指向下一層的節(jié)點，葉子節(jié)點的指針為 null，如下圖：

要查找值的時候，會先從根節(jié)點開始查找，根節(jié)點的每個 key 有左右兩個指針，可以通過這兩個指針訪問下一層節(jié)點。每次查找都會將查找值與 key 值進行比較，根據比較結果找到合適的指針進入下一層節(jié)點，最終，如此重復，最終找到對應的值或者值不存在.

補充下磁盤的知識，系統從磁盤讀取數據到內存時是以磁盤塊（block）為基本單位的，位于同一個磁盤塊中的數據會被一次性讀取出來，而不是需要什么取什么。

InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB，可通過參數innodb_page_size將頁的大小設置為4K、8K、16K，在MySQL中可通過如下命令查看頁的大?。?/p>

mysql> show variables like 'innodb_page_size'

而系統一個磁盤塊的存儲空間往往沒有這么大，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達到頁的大小16KB。InnoDB在把磁盤數據讀入到磁盤時會以頁為基本單位，在查詢數據時如果一個頁中的每條數據都能有助于定位數據記錄的位置，這將會減少磁盤I/O次數，提高查詢效率。

B+Tree是在B-Tree基礎上的一種優(yōu)化，使其更適合實現外存儲索引結構，InnoDB存儲引擎就是用B+Tree實現其索引結構。

B-Tree結構每個節(jié)點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節(jié)點（即一個頁）能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上，而非葉子節(jié)點上只存儲key值信息，這樣可以大大加大每個節(jié)點存儲的key值數量，降低B+Tree的高度。

B+Tree 節(jié)點是 B-Tree 的變種，相對于 B-Tree 而言 B+Tree 有如下不同：

非葉子節(jié)點只存儲鍵值信息。

所有葉子節(jié)點之間都有一個鏈指針。

數據記錄都存放在葉子節(jié)點中。

關于MySQL中 B-Tree和B+Tree的區(qū)別是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。