概述

要描述清楚B+樹,得先了解二叉查找數,平衡二叉樹.

二叉查找樹

這里寫圖片描述

任意節點,它的左子樹如果不為空,那么左子樹上所有節點的值都小于根節點的值；

任意節點,他的右子樹如果不為空,那么右子樹上的所有節點的值大于根節點的值.

這個特性給查找帶來了方便,如上圖,要找key=3的鍵值,只要從5這個節點左子樹進行遞歸查找即可,右子樹的節點可以完全不理會.

平衡二叉樹

二叉查找樹有些缺陷,因為它對樹的左右子樹的高度沒有任何限制,極端的情況下會出現如下圖的類似鏈表的情況：

這里寫圖片描述

這種二叉查找樹對查詢沒任何好處的.所以有必要將樹節點的左右子樹的高度做一下限制,盡量堅持平衡.

二叉平衡樹 圖一

這里寫圖片描述

二叉查找樹 圖二

這里寫圖片描述

二叉平衡樹要求節點的左右子樹的高度不要相差超過1,像圖二中的6這個節點,它的左子樹的高度是4,右子樹的高度是2,相差超過了1,不具備平衡二叉樹的特性.

由二叉平衡樹的特性可以看到,查詢的效率同樣很高,同時又避免了二叉查找樹出現鏈表那種極端情況.

B+樹

圖三

這里寫圖片描述

B+樹有幾個特點：

1、是多叉而不是二叉了,使用多叉的目的是降低樹的高度;

2、每個節點不再只是存儲一個key了,可以存儲多個key；

3、非葉子節點存儲key,葉子節點存儲key和數據.

4、葉子節點兩兩相連,為順序查詢提供了贊助

Mysql為什么選擇B+樹

1、B+樹的非葉子節點只是存儲key,占用空間非常小,因此每一層的節點能索引到的數據范圍更加的廣.換句話說,每次IO操作可以觀看更多的數據；

2、葉子節點兩兩相連,符合磁盤的預讀特性.如圖三中存儲50和55的葉子節點,它有個指針指向了60和62這個葉子節點,那么當我們從磁盤讀取50和55對應的數據的時候,由于磁盤的預讀特性,會順便把60和62對應的數據讀取出來.這個時候屬于順序讀取,而不是磁盤尋道了,加快了速度.

3、支持范圍查詢,而且部分范圍查詢非常高效,原因是數據都是存儲在葉子節點這一層,并且有指針指向其他葉子節點,這樣范圍查詢只需要遍歷葉子節點這一層,無需整棵樹遍歷.

Mysql 索引簡單描述

innodb存儲引擎

自增主鍵索引

自增主鍵索引就是使用了B+數,索引文件同時也是數據文件,存儲了整張表的數據.也就是說,平時我們執行sql依照主鍵查詢的時候,那么只需要從這個索引文件獲取數據即可.這種索引也叫聚集索引 ,原因是所有數據是依照主鍵聚集的.

輔助索引(非自增主鍵索引,也可以叫非聚集索引)

這種索引文件的葉子節點存儲了鍵值和書簽.鍵值說的就是列的值,書簽就是對應記錄的主鍵的值,如果依照某個輔助索引來查詢數據的時候,如果沒有用到覆蓋索引,那么就得分兩步走：

1、先從輔助索引文件中獲取到數據對應的主鍵；

2、根據主鍵從聚集索引中獲取真實數據.

MyISAM存儲引擎

MyISAM引擎使用B+Tree作為索引結構,葉節點的data域存放的是數據記錄的地址.這種稱為非聚集索引,這個命名其實是對應上面innodb的叫法罷了.

1、具有1-5工作經驗的,面對目前流行的技術不知從何下手,需要突破技術瓶頸的可以加群.

2、在公司待久了,過得很安適,但跳槽時面試碰壁.需要在短時間內進修、跳槽拿高薪的可以加群.

3、如果沒有工作經驗,但基礎非常扎實,對java工作機制,常用設計思想,常用java開發框架掌握熟練的,可以加群.

4、覺得本身很牛B,一般需求都能搞定.但是所學的知識點沒有系統化,很難在技術領域繼續突破的可以加群.

5. 群號：高級架構群 647631030備注好信息!

6.阿里Java高級架構師直播講解知識點,分享知識,多年工作經驗的梳理和總結,帶著大家全面、科學地建立本身的技術體系和技術認知!