這篇文章將為大家詳細講解有關(guān)MySQL索引采用B+樹結(jié)構(gòu)的原因有哪些，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)服務(wù)項目包括達州網(wǎng)站建設(shè)、達州網(wǎng)站制作、達州網(wǎng)頁制作以及達州網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，達州網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到達州省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

索引提高查詢效率，就像我們看的書，想要直接翻到某一章，是不是不用一頁一頁的翻，只需要看下目錄，根據(jù)目錄找到其所在的頁數(shù)即可。

在計算機中我們需要一種數(shù)據(jù)結(jié)構(gòu)來存儲這個目錄，常見數(shù)據(jù)結(jié)構(gòu)有哈希表，二叉查找樹，二叉平衡樹(AVL)，紅黑樹，那為什么Innodb和MyISAM選擇b+樹呢。

1. 哈希表

哈希表就是一個數(shù)組+鏈表，用下標0，1，2，3..... 表示其數(shù)據(jù)所在的位置。如果想要在哈希表中存放數(shù)據(jù)，首先用對這個數(shù)據(jù)進行散列算法（基本的就是取模運算），假如數(shù)組長度是13 ，進行模13之后是0-12，正好對應(yīng)的數(shù)據(jù)的下標，如果計算出的下標一樣的，就會在下標位置跟上鏈表。

缺點：

1. 利用hash存儲需要將所有的數(shù)據(jù)文件添加到內(nèi)存，比較消耗內(nèi)存空間。

2. hash的查找是等值查詢，速度很快，但是各個數(shù)據(jù)間沒有范圍規(guī)律，但在實際工作中更多的是范圍查詢，hash就不太合適了。

不能直接說mysql不使用哈希表，而是要根據(jù)存儲引擎來確定的，Memory存儲引擎使用的就是哈希表

2. 二叉查找樹

缺點：

1. 如圖，極端情況可能會出現(xiàn)傾斜的問題，最后變成鏈表結(jié)構(gòu)。

2. 造成樹節(jié)點過深，從而增加查找的IO，而現(xiàn)在IO就是查找的瓶頸

3. 二叉平衡樹-AVL

為了保持樹的平衡，避免出現(xiàn)數(shù)據(jù)傾斜，需要進行旋轉(zhuǎn)操作，通過左旋或者右旋最終保持最長子樹和最短子樹長度不能超過1，如果超過1就不是嚴格意義上AVL樹了

缺點：

1.當(dāng)數(shù)據(jù)量很大的時候，為了保持平衡，需要進行1-n次的旋轉(zhuǎn)，這個旋轉(zhuǎn)是比較浪費性能的，插入和刪除效率極低，查詢效率很高。

2. 只有兩個分支，數(shù)據(jù)量大的時候樹的深度依然很深。

4. 紅黑樹

最長子樹的不能超過最短子樹的2倍，通過變色和旋轉(zhuǎn)，在插入和查詢上做了平衡

紅黑樹是avl樹的變種，損失了部分查詢性能來提高插入性能。

缺點：

同樣是只有兩個分支，數(shù)據(jù)量大的時候深度依然會很深

以上三種二叉樹，隨著數(shù)據(jù)的增多，最終都會出現(xiàn)節(jié)點過多的情況，而且他們有且僅有2個分支，那么IO的次數(shù)一樣很多.

怎么解決僅有2個分支而且深度過深，這就有了B樹，增加分支

5. B-Tree

1. 首先不讀B減樹，讀B樹

2. 所有鍵值分布在整棵樹中。

3. 搜索有可能在非葉子結(jié)點結(jié)束，在關(guān)鍵字全集內(nèi)做一次查找，性能逼近二分查找。

4. 每個結(jié)點最多擁有m個子樹。

5. 根節(jié)點至少有2個子樹。

6. 分支節(jié)點至少擁有m/2棵子樹(除根節(jié)點和葉子節(jié)點外都是分支節(jié)點)。

7. 所有葉子節(jié)點都在同一層，每個節(jié)點最多可以有m-1個key,并且以升序排列

如上圖：（圖中只是畫出來一部分，實際上沒有限制的，不止p1,p2,p3）

每個節(jié)點占用一個磁盤塊，一個節(jié)點上有兩個升序排列的關(guān)鍵字和三個指向子樹根節(jié)點的指針，指針存儲的是子節(jié)點所在的磁盤塊地址。兩個關(guān)鍵詞劃分成的三個范圍域?qū)?yīng)三個指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點為例，關(guān)鍵字為16和34，p1指針指向的子樹的數(shù)據(jù)范圍小于16，p2指針指向的子樹的數(shù)據(jù)范圍為16-34，p3指針指向的子樹的數(shù)據(jù)范圍大于34。

查找關(guān)鍵字28的過程：

1. 根據(jù)根節(jié)點找到磁盤塊1，讀到內(nèi)存中。【第一次磁盤I/O操作】

2. 比較關(guān)鍵字28在區(qū)間(16，34)，找到磁盤塊1的指針p2。

3. 根據(jù)p2指針找到磁盤塊3，讀到內(nèi)存?！镜诙未疟PI/O操作】

4. 比較關(guān)鍵字28在區(qū)間(25，31)，找到磁盤塊3的指針p2。

5. 根據(jù)指針p2找到磁盤塊8，讀到內(nèi)存?！镜谌未疟PI/O操作】

6. 在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字28，結(jié)束。

缺點：

1. 每個節(jié)點都有key，同時包含data，而每個頁存儲空間是有限的，如果data很大的話會導(dǎo)致每個節(jié)點能存儲的key的數(shù)量變小。

2. 當(dāng)存儲的數(shù)據(jù)量很大的時候會導(dǎo)致深度變大，增加查詢磁盤的io次數(shù)，進而影響查詢性能。

6. B+樹

B+樹是在B樹的基礎(chǔ)上做的一種優(yōu)化，變化如下：

1. B+樹每個節(jié)點可以包含更多的節(jié)點，這個做的原因有兩個，第一個原因是為了降低樹的高度，第二個原因是將數(shù)據(jù)范圍變成多個區(qū)間，區(qū)間越多，數(shù)據(jù)檢索越快。

2. 非葉子節(jié)點只存儲key，葉子節(jié)點存儲key和數(shù)據(jù)。

3. 葉子節(jié)點兩兩指針互相連接(符合磁盤預(yù)讀的特性)，順序查詢性能更高。

如上圖： 在B+樹上有兩個頭指針，一個指向根節(jié)點，另一個指向關(guān)鍵字的最小葉子節(jié)點，而且所有葉子節(jié)點(及數(shù)據(jù)節(jié)點)之間是一種鏈式環(huán)結(jié)構(gòu)，因此可以對B+樹進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點開始的隨機查找。

InnoDB和MyISAM中索引上的差異

1. InnoDB-主鍵索引

葉子節(jié)點存儲的是具體的行數(shù)據(jù)

2. InnoDB-非主鍵索引

非主鍵索引的葉子節(jié)點存儲的是主鍵值（所以查詢數(shù)據(jù)基本要回表）

3. MyISAM

葉子節(jié)點存儲的是行數(shù)據(jù)的地址，額外需要一次尋址，多一次IO

關(guān)于“mysql索引采用B+樹結(jié)構(gòu)的原因有哪些”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。