共計 3741 個字符，預計需要花費 10 分鐘才能閱讀完成。
這篇文章主要介紹 MySQL 使用 B 樹的原因有哪些，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲在磁盤上。這樣的話，索引查找過程中就要產生磁盤 I / O 消耗，相對于內存存取，I/ O 存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤 I / O 操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤 I / O 的存取次數。下面先介紹內存和磁盤存取原理，然后再結合這些原理分析 B -/+Tree 作為索引的效率。
主存存取原理
目前計算機使用的主存基本都是隨機讀寫存儲器(RAM)，現代 RAM 的結構和存取原理比較復雜，這里本文拋卻具體差別，抽象出一個十分簡單的存取模型來說明 RAM 的工作原理。
從抽象角度看，主存是一系列的存儲單元組成的矩陣，每個存儲單元存儲固定大小的數據。每個存儲單元有唯一的地址，現代主存的編址規則比較復雜，這里將其簡化成一個二維地址：通過一個行地址和一個列地址可以唯一定位到一個存儲單元。上圖展示了一個 4 x 4 的主存模型。
主存的存取過程如下：
當系統需要讀取主存時，則將地址信號放到地址總線上傳給主存，主存讀到地址信號后，解析信號并定位到指定存儲單元，然后將此存儲單元數據放到數據總線上，供其它部件讀取。
寫主存的過程類似，系統將要寫入單元地址和數據分別放在地址總線和數據總線上，主存讀取兩個總線的內容，做相應的寫操作。
這里可以看出，主存存取的時間僅與存取次數呈線性關系，因為不存在機械操作，兩次存取的數據的“距離”不會對時間有任何影響，例如，先取 A0 再取 A1 和先取 A0 再取 D3 的時間消耗是一樣的。
磁盤存取原理
上文說過，索引一般以文件形式存儲在磁盤上，索引檢索需要磁盤 I / O 操作。與主存不同，磁盤 I / O 存在機械運動耗費，因此磁盤 I / O 的時間消耗是巨大的。
一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動(各個磁盤必須同步轉動)。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內容。磁頭不能轉動，但是可以沿磁盤半徑方向運動(實際是斜切向運動)，每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的(不過目前已經有多磁頭獨立技術，可不受此限制)。
盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。為了簡單起見，我們下面假設磁盤只有一個盤片和一個磁頭。
當需要從磁盤讀取數據時，系統會將數據邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁道，哪個扇區。為了讀取這個扇區的數據，需要將磁頭放到這個扇區上方，為了實現這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然后磁盤旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
局部性原理與磁盤預讀
由于存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤 I /O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節，磁盤也會從這個位置開始，順序向后讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：
當一個數據被用到時，其附近的數據也通常會馬上被使用。
所以，程序運行期間所需要的數據通常應當比較集中。
由于磁盤順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，因此對于具有局部性的程序來說，預讀可以提高 I / O 效率。
預讀的長度一般為頁 (page) 的整倍數。頁是計算機管理存儲器的邏輯塊，硬件及操作系統往往將主存和磁盤存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統中，頁得大小通常為 4k)，主存和磁盤以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁盤發出讀盤信號，磁盤會找到數據的起始位置并向后連續讀取一頁或幾頁載入內存中，然后異常返回，程序繼續運行。
B-/+Tree 索引的性能分析
到這里終于可以分析 B -/+Tree 索引的性能了。
上文說過一般使用磁盤 I / O 次數評價索引結構的優劣。先從 B -Tree 分析，根據 B -Tree 的定義，可知檢索一次最多需要訪問 h 個節點。數據庫系統的設計者巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣每個節點只需要一次 I / O 就可以完全載入。為了達到這個目的，在實際實現 B -Tree 還需要使用如下技巧：
每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個 node 只需一次 I /O。
B-Tree 中一次檢索最多需要 h - 1 次 I /O(根節點常駐內存)，漸進復雜度為 (?)= ()。
一般實際應用中，出度 d 是非常大的數字，通常超過 100，因此 h 非常小(通常不超過 3)。(h 表示樹的高度 出度 d 表示的是樹的度，即樹中各個節點的度的最大值)
綜上所述，用 B -Tree 作為索引結構效率是非常高的。
而紅黑樹這種結構，h 明顯要深的多。由于邏輯上很近的節點 (父子) 物理上可能很遠，無法利用局部性，所以紅黑樹的 I / O 漸進復雜度也為 O(h)，效率明顯比 B -Tree 差很多。
上文還說過，B+Tree 更適合外存索引，原因和內節點出度 d 有關。從上面分析可以看到，d 越大索引的性能越好，而出度的上限取決于節點內 key 和 data 的大小：
= (/( + +))
floor 表示向下取整。由于 B +Tree 內節點去掉了 data 域，因此可以擁有更大的出度，擁有更好的性能。
在 MySQL 中，索引屬于存儲引擎級別的概念，不同存儲引擎對索引的實現方式是不同的，本文主要討論 MyISAM 和 InnoDB 兩個存儲引擎的索引實現方式。
MyISAM 非聚簇索引
MyISAM 引擎使用 B +Tree 作為索引結構，葉節點的 data 域存放的是數據記錄的地址。
這里設表一共有三列，假設我們以 Col1 為主鍵，則上圖是一個 MyISAM 表的主索引 (Primary key) 示意。可以看出 MyISAM 的索引文件僅僅保存數據記錄的地址。在 MyISAM 中，主索引和輔助索引 (Secondary key) 在結構上沒有任何區別，只是主索引要求 key 是唯一的，而輔助索引的 key 可以重復。
同樣也是一棵 B + 樹，data 域保存數據記錄的地址。因此，MyISAM 中索引檢索的算法為首先按照 B +Tree 搜索算法搜索索引，如果指定的 Key 存在，則取出其 data 域的值，然后以 data 域的值為地址，讀取相應數據記錄。
MyISAM 的索引方式也叫做“非聚集”的，之所以這么稱呼是為了與 InnoDB 的聚集索引區分。
InnoDB 索引實現
雖然 InnoDB 也使用 B +Tree 作為索引結構，但具體實現方式卻與 MyISAM 截然不同。
第一個重大區別是 InnoDB 的數據文件本身就是索引文件。從上文知道，MyISAM 索引文件和數據文件是分離的，索引文件僅保存數據記錄的地址。而在 InnoDB 中，表數據文件本身就是按 B +Tree 組織的一個索引結構，這棵樹的葉節點 data 域保存了完整的數據記錄。這個索引的 key 是數據表的主鍵，因此 InnoDB 表數據文件本身就是主索引。
主索引 (Primary Key)
InnoDB 主索引 (同時也是數據文件) 可以看到葉節點包含了完整的數據記錄。這種索引叫做聚集索引。因為 InnoDB 的數據文件本身要按主鍵聚集，所以 InnoDB 要求表必須有主鍵(MyISAM 可以沒有)，如果沒有顯式指定，則 MySQL 系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則 MySQL 自動為 InnoDB 表生成一個隱含字段作為主鍵，這個字段長度為 6 個字節，類型為長整型。
輔助索引(Secondary Key)
第二個與 MyISAM 索引的不同是 InnoDB 的輔助索引 data 域存儲相應記錄主鍵的值而不是地址。換句話說，InnoDB 的所有輔助索引都引用主鍵作為 data 域。
這里以英文字符的 ASCII 碼作為比較準則。聚集索引這種實現方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。
了解不同存儲引擎的索引實現方式對于正確使用和優化索引都非常有幫助，例如知道了 InnoDB 的索引實現后，就很容易明白為什么不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。
再例如，用非單調的字段作為主鍵在 InnoDB 中不是個好主意，因為 InnoDB 數據文件本身是一棵 B +Tree，非單調的主鍵會造成在插入新記錄時數據文件為了維持 B +Tree 的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。
以上是“MySQL 使用 B 樹的原因有哪些”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注丸趣 TV 行業資訊頻道！
