專注於Java領域優質技術號，歡迎關注

B-樹

B-樹,這裡的 B 表示 balance( 平衡的意思),B-樹是一種多路自平衡的搜索樹。

它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節點有更多的子節點。

下圖是 B-樹的簡化圖：

B-樹

B-樹有如下特點:

• 所有鍵值分佈在整顆樹中；
• 任何一個關鍵字出現且只出現在一個結點中；
• 搜索有可能在非葉子結點結束；
• 在關鍵字全集內做一次查找,性能逼近二分查找；

B+ 樹

B+樹是B-樹的變體，也是一種多路搜索樹, 它與 B- 樹的不同之處在於：

• 所有關鍵字存儲在葉子節點出現，內部節點（非葉子節點）並不存儲真正的 data
• 為所有葉子結點增加了一個鏈指針

簡化 B+樹 如下圖：

B+樹

為什麼使用B-/B+ 樹

紅黑樹等數據結構也可以用來實現索引，但是文件系統及數據庫系統普遍採用B-/+Tree作為索引結構。

MySQL 是基於磁盤的數據庫系統,索引往往以索引文件的形式存儲的磁盤上，索引查找過程中就要產生磁盤I/O消耗，相對於內存存取，I/O存取的消耗要高几個數量級,索引的結構組織要儘量減少查找過程中磁盤I/O的存取次數。

為什麼使用B-/+Tree，還跟磁盤存取原理有關。

局部性原理與磁盤預讀

由於磁盤的存取速度與內存之間效率差異比較大，為了提高效率，要儘量減少磁盤I/O，磁盤往往不是嚴格按需讀取，而是每次都會預讀，磁盤讀取完需要的數據，會順序向後讀一定長度的數據放入內存。而這樣做的理論依據是計算機科學中著名的局部性原理：

當一個數據被用到時，其附近的數據也通常會馬上被使用，程序運行期間所需要的數據通常比較集中

由於磁盤順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，因此對於具有局部性的程序來說，預讀可以提高I/O效率.預讀的長度一般為頁(page)的整倍數。

MySQL(使用InnoDB引擎),將記錄按照頁的方式進行管理,每頁大小默認為16K(這個值可以修改).linux 默認頁大小為4K

使用B+樹的優勢

• B+樹更適合外部存儲,由於內節點無 data 域,一個結點可以存儲更多的內結點,每個節點能索引的範圍更大更精確,也意味著 B+樹單次磁盤IO的信息量大於B-樹,I/O效率更高。
• Mysql是一種關係型數據庫，區間訪問是常見的一種情況，B+樹葉節點增加的鏈指針,加強了區間訪問性，可使用在範圍區間查詢等，而B-樹每個節點 key 和 data 在一起，則無法區間查找。

MySQL索引實現

MySQL存在多種存儲引擎的選擇，不同存儲引擎對索引的實現是不同的，下面對常見存儲引擎InnoDB和MyISAM存儲引擎的索引實現進行討論

使用B+樹作為索引結構，數據文件本身就是索引文件。數據文件按照B+樹的結構進行組織，葉節點的data域存儲完整的數據記錄，索引的key即為表的主鍵。

下圖為 主鍵索引 示意圖。

InnoDB主索引

可以看到葉節點包含了完整的數據記錄，這種索引叫做聚集索引，聚集索引使得搜索主鍵非常高效。

因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形。

下圖為輔助索引示意圖，InnoDB輔助索引的data域存儲的是主鍵的值。搜索輔助索引需要先根據輔助索引獲取到主鍵值，再根據主鍵到主索引中獲取到對應的數據記錄。

InnoDB輔助索引

MyISAM索引實現

MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是數據記錄的地址。下圖是MyISAM索引的原理圖：

MyISAM主索引

假設我們以Col1為主鍵，可以看出MyISAM的索引文件僅僅保存數據記錄的地址。

在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何區別，只是主索引要求key是唯一的，而輔助索引的key可以重複。

如果我們在Col2上建立一個輔助索引，則此索引的結構如下圖所示：

MyISAM輔助索引

鏈接：https://www.jianshu.com/p/9bd572b0a0d4

閱讀更多 Java技術架構 的文章

關鍵字: MySQL 關鍵字 結點