Mysql索引原理-創(chuàng)新互聯(lián)

說(shuō)起Mysql就離不開(kāi)SQL優(yōu)化，說(shuō)起優(yōu)化就離不開(kāi)索引，那么什么是索引？為什么加了索引就可以快？那接下來(lái)我們就一起來(lái)探討一下索引相關(guān)的知識(shí)！

站在用戶(hù)的角度思考問(wèn)題，與客戶(hù)深入溝通，找到廣安網(wǎng)站設(shè)計(jì)與廣安網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶(hù)體驗(yàn)好的作品，建站類(lèi)型包括：做網(wǎng)站、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、網(wǎng)頁(yè)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋廣安地區(qū)。

一、數(shù)據(jù)結(jié)構(gòu)中常見(jiàn)的索引

【對(duì)這塊數(shù)據(jù)結(jié)構(gòu)了解的同學(xué)建議跳過(guò)本節(jié)】

1.二叉樹(shù)

說(shuō)起二叉樹(shù)，我們都知道每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)子結(jié)點(diǎn)，例如：

可以發(fā)現(xiàn)二叉樹(shù)很有規(guī)律，左子結(jié)點(diǎn)小于當(dāng)前結(jié)點(diǎn)，右子結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)。那這樣不是查詢(xún)起來(lái)很方便呢？二叉樹(shù)的性質(zhì)決定了它的時(shí)間復(fù)雜度為 Olog(n)，當(dāng)然，二叉樹(shù)的時(shí)間復(fù)雜度與它的插入順序有著，如果按升序或降序的方式插入數(shù)據(jù)，那么它的二叉樹(shù)的高度h就與結(jié)點(diǎn)個(gè)數(shù)相等了，此時(shí)復(fù)雜度就提高到了O(n)。

假如，數(shù)據(jù)庫(kù)使用二叉樹(shù)來(lái)做索引，此時(shí)需要插入1000條數(shù)據(jù)，我們來(lái)計(jì)算一下這樹(shù)的高度。（深度為k的二叉樹(shù)最少有k個(gè)結(jié)點(diǎn)，最多有2^k-1個(gè)結(jié)點(diǎn)）

2^10-1 ≈ 1000    此時(shí)樹(shù)的高度約為10
最差的情況，樹(shù)的高度為1000

樹(shù)的高度決定了查詢(xún)的效率，而二叉樹(shù)又會(huì)存在高度10~1000這么大的差距，很明顯它已經(jīng)不適合做我們的索引了！

2.平衡樹(shù)

前面把問(wèn)題擺出來(lái)了，二叉樹(shù)的高度很不穩(wěn)定，那我們能不能把高度穩(wěn)定一下呢？這就是平衡樹(shù)，它會(huì)根據(jù)插入的情況，動(dòng)態(tài)的調(diào)整二叉樹(shù)的高度（左右子樹(shù)的高度最多差1），比如：我們插入從10，9，8，，，1

看，我沒(méi)有騙你吧，它會(huì)根據(jù)插入的情況調(diào)整樹(shù)的高度，具體怎么調(diào)整的，我只簡(jiǎn)單說(shuō)明一下吧，畢竟不是本文的重點(diǎn)。

平衡樹(shù)的調(diào)整分四種情況：

LL、LR、RL、RR

這種情況很好理解

這種情況就是，先將5與6結(jié)點(diǎn)左旋轉(zhuǎn)，然后轉(zhuǎn)成了LL型，再右旋轉(zhuǎn)。
好了，另外兩種就不說(shuō)了，和這兩種的旋轉(zhuǎn)方式正好相反而已。

咳咳，回到正題，現(xiàn)在好了，平衡樹(shù)足以保證了樹(shù)的平衡，那么使用它來(lái)做索引有沒(méi)有 問(wèn)題呢？
假如我們有100000 條記錄，那么根據(jù)二叉樹(shù)的性質(zhì)，樹(shù)的高度最低約為2^16，也就是查找一個(gè)元素需要查找16次，有同學(xué)可能說(shuō)，嗯，查詢(xún)16次我可以接受了，那么假如插入或刪除數(shù)據(jù)呢？AVL樹(shù)的大缺點(diǎn)就是插入結(jié)點(diǎn)時(shí)，樹(shù)需要頻繁的旋轉(zhuǎn)調(diào)整結(jié)點(diǎn)，所以平衡樹(shù)也不太適合做索引。

3.紅黑樹(shù)

前面說(shuō)了平衡樹(shù)對(duì)二叉樹(shù)的要求，左右子樹(shù)的高度最多差1，插入數(shù)據(jù)稍有不慎就會(huì)造成平衡樹(shù)的轉(zhuǎn)換操作，而轉(zhuǎn)換又是非常耗時(shí)的一件事情。
而紅黑樹(shù)的出現(xiàn)就是為了避免平衡樹(shù)的頻繁轉(zhuǎn)換結(jié)點(diǎn)操作。紅黑樹(shù) 并不追求 完全平衡 它只要求部分結(jié)點(diǎn)達(dá)到平衡，降低了對(duì)旋轉(zhuǎn)的要求，從而提高了性能。先看下紅黑樹(shù)的定義吧！

*   每個(gè)結(jié)點(diǎn)要么是紅的要么是黑的。  
*   根結(jié)點(diǎn)是黑的。  
*   每個(gè)葉結(jié)點(diǎn)（葉結(jié)點(diǎn)即指樹(shù)尾端NIL指針或NULL結(jié)點(diǎn)）都是黑的。  
*   如果一個(gè)結(jié)點(diǎn)是紅的，那么它的兩個(gè)兒子都是黑的。  
*    對(duì)于任意結(jié)點(diǎn)而言，其到葉結(jié)點(diǎn)樹(shù)尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。 

插入或刪除元素時(shí)，也是需要維護(hù)紅黑樹(shù)結(jié)構(gòu)的，之所以索引也不使用紅黑樹(shù)主要是二叉樹(shù)保存大量結(jié)點(diǎn)的時(shí)候，會(huì)導(dǎo)致樹(shù)的高度不斷增加。比如1億個(gè)節(jié)點(diǎn)，樹(shù)的高度就會(huì)達(dá)到27層左右，而一般索引又是保存到磁盤(pán)中的，如果每次查詢(xún)都需要一次IO的話(huà)，那也就是需要27次IO操作，而每次IO操作都是非常耗時(shí)的。

4.B樹(shù)

平衡樹(shù)、紅黑樹(shù)都是二叉樹(shù)，當(dāng)二叉樹(shù)保存大量元素的時(shí)候會(huì)導(dǎo)致樹(shù)的高度不斷增高，那可不可以使用多叉樹(shù)呢？

先來(lái)看下B樹(shù)的定義：

1、B樹(shù)的組成
    關(guān)鍵字（可以理解為數(shù)據(jù)）
    指向孩子節(jié)點(diǎn)的指針

2、B樹(shù)的性質(zhì)：
* 若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則至少有2棵子樹(shù)
* 除根節(jié)點(diǎn)以外的所有非葉結(jié)點(diǎn)至少有 M/2 棵子樹(shù)，至多有 M 個(gè)子樹(shù)（關(guān)鍵字?jǐn)?shù)為子樹(shù)減一）
* 所有的葉子結(jié)點(diǎn)都位于同一層

5.B+樹(shù)

B+樹(shù)與B樹(shù)的區(qū)別主要在于：

* 節(jié)點(diǎn)的子樹(shù)數(shù)和關(guān)鍵字?jǐn)?shù)相同（B 樹(shù)是關(guān)鍵字?jǐn)?shù)比子樹(shù)數(shù)少一）
* 節(jié)點(diǎn)的關(guān)鍵字表示的是子樹(shù)中的大數(shù)，在子樹(shù)中同樣含有這個(gè)數(shù)據(jù)
* 葉子節(jié)點(diǎn)包含了全部數(shù)據(jù)，同時(shí)符合左小右大的順序

B+樹(shù)相比B樹(shù)的優(yōu)點(diǎn)再于：層級(jí)更低，葉子結(jié)點(diǎn)形成鏈表，范圍查詢(xún)方便；

二、Mysql中的B樹(shù)與B+樹(shù)

1.磁盤(pán)讀取原理

索引文件一般以文件的形式存在磁盤(pán)上面，索引檢索操作需要磁盤(pán)的IO，但是磁盤(pán)順序讀取的效率很高，所以在讀取的時(shí)候，磁盤(pán)往往不是按需讀取，而且每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤(pán)也會(huì)從這個(gè)位置開(kāi)始，順序向后讀取一定長(zhǎng)度的數(shù)據(jù)放入內(nèi)存。由于磁盤(pán)順序讀取的效率很高，因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高IO效率。預(yù)讀的長(zhǎng)度一般為頁(yè)的整數(shù)倍（頁(yè)是計(jì)算機(jī)管理存儲(chǔ)器的邏輯塊，操作系統(tǒng)往往將主存和磁盤(pán)存儲(chǔ)區(qū)分割為連續(xù)的大小相等的塊，每個(gè)存儲(chǔ)塊稱(chēng)為一頁(yè)，大小通常是4K）主存和磁盤(pán)以頁(yè)為單位交換數(shù)據(jù)。當(dāng)程序要讀取的數(shù)據(jù)不在主存中時(shí)，會(huì)觸發(fā)一個(gè)缺頁(yè)異常，此時(shí)系統(tǒng)會(huì)向磁盤(pán)發(fā)出讀盤(pán)信號(hào)，磁盤(pán)會(huì)找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁(yè)或幾頁(yè)載入內(nèi)存中，然后異常返回，程序繼續(xù)運(yùn)行

2.Innodb中的B+樹(shù)

Innodb中使用是B+樹(shù)作為索引，比如下圖中的主索引：

葉子結(jié)點(diǎn)包含了所以的結(jié)點(diǎn)，除了葉子結(jié)點(diǎn)之外，其它結(jié)點(diǎn)不包含值，而葉子結(jié)點(diǎn)包含具體的值

二級(jí)索引
Innodb中的二級(jí)索引，也是一棵B+樹(shù)，只是它的葉子結(jié)點(diǎn)指向的是主索引中的主鍵值，然后再去主索引中查找具體的值；

3.myISAM中的B+樹(shù)

MyISAM引擎使用B+樹(shù)作索引時(shí)，結(jié)構(gòu)與Innodb大致相同，只是它葉子結(jié)點(diǎn)存放的不是具體的記錄值，而是記錄的地址。

二級(jí)索引
一級(jí)索引中，MyISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址，而二級(jí)索引在結(jié)構(gòu)上沒(méi)有任何區(qū)別，二級(jí)索引也是直接指向記錄的地址。

文章題目：Mysql索引原理-創(chuàng)新互聯(lián)
URL分享：http://bm7419.com/article32/gjcpc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開(kāi)發(fā)、企業(yè)網(wǎng)站制作、標(biāo)簽優(yōu)化、關(guān)鍵詞優(yōu)化、網(wǎng)頁(yè)設(shè)計(jì)公司、做網(wǎng)站

廣告

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