朗讀Mysql索引為什麼要用B+樹，而不用紅黑樹第Mysql索引為什麼要用B+樹，而不用紅黑樹

《Mysql索引為什麼要用B+樹，而不用紅黑樹》
凱騰凱當然紅黑樹為了維持自身的平衡性，會存在變色和旋轉。B-樹
B樹是利用磁盤塊的特性來構建的樹結構，每個磁盤塊一個節點，每個節點包含很多的關鍵字，數的關鍵字增多後數的層級就會比二叉樹更少，減少了查詢的次數和複雜度。其次還利用了磁盤預讀的特性，把每個節點作為一個頁（磁盤頁大小為4K），每個節點一次I/O操作就可以完全載入。但是由於每個節點關鍵字還和關鍵字記錄指針綁定到一起，導致一個節點不能夠存儲過多的關鍵字，所以B+樹就出現了。B+樹B+樹每個非葉子節點存儲關鍵字和父節點指針，關鍵字記錄的指針存儲在葉子節點，並且葉子節點有序。這樣每個非葉子節點能夠存儲更多的關鍵字，樹的層級也就下降了，查詢數據的速率變快。
為什麼要選用B+樹，而不是紅黑樹呢？B+樹只有葉節點存放數據，其餘節點用來索引，而B-樹是每個索引節點都會有Data域。所以從Mysql（Inoodb）的角度來看，B+樹是用來充當索引的，一般來說索引非常大，尤其是關系型數據庫這種數據量大的索引能達到億級別，所以為了減少內存的占用，索引也會被存儲在磁盤上。那麼Mysql如何衡量查詢效率呢？– 磁盤IO次數。 B-樹/B+樹 的特點就是每層節點數目非常多，層數很少，目的就是為了減少磁盤IO次數，但是B-樹的每個節點都有data域（指針），這無疑增大了節點大小，說白了增加了磁盤IO次數（磁盤IO一次讀出的數據量大小是固定的，單個數據變大，每次讀出的就少，IO次數增多，一次IO多耗時），而B+樹除了葉子節點其它節點並不存儲數據，節點小，磁盤IO次數就少。這是優點之一。另一個優點是： B+樹所有的Data域在葉子節點，一般來說都會進行一個優化，就是將所有的葉子節點用指針串起來。這樣遍曆葉子節點就能獲得全部數據，這樣就能進行區間訪問啦。在數據庫中基於範圍的查詢是非常de頻繁的，而B樹不支持這樣的遍曆操作紅黑樹基本都是存儲在內存中才會使用的數據結構。在大規模數據存儲的時候，紅黑樹往往出現由於樹的深度過大而造成磁盤IO讀寫過於頻繁，進而導致效率低下的情況。磁盤IO代價主要花費在查找所需的柱面上，樹的深度過大會造成磁盤IO頻繁讀寫。根據磁盤查找存取的次數往往由樹的高度所決定，所以，只要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度，B樹可以有多個子女，從幾十到上千，可以降低樹的高度。Mysql的聚集索引在MySQL的Innodb存儲引擎下主鍵索引稱為聚集索引，列索引稱為輔助索引，二級索引的B+樹的非葉子節點存儲的數據指針是聚集索引的主鍵。
如上圖中，id主鍵索引的葉子節點的數據區保存的就是真實的數據，在通過索引進行檢索的時候，命中葉子節點，就可以直接從葉子節點中取出行數據。主鍵索引的葉子節點保存的是真正的數據。而輔助索引葉子節點的數據區保存的是主鍵索引關鍵字的值。假如要查詢name = C 的數據，其搜索過程如下：先在輔助索引中通過C查詢最後找到主鍵id = 9。然後在主鍵索引中搜索id為9的數據，最終在主鍵索引的葉子節點中獲取到真正的數據。所以通過輔助索引進行檢索，需要檢索兩次索引。為什麼這樣設計呢？原因就是：如果和MyISAM一樣在主鍵索引和輔助索引的葉子節點中都存放數據行指針，一旦數據發生遷移，則需要去重新組織維護所有的索引。
我是凱騰凱，互聯網浪潮下一枚苟且偷生的程序仔
《Mysql索引為什麼要用B+樹，而不用紅黑樹》完，請繼續朗讀精采文章。
喜歡 小編的世界 e4to.com，請記得按讚、收藏及分享！