mysql索引采用B+樹結(jié)構(gòu)的原因有哪些

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

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

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

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

1. 哈希表

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

缺點(diǎn)：

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

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

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

2. 二叉查找樹

缺點(diǎn)：

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

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

3. 二叉平衡樹-AVL

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

缺點(diǎn)：

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

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

4. 紅黑樹

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

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

缺點(diǎn)：

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

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

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

5. B-Tree

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

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

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

4. 每個(gè)結(jié)點(diǎn)最多擁有m個(gè)子樹。

5. 根節(jié)點(diǎn)至少有2個(gè)子樹。

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

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

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

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

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

1. 根據(jù)根節(jié)點(diǎn)找到磁盤塊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é)束。

缺點(diǎn)：

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

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

6. B+樹

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

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

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

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

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

InnoDB和MyISAM中索引上的差異

1. InnoDB-主鍵索引

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

2. InnoDB-非主鍵索引

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

3. MyISAM

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

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

網(wǎng)站題目：mysql索引采用B+樹結(jié)構(gòu)的原因有哪些
網(wǎng)站鏈接：http://muchs.cn/article10/jojjdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、營(yíng)銷型網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、網(wǎng)站設(shè)計(jì)公司、外貿(mào)網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)