MySQL(三)MySQL索引原理
數(shù)據(jù)庫(kù)索引，是數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）中一個(gè)排序的數(shù)據(jù)結(jié)構(gòu)，以協(xié)助快速查詢、更新數(shù)據(jù)庫(kù)表中數(shù)據(jù)。
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?-----維基百科對(duì)數(shù)據(jù)庫(kù)索引的定義
目錄
索引類型
索引結(jié)構(gòu)
二分查找
二叉查找樹(shù)（BST Binary Search Tree）
平衡二叉樹(shù)（AVL Tree)
多路平衡查找樹(shù)（B Tree）
加強(qiáng)版多路平衡查找樹(shù)（B+樹(shù)）
總結(jié)一下InnoDB中B+樹(shù)的優(yōu)點(diǎn)
不同存儲(chǔ)引擎的索引結(jié)構(gòu)
InnoDB
MyISAM
拿漢語(yǔ)字典的目錄頁(yè)（索引）打比方，我們可以按拼音、筆畫(huà)、偏旁部首等排序的目錄（索引）快速查找到需要的字。
索引類型
在InnoDB 里面，索引類型有三種，普通索引、唯一索引（主鍵索引是特殊的唯一索引）、全文索引。
普通（Normal）索引：也叫非唯一索引，是最普通的索引，沒(méi)有任何的限制。
唯一（Unique）索引：唯一索引要求鍵值不能重復(fù)。另外需要注意的是，主鍵索引是一種特殊的唯一索引，它還多了一個(gè)限制條件，要求鍵值不能為空。主鍵索引用primay key創(chuàng)建。
全文（Fulltext）索引：針對(duì)比較大的數(shù)據(jù)，比如我們存放的是消息內(nèi)容，有幾KB的數(shù)據(jù)的這種情況，如果要解決like查詢效率低的問(wèn)題，可以創(chuàng)建全文索引。只有文本類型的字段才可以創(chuàng)建全文索引，比如char、varchar、text。
MyISAM和InnoDB都支持全文索引。
索引結(jié)構(gòu)
二分查找
對(duì)于提高查詢效率的辦法，最常見(jiàn)的就是二分查找法，這在生活中也有非常多的應(yīng)用。
每一次，我們都把候選數(shù)據(jù)縮小了一半。對(duì)于已經(jīng)排序過(guò)的數(shù)據(jù)，采用這種方式效率比較高。
如果考慮以有序數(shù)組作為索引的數(shù)據(jù)結(jié)構(gòu)，對(duì)于等值查詢和比較查詢效率確實(shí)會(huì)比較高，但是在更新數(shù)據(jù)(刪除，新增)的時(shí)候可能需要挪動(dòng)大量的數(shù)據(jù)（改變其index），所以只適合用來(lái)保存靜態(tài)的數(shù)據(jù)。
為了對(duì)于頻繁的插入/刪除也有比較高的效率，就需要采用鏈表來(lái)實(shí)現(xiàn)。如果是簡(jiǎn)單的單鏈表，那么它的查找效率是比較差的。
想要兼具數(shù)組和鏈表的優(yōu)勢(shì)，就需要一個(gè)新的數(shù)據(jù)結(jié)構(gòu)----二叉查找樹(shù)
二叉查找樹(shù)（BST Binary Search Tree）
二叉查找樹(shù)就是滿足 : 左子樹(shù)所有的節(jié)點(diǎn)都小于父節(jié)點(diǎn)，右子樹(shù)所有的節(jié)點(diǎn)都大于父節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，將其投影到平面上以后，就是一個(gè)有序的線性表。
二叉查找樹(shù)既能夠?qū)崿F(xiàn)快速查找，又能夠?qū)崿F(xiàn)快速插入。
但是二叉查找樹(shù)有一個(gè)問(wèn)題：它的查找耗時(shí)是和這棵樹(shù)的深度相關(guān)的，在最壞的情況下，根節(jié)點(diǎn)為最大或者最小的時(shí)候會(huì)變成斜樹(shù)，也就是單鏈表，時(shí)間復(fù)雜度會(huì)退化成O(n)
因?yàn)樽笥易訕?shù)深度差太大，導(dǎo)致其查詢效率跟普通單鏈表一樣
所以我們就需要一個(gè)更加平衡的二叉樹(shù) --- 平衡二叉樹(shù) Balanced binary search trees
平衡二叉樹(shù)（AVL Tree)
平衡二叉樹(shù)要求左右子樹(shù)深度差絕對(duì)值不能超過(guò)1。
如果此時(shí)我們依次插入1,2,3,4,5,6，其樹(shù)型結(jié)構(gòu)會(huì)是如下圖所示，不會(huì)出現(xiàn)斜樹(shù)的情形https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
使用上述鏈接演示一下可以發(fā)現(xiàn)，當(dāng)AVL樹(shù)出現(xiàn)斜樹(shù)的情形時(shí)，就會(huì)發(fā)生旋轉(zhuǎn)
在平衡二叉樹(shù)中，一個(gè)節(jié)點(diǎn)是一個(gè)大小固定的單位，作為索引應(yīng)該存儲(chǔ)什么內(nèi)容？
第一個(gè)是索引的鍵值。比如我們?cè)趇d上創(chuàng)建了一個(gè)索引，在用where id=1的條件查詢的時(shí)候就會(huì)找到索引里面的id的這個(gè)鍵值。
第二個(gè)是數(shù)據(jù)的磁盤(pán)地址。因?yàn)樗饕淖饔镁褪欠奖阄覀兛焖俨檎覕?shù)據(jù)的存放地址。
第三個(gè)是左右子節(jié)點(diǎn)的引用
當(dāng)我們使用AVL樹(shù)存儲(chǔ)索引數(shù)據(jù)時(shí)，訪問(wèn)一個(gè)節(jié)點(diǎn)就要跟磁盤(pán)之間發(fā)生一次IO。
InnoDB操作磁盤(pán)的最小的單位是一頁(yè)（或者叫一個(gè)磁盤(pán)塊），大小是16K(16384字節(jié))。那么一個(gè)樹(shù)的節(jié)點(diǎn)大小最大就是16K的大小。
如果我們一個(gè)節(jié)點(diǎn)只存一個(gè)鍵值+數(shù)據(jù)+引用，例如整型的字段，可能只用了十幾個(gè)或者幾十個(gè)字節(jié)，它遠(yuǎn)遠(yuǎn)達(dá)不到16K的容量，所以訪問(wèn)一個(gè)樹(shù)節(jié)點(diǎn)，進(jìn)行一次IO的時(shí)候，浪費(fèi)了大量的空間(明明可以讀取16K的數(shù)據(jù))。
其次，當(dāng)數(shù)據(jù)量非常大的時(shí)候，這個(gè)AVL樹(shù)的高度也會(huì)非常高，導(dǎo)致需要和磁盤(pán)進(jìn)行非常多次的IO,很消耗時(shí)間
所以就需要在AVL樹(shù)的基礎(chǔ)上再次進(jìn)行優(yōu)化
1.讓每個(gè)節(jié)點(diǎn)存儲(chǔ)更多的數(shù)據(jù)。
2.節(jié)點(diǎn)上的關(guān)鍵字的數(shù)量越多，我們的指針數(shù)也越多，也就是意味著可以有更多的分叉（“路數(shù)”）。
多路平衡查找樹(shù)（B Tree）
跟AVL樹(shù)一樣，B樹(shù)在枝節(jié)點(diǎn)和葉子節(jié)點(diǎn)存儲(chǔ)鍵值、數(shù)據(jù)地址、節(jié)點(diǎn)引用。
它有一個(gè)特點(diǎn)：分叉數(shù)（路數(shù)）永遠(yuǎn)比關(guān)鍵字?jǐn)?shù)多1。
https://www.cs.usfca.edu/~galles/visualization/BTree.html
如圖就是一個(gè)多路平衡查找樹(shù)(Degree 節(jié)點(diǎn)擁有的子樹(shù)= 4)
比如MaxDegree（路數(shù)）= 4的時(shí)候，我們插入數(shù)據(jù)1、2、3、4，在插入4的時(shí)候，本來(lái)應(yīng)該在第一個(gè)磁盤(pán)塊，但是如果一個(gè)節(jié)點(diǎn)有四個(gè)關(guān)鍵字的時(shí)候，意味著有5個(gè)指針，子節(jié)點(diǎn)會(huì)變成5?路，所以這個(gè)時(shí)候必須進(jìn)行分裂。把中間的數(shù)據(jù)2提上去，把1變成左子樹(shù)節(jié)點(diǎn)，3、4變成2的右子樹(shù)節(jié)點(diǎn)。如果刪除節(jié)點(diǎn)，會(huì)有相反的合并的操作
從B樹(shù)的特性不難發(fā)現(xiàn)，在更新索引的時(shí)候也會(huì)發(fā)生大量的索引結(jié)構(gòu)的調(diào)整，這就是為什么建議我們不要在頻繁更新的列上建索引，或者為什么不要更新主鍵。
InnoDB中存在頁(yè)的概念，默認(rèn)大小為16K,文件系統(tǒng)中，也有頁(yè)的概念。操作系統(tǒng)和內(nèi)存打交道，最小的單位是頁(yè)P(yáng)age。文件系統(tǒng)的內(nèi)存頁(yè)通常是4K。為什么操作系統(tǒng)操作的最小單位要是一頁(yè)呢?這是因?yàn)镃PU訪問(wèn)存儲(chǔ)器時(shí)，無(wú)論是存取指令還是存取數(shù)據(jù)，所訪問(wèn)的存儲(chǔ)單元都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中，這就是所謂的局部性原理
假設(shè)一行數(shù)據(jù)大小是1K，那么一個(gè)數(shù)據(jù)頁(yè)可以放16行數(shù)據(jù)，往表中插入數(shù)據(jù)時(shí)，如果一個(gè)頁(yè)面已經(jīng)寫(xiě)完，會(huì)產(chǎn)生一個(gè)新的Page頁(yè)面。如果一個(gè)簇的所有的頁(yè)面都被用完，會(huì)從當(dāng)前頁(yè)面所在段分配一個(gè)新的簇。
如果數(shù)據(jù)不是連續(xù)的，在往已經(jīng)寫(xiě)滿的頁(yè)中插入數(shù)據(jù)，會(huì)導(dǎo)致Page頁(yè)面分裂。
這是因?yàn)槿绻迦氲臄?shù)據(jù)的索引(一般為主鍵索引) 不是遞增的,那么在插入過(guò)程中，就會(huì)由于排序的問(wèn)題，導(dǎo)致新的數(shù)據(jù)需要破壞原有的page才可以插入使其滿足查找樹(shù)的特性，導(dǎo)致頁(yè)分裂，從而可能使得樹(shù)的高度增加
這也是為什么我們建議使用遞增的數(shù)字來(lái)做主鍵
但是注意:葉分裂無(wú)法完全避免，因?yàn)橹麈I可以遞增，但是很多其他的索引無(wú)法滿足遞增。
加強(qiáng)版多路平衡查找樹(shù)（B+樹(shù)）
實(shí)際上，MySQL使用的索引還不是B樹(shù)，而是使用了B樹(shù)的改良版本--B+樹(shù)
其存儲(chǔ)結(jié)構(gòu)如下所示:
可以把非葉子節(jié)點(diǎn)理解成多層目錄，葉子節(jié)點(diǎn)理解成目錄下的具體頁(yè)碼
MySQL中的B+Tree有幾個(gè)特點(diǎn)：
1、它的關(guān)鍵字的數(shù)量是跟路數(shù)相等的；
2、B+Tree的根節(jié)點(diǎn)和枝節(jié)點(diǎn)中都不會(huì)存儲(chǔ)數(shù)據(jù)，只有葉子節(jié)點(diǎn)才存儲(chǔ)數(shù)據(jù)。搜索到關(guān)鍵字不會(huì)直接返回，會(huì)到最后一層的葉子節(jié)點(diǎn)。比如我們搜索 id=28，雖然在第一層直接命中了，但是全部的數(shù)據(jù)在葉子節(jié)點(diǎn)上面，所以還是要繼續(xù)往下搜索，一直到葉
子節(jié)點(diǎn)。
舉個(gè)例子：假設(shè)一條記錄是1K，一個(gè)葉子節(jié)點(diǎn)（一頁(yè)）可以存儲(chǔ)16條記錄。我們計(jì)算下非葉子節(jié)點(diǎn)可以存儲(chǔ)多少個(gè)指針？
假設(shè)索引字段是bigint 類型，長(zhǎng)度為 8 字節(jié)。指針大小在 InnoDB 中設(shè)置為6 字節(jié)，這樣一共 14 字節(jié)。非葉子節(jié)點(diǎn)（一頁(yè)）可以存儲(chǔ)16384/14=1170個(gè)這樣的單元（鍵值+指針），代表有1170個(gè)指針。
樹(shù) 深 度 為 2 的 時(shí) 候 ， 有 1170^2 個(gè) 葉 子 節(jié) 點(diǎn) ， 可 以 存 儲(chǔ) 的 數(shù) 據(jù) 為1170*1170*16=21902400。
在查找數(shù)據(jù)時(shí)一次IO讀取一頁(yè)的數(shù)據(jù)，也就是說(shuō)，一張2000萬(wàn)左右的表，查詢數(shù)據(jù)最多需要訪問(wèn)3次磁盤(pán)
3.B+Tree的每個(gè)葉子節(jié)點(diǎn)增加了一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針
它的最后一個(gè)數(shù)據(jù)會(huì)指向下一個(gè)葉子節(jié)點(diǎn)的第一個(gè)數(shù)據(jù)，形成了一個(gè)有序鏈表的結(jié)構(gòu)。如果是范圍查詢，在查到一端的最小值之后，可以直接遍歷這個(gè)鏈表的結(jié)構(gòu)，直接獲取到所有的值不需要重新從根節(jié)點(diǎn)進(jìn)行IO查找
4、它是根據(jù)左閉右開(kāi)的區(qū)間 [ )來(lái)檢索數(shù)據(jù)。
總結(jié)一下InnoDB中B+樹(shù)的優(yōu)點(diǎn)
1)它是B樹(shù)的變種，也解決B樹(shù)解決的問(wèn)題:每個(gè)節(jié)點(diǎn)存儲(chǔ)更多關(guān)鍵字和更多路數(shù)
2) 掃庫(kù)、掃表能力更強(qiáng)
如果我們要對(duì)表進(jìn)行全表掃描，只需要遍歷葉子節(jié)點(diǎn)就可以了，不需要遍歷整棵B+樹(shù)拿到所有的數(shù)據(jù)
3)B+樹(shù)的磁盤(pán)讀寫(xiě)能力相對(duì)于B樹(shù)來(lái)說(shuō)更強(qiáng)
根節(jié)點(diǎn)和枝節(jié)點(diǎn)不保存數(shù)據(jù)，所以一個(gè)節(jié)點(diǎn)可以保存更多的關(guān)鍵字，一次磁盤(pán)加載的關(guān)鍵字更多
4)排序能力更強(qiáng)
因?yàn)槿~子節(jié)點(diǎn)上有下一個(gè)數(shù)據(jù)區(qū)的指針，數(shù)據(jù)形成了鏈表
5)效率更加穩(wěn)定
B+樹(shù)永遠(yuǎn)是在葉子節(jié)點(diǎn)拿到數(shù)據(jù)，所以IO次數(shù)是穩(wěn)定的
不同存儲(chǔ)引擎的索引結(jié)構(gòu)
每張InnoDB 的表會(huì)有兩個(gè)文件（.frm和.ibd），MyISAM的表會(huì)有三個(gè)文件（.frm、.MYD、.MYI）。
?.frm是MySQL里面表結(jié)構(gòu)定義的文件，不管你建表的時(shí)候選用任何一個(gè)存儲(chǔ)引擎都會(huì)生成
InnoDB
在InnoDB 里面，它是以主鍵為索引來(lái)組織數(shù)據(jù)的存儲(chǔ)的，所以索引文件和數(shù)據(jù)文件是同一個(gè)文件，都在.ibd文件里面
在InnoDB的主鍵索引的葉子節(jié)點(diǎn)上，它直接存儲(chǔ)了表中的數(shù)據(jù)。
InnoDB中的主鍵索引又稱為聚集索引，非主鍵都是非聚集索引。
所謂聚集索引就是索引鍵值的邏輯順序跟表數(shù)據(jù)行的物理存儲(chǔ)順序是一致的。（比如字典的目錄是按拼音排序的，內(nèi)容也是按拼音排序的，按拼音排序的這種目錄就叫聚集索引）。
對(duì)于非主鍵索引(輔助索引)存儲(chǔ)的是輔助索引和主鍵值。如果使用輔助索引查詢，會(huì)先根據(jù)輔助索引查找到對(duì)應(yīng)的主鍵值，再根據(jù)主鍵值在主鍵索引中查詢，最終取得數(shù)據(jù)。
因?yàn)锽+樹(shù)在實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)關(guān)鍵字，并保持平衡的過(guò)程中會(huì)發(fā)生分叉和合并的操作，這個(gè)時(shí)候鍵值的地址會(huì)發(fā)生變化，所以在輔助索引里面不能存儲(chǔ)鍵值的磁盤(pán)地址。
因?yàn)镮nnoDB是以主鍵為索引來(lái)組織數(shù)據(jù)的存儲(chǔ)，如果一張表沒(méi)有主鍵怎么辦？
1.如果我們定義了主鍵(PRIMARY KEY)，那么InnoDB會(huì)選擇主鍵作為聚集索引。
2.如果沒(méi)有顯式定義主鍵，則InnoDB會(huì)選擇第一個(gè)不包含NULL值的唯一索引作為主鍵索引。
3.如果也沒(méi)有這樣的唯一索引，則InnoDB會(huì)選擇內(nèi)置6字節(jié)長(zhǎng)的ROWID作為隱藏的聚集索引，它會(huì)隨著行記錄的寫(xiě)入而遞增
MyISAM
MyISAM有兩個(gè)額外的文件: .MYD和.MYI
.MYD文件，D代表Data，是MyISAM的數(shù)據(jù)文件，存放數(shù)據(jù)記錄; .MYI文件，I代表Index，是MyISAM的索引文件，存放索引
在MyISAM里面，索引和數(shù)據(jù)是兩個(gè)獨(dú)立的文件。
在MyISAM的B+Tree 里面，葉子節(jié)點(diǎn)存儲(chǔ)的是數(shù)據(jù)文件對(duì)應(yīng)的磁盤(pán)地址。所以從索引文件.MYI中找到鍵值后，會(huì)到數(shù)據(jù)文件.MYD中獲取相應(yīng)的數(shù)據(jù)記錄。
在MyISAM中，主鍵索引和輔助索引的檢索方式都是一樣的，都是先在索引文件里面找到磁盤(pán)地址，然后到數(shù)據(jù)文件里面根據(jù)磁盤(pán)地址獲取對(duì)應(yīng)數(shù)據(jù)
總結(jié)
以上是生活随笔為你收集整理的MySQL(三)MySQL索引原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： MySQL(一)SQL执行流程与MySQ
- 下一篇： JDBC连接失败java.sql.SQL