數(shù)據(jù)庫為何要使用索引?
- 磁盤IO的方式
尋道（速度較慢）,旋轉(zhuǎn)（速度較快）。
一個(gè)磁盤由大小相同且同軸的圓形盤片組成敷鸦，磁盤可以轉(zhuǎn)動(dòng)（各個(gè)磁盤必須同步轉(zhuǎn)動(dòng)）扒披。在磁盤的一側(cè)有磁頭支架圃泡，磁頭支架固定了一組磁頭颇蜡，每個(gè)磁頭負(fù)責(zé)存取一個(gè)磁盤的內(nèi)容。磁頭不能轉(zhuǎn)動(dòng)熔任，但是可以沿磁盤半徑方向運(yùn)動(dòng)（實(shí)際是斜切向運(yùn)動(dòng)）疑苔，每個(gè)磁頭同一時(shí)刻也必須是同軸的，即從正上方向下看惦费，所有磁頭任何時(shí)候都是重疊的（不過目前已經(jīng)有多磁頭獨(dú)立技術(shù)，可不受此限制）恍箭。
磁盤IO.png
- 局部性原理與磁盤預(yù)讀
磁盤讀取數(shù)據(jù)靠的是機(jī)械運(yùn)動(dòng)扯夭，每次讀取數(shù)據(jù)花費(fèi)的時(shí)間可以分為尋道時(shí)間鞍匾、旋轉(zhuǎn)延遲橡淑、傳輸時(shí)間三個(gè)部分，尋道時(shí)間指的是磁臂移動(dòng)到指定磁道所需要的時(shí)間置森，主流磁盤一般在5ms以下凫海；旋轉(zhuǎn)延遲就是我們經(jīng)常聽說的磁盤轉(zhuǎn)速濒蒋，比如一個(gè)磁盤7200轉(zhuǎn)把兔，表示每分鐘能轉(zhuǎn)7200次县好，也就是說1秒鐘能轉(zhuǎn)120次缕贡，旋轉(zhuǎn)延遲就是1/120/2 = 4.17ms；傳輸時(shí)間指的是從磁盤讀出或?qū)?shù)據(jù)寫入磁盤的時(shí)間收擦，一般在零點(diǎn)幾毫秒塞赂，相對(duì)于前兩個(gè)時(shí)間可以忽略不計(jì)昼蛀。那么訪問一次磁盤的時(shí)間圆存，即一次磁盤IO的時(shí)間約等于5+4.17 = 9ms左右仇哆，聽起來還挺不錯(cuò)的讹剔，但要知道一臺(tái)500 -MIPS的機(jī)器每秒可以執(zhí)行5億條指令延欠，因?yàn)橹噶钜揽康氖请姷男再|(zhì)，換句話說執(zhí)行一次IO的時(shí)間可以執(zhí)行40萬條指令诀紊，數(shù)據(jù)庫動(dòng)輒十萬百萬乃至千萬級(jí)數(shù)據(jù)隅俘，每次9毫秒的時(shí)間为居，顯然是個(gè)災(zāi)難蒙畴。這種情況下，我們就需要對(duì)其進(jìn)行優(yōu)化碑隆。
FIX：向表插入數(shù)據(jù)的時(shí)候上煤，在磁盤上面是分開分布的著淆，并不連續(xù)在一起的永部。極限情況下苔埋，找到一某一行數(shù)據(jù)可能要經(jīng)過最大行數(shù)的IO。
索引是什么?
- 索引的作用
幫助Mysql高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)。 - 索引的存儲(chǔ)
索引一般以文件形式存儲(chǔ)在磁盤上孕惜，索引檢索需要磁盤I/O操作愧薛。
與主存不同，磁盤I/O存在機(jī)械運(yùn)動(dòng)耗費(fèi)衫画，因此磁盤I/O的時(shí)間消耗是巨大的毫炉。
FIX：mysql data目錄下的數(shù)據(jù)庫里面的表文件打開，可以發(fā)現(xiàn)專門存儲(chǔ)索引的文件削罩。
索引的數(shù)據(jù)結(jié)構(gòu)瞄勾，優(yōu)劣勢(shì)對(duì)比
二叉樹
二叉排序樹.png
- 二叉排序樹
①若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值弥激；
②若右子樹不空进陡，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
③左微服、右子樹也分別為二叉排序樹趾疚；
當(dāng)插入的元素是有序的丛肮，生成的二叉排序樹就是一個(gè)鏈表焚廊，這種情況下，需要遍歷全部元素才行嗓蘑。如果我們可以保證二叉排序樹不出現(xiàn)上面提到的極端情況（插入的元素是有序的豌汇，導(dǎo)致變成一個(gè)鏈表），就可以保證很高的效率了（效率近似于折半查找）闸天。 - 平衡二叉樹
①平衡二叉樹要么是一棵空樹，要么保證左右子樹的高度之差不大于 1。
②子樹也必須是一顆平衡二叉樹贷帮。
用平衡因子差值判斷是否平衡并通過旋轉(zhuǎn)來實(shí)現(xiàn)平衡精居。
平衡二叉樹在添加和刪除時(shí)需要進(jìn)行旋轉(zhuǎn)保持整個(gè)樹的平衡沟绪。
解決的問題：通過維護(hù)樹的平衡來避免生成二叉樹為鏈表的情況坝疼。
缺點(diǎn)：維護(hù)這種高度平衡所付出的代價(jià)比從后者那個(gè)獲得的效率收益要大，故而實(shí)際的應(yīng)用不多耕陷。但在對(duì)插入刪除不頻繁锌介，只對(duì)查找要求較高，平衡二叉樹的優(yōu)勢(shì)還是比較明顯。
- 紅黑樹
一種自平衡的二叉查找樹雳窟，調(diào)整方式（變色捣作，旋轉(zhuǎn)[左旋轉(zhuǎn)][右旋轉(zhuǎn)]）節(jié)點(diǎn)是紅色或者黑色。
根節(jié)點(diǎn)是黑色以舒，每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)滥沫。
每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)踪央。
解決問題：
缺點(diǎn)：每個(gè)節(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)镐牺，當(dāng)數(shù)據(jù)量大的時(shí)候深度不可控畦浓。
FIX:TreeMap底層就是紅黑樹，有興趣的朋友可以了解一下。
HASH
通過算法，將索引和磁盤的地址進(jìn)行關(guān)聯(lián)状勤，查找某一行數(shù)據(jù)便只需要進(jìn)行一次IO即可持搜。HASH索引無法實(shí)現(xiàn)范圍查找，但是匹配具體條件查詢的話效率還是比較高的
BTREE
B-TREE.png
B+TREE.png
- B-TREE
KEY和指針互相間隔匣距，節(jié)點(diǎn)兩端是指針,每個(gè)指針要么為null尸红，要么指向另外一個(gè)節(jié)點(diǎn)。
葉子節(jié)點(diǎn)具有相同的深度，葉子節(jié)點(diǎn)的指針為空，節(jié)點(diǎn)中的數(shù)據(jù)key從左到右遞增排列顶瞳。
度（節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的個(gè)數(shù)）> 15/16的時(shí)候會(huì)分裂闪彼，橫向擴(kuò)展描馅。
檢索原理：首先從根節(jié)點(diǎn)進(jìn)行二分查找，如果找到則返回對(duì)應(yīng)節(jié)點(diǎn)的data，否則對(duì)相應(yīng)區(qū)間的指針指向的節(jié)點(diǎn)遞歸進(jìn)行查找簸喂，直到找到節(jié)點(diǎn)或未找到節(jié)點(diǎn)返回null指針唉锌。 - B+TREE
非葉子節(jié)點(diǎn)不存儲(chǔ)data秃症，只存儲(chǔ)索引key聚请；只有葉子節(jié)點(diǎn)才存儲(chǔ)data
MYSQL的B+TREE
MYSQL B+TREE索引結(jié)構(gòu).png
在B+Tree的每個(gè)葉子節(jié)點(diǎn)增加一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針蚯姆，就形成了帶有順序訪問指針的B+Tree。這樣就提高了區(qū)間訪問性能：如果要查詢key為從18到49的所有數(shù)據(jù)記錄链韭，當(dāng)找到18后，只需順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點(diǎn)，極大提到了區(qū)間查詢效率(無需返回上層父節(jié)點(diǎn)重復(fù)遍歷查找減少IO操作)宛官。
MYSQL索引底層數(shù)據(jù)結(jié)構(gòu)分析
MyISAM引擎
非聚簇索引：myi索引文件和myd數(shù)據(jù)文件分離党晋，索引文件僅保存數(shù)據(jù)記錄的指針地址。葉子節(jié)點(diǎn)data域存儲(chǔ)指向數(shù)據(jù)記錄的指針地址橙困。(底層存儲(chǔ)文件： frm -表定義明未、 myi -myisam索引、 myd-myisam數(shù)據(jù))匆光×可以看到表定義文件，索引文件，數(shù)據(jù)文件是分開的
MyISAM引擎的表排监，索引可以緩存到內(nèi)存中附鸽。
MyISAM引擎索引.png
InnoDB引擎
聚簇索引：數(shù)據(jù)&索引文件為一個(gè)idb文件竟秫，表數(shù)據(jù)文件本身就是主索引浅侨，相鄰的索引臨近存儲(chǔ)（數(shù)據(jù)一定也是相鄰地存放在磁盤上）澳化。 葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄(數(shù)據(jù)[除主鍵id外其他列data]+主索引[索引key:表主鍵id])喻奥。 (底層存儲(chǔ)結(jié)構(gòu): frm -表定義寇钉、 ibd: innoDB數(shù)據(jù)&索引文件)锥累。聚簇索引的索引和數(shù)據(jù)是一個(gè)文件。
主鍵索引 & 輔助索引.png
