前言
磁盤存取時(shí)間
- 尋道時(shí)間（速度慢，費(fèi)時(shí)）
-
旋轉(zhuǎn)時(shí)間（速度較快）
image.png
image.png
局部性原理與磁盤預(yù)讀
為了提升效率蛔糯，要盡量減少磁盤IO的次數(shù)拯腮。實(shí)際過(guò)程中，磁盤并不是每次嚴(yán)格按需讀取蚁飒，而是每次都會(huì)預(yù)讀动壤。磁盤讀取完需要的數(shù)據(jù)后，會(huì)按順序再多讀一部分?jǐn)?shù)據(jù)到內(nèi)存中淮逻，這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中注明的局部性原理：
當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)琼懊，其附近的數(shù)據(jù)也通常會(huì)馬上被使用
程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中
（1）由于磁盤順序讀取的效率很高(不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間)爬早，
因此對(duì)于具有局部性的程序來(lái)說(shuō)哼丈，預(yù)讀可以提高I/O效率.預(yù)讀的長(zhǎng)度一般為頁(yè)(page)的整倍數(shù)。
（2）MySQL(默認(rèn)使用InnoDB引擎),將記錄按照頁(yè)的方式進(jìn)行管理,每頁(yè)大小默認(rèn)為16K(這個(gè)值可以修改)筛严。linux 默認(rèn)頁(yè)大小為4K醉旦。
1. 索引到底是什么
索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
索引存儲(chǔ)在文件里
索引結(jié)構(gòu)
為什么不用二叉樹、紅黑樹桨啃、HASH 作為索引結(jié)構(gòu)
二叉樹 數(shù)據(jù)向一方偏離车胡，一個(gè)節(jié)點(diǎn)的左鍵點(diǎn)小于該節(jié)點(diǎn)，右節(jié)點(diǎn)大于該節(jié)點(diǎn)照瘾，但是如果插入二叉樹的數(shù)據(jù)是有序的匈棘，就會(huì)形成二叉樹的極端情況，形成鏈表析命，我們知道樹的查詢復(fù)雜度跟樹的高度有關(guān)主卫，樹越高逃默，那么查詢事件復(fù)雜度就越高，并且需要更多的磁盤IO队秩，所以需要通過(guò)某種約束來(lái)保證樹的平衡笑旺，
紅黑樹
雖然數(shù)據(jù)較二叉樹樹形能翻轉(zhuǎn)保持平衡，數(shù)據(jù)大量的時(shí)候馍资，數(shù)據(jù)深度會(huì)很大
紅黑樹就是平衡二叉樹中的一種筒主，它通過(guò)一系列的規(guī)則來(lái)保證樹的平衡。但是在大規(guī)模數(shù)據(jù)存儲(chǔ)的時(shí)候鸟蟹，紅黑樹常常會(huì)因?yàn)闃涞纳疃冗^(guò)高而導(dǎo)致磁盤IO讀寫過(guò)于頻繁乌妙，導(dǎo)致效率底下，為什么會(huì)形成這種情況呢建钥，我們知道要獲取磁盤上的數(shù)據(jù)藤韵，必須通過(guò)磁盤移動(dòng)臂移動(dòng)到數(shù)據(jù)所在的柱面，然后找到指定盤面熊经，接著旋轉(zhuǎn)盤面找到數(shù)據(jù)所在的磁道泽艘，最后進(jìn)行讀寫，這種涉及到物理操作情況下镐依，性能自然會(huì)很低下匹涮。
HASH
1.hash表只能匹配是否相等，不能實(shí)現(xiàn)范圍查找
select * from xx where id > 23; 這時(shí)就沒辦法索引了
2.當(dāng)需要按照索引進(jìn)行order by時(shí)槐壳，hash值沒辦法支持排序
select * from xx order by score desc;如果score為建立索引的字段然低，hash值沒辦法輔助排序。
3.組合索引可以支持部分索引查詢务唐，如(a,b,c)的組合索引雳攘，查詢中只用到了阿和b也可以查詢的，如果使用hash表枫笛，組合索引會(huì)將幾個(gè)字段合并hash吨灭，沒辦法支持部分索引
4.當(dāng)數(shù)據(jù)量很大時(shí)，hash沖突的概率也會(huì)非常大
一般來(lái)說(shuō)有多少層高（數(shù)據(jù)深度）就有多少次IO耗時(shí)操作刑巧，減少層高非常有必要
BTree
- 度(Degree)一節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)個(gè)數(shù)
- 葉子節(jié)點(diǎn)具有相同的深度
- 葉子節(jié)點(diǎn)的指針為空
-
節(jié)點(diǎn)中的數(shù)據(jù)key從左到右遞增排列
注意：由于計(jì)算機(jī)硬件限制沃于，度(Degree)無(wú)限增大，并不能減少IO次數(shù)
image.png
B+Tree(B-Tree上優(yōu)化)
- 非葉子節(jié)點(diǎn)不存儲(chǔ)data海诲，只儲(chǔ)存key，
可以增大度(Degree) - 葉子節(jié)點(diǎn)不存儲(chǔ)指針
-
順序訪問(wèn)指針檩互，提高區(qū)間訪問(wèn)的性能
image.png
B+Tree索引的性能分析
- 一般使用磁盤I/O次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣
- 預(yù)讀：磁盤一般會(huì)順序向后讀取一定長(zhǎng)度的數(shù)據(jù)(頁(yè)的整數(shù)倍)放入內(nèi)存
- 局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)特幔，其附近的數(shù)據(jù)也通常會(huì)馬上被使用
- B+Tree節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，每次新建節(jié)點(diǎn)直接申請(qǐng)一個(gè)頁(yè)的空間闸昨，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里蚯斯，就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)的載入只需一次I/O
- B+Tree的度d一般會(huì)超過(guò)100薄风，因此h非常小(一般為3到5之間)
為什么mysql的索引使用B+樹而不是B樹呢？拍嵌？
上面大致介紹了B-樹遭赂，B+樹，哈希索引横辆。那么B+樹的優(yōu)勢(shì)大致總結(jié)如下
- 不同于B-樹只適合隨機(jī)檢索撇他，B+樹同時(shí)支持隨機(jī)檢索和順序檢索；
- B+樹的磁盤讀寫代價(jià)更低狈蚤。B+樹內(nèi)部結(jié)點(diǎn)比B-樹小困肩，盤塊能容納的結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)量更多，一次性讀入內(nèi)存中可以查找的關(guān)鍵字也就越多脆侮，相對(duì)的锌畸，IO讀寫次數(shù)也就降低了。而IO讀寫次數(shù)是影響索引檢索效率的最大因素靖避。
- B+樹的查詢效率更加穩(wěn)定潭枣。B-樹搜索有可能會(huì)在非葉子結(jié)點(diǎn)結(jié)束，越靠近根節(jié)點(diǎn)的記錄查找時(shí)間越短幻捏，只要找到關(guān)鍵字即可確定記錄的存在盆犁，其性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找。而在B+樹中粘咖，順序檢索比較明顯蚣抗，隨機(jī)檢索時(shí)，任何關(guān)鍵字的查找都必須走一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路瓮下，所有關(guān)鍵字的查找路徑長(zhǎng)度相同翰铡，導(dǎo)致每一個(gè)關(guān)鍵字的查詢效率相當(dāng)。
-
B-樹在提高了磁盤IO性能的同時(shí)并沒有解決元素遍歷的效率低下的問(wèn)題讽坏。B+樹的葉子節(jié)點(diǎn)使用指針順序連接在一起锭魔，只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢是非常頻繁的路呜，而B-樹不支持這樣的操作（或者說(shuō)效率太低）迷捧。
image.png
2. MySQL數(shù)據(jù)庫(kù)存儲(chǔ)引擎
MyISAM索引實(shí)現(xiàn)(非聚集)
MyISAM索引文件和數(shù)據(jù)文件是分離的
有些 MySQL 版本還缺乏完整的存儲(chǔ)過(guò)程支持 — 意味著不支持事務(wù)，這是 MyISAM 系統(tǒng)的最大缺點(diǎn)胀葱。
InnoDB索引實(shí)現(xiàn)(聚集)
- 數(shù)據(jù)文件本身就是索引文件
- 表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件
- 聚集索引-葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄
為什么InnoDB表必須有主鍵漠秋，并且推薦使用整型的自增主鍵？
首先抵屿，為了滿足MySQL的索引數(shù)據(jù)結(jié)構(gòu)B+樹的特性庆锦，必須要有索引作為主鍵，可以有效提高查詢效率轧葛，因此InnoDB必須要有主鍵搂抒。如果不手動(dòng)指定主鍵艇搀，InnoDB會(huì)從插入的數(shù)據(jù)中找出不重復(fù)的一列作為主鍵索引，如果沒找到不重復(fù)的一列求晶，這時(shí)候InnoDB會(huì)選擇內(nèi)置的ROWID作為主鍵焰雕，寫入順序和ROWID增長(zhǎng)順序一致；
其次芳杏，索引的數(shù)據(jù)類型是整型矩屁，一方面整型占有的磁盤空間或內(nèi)存空間相比字符串更少，另一方面整型比較比字符串比較更快速蚜锨，字符串比較是先轉(zhuǎn)換為ASCII碼档插，然后再比較的。
最后亚再，B+樹本質(zhì)是多路多叉樹郭膛，如果主鍵索引不是自增的，那么后續(xù)插入的索引就會(huì)引起B(yǎng)+樹的其他節(jié)點(diǎn)的分裂和重新平衡氛悬，影響數(shù)據(jù)插入的效率则剃，如果是自增主鍵，只用在尾節(jié)點(diǎn)做增加就可以如捅。
- 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵值棍现？(一致性和節(jié)省存儲(chǔ)空間)
主鍵索引和非主鍵索引維護(hù)各自的B+樹結(jié)構(gòu)，當(dāng)插入的數(shù)據(jù)的時(shí)候镜遣，由于數(shù)據(jù)只有一份己肮，通過(guò)非主鍵索引獲取到主鍵值，然后再去主鍵索引的B+樹數(shù)據(jù)結(jié)構(gòu)中找到對(duì)應(yīng)的行數(shù)據(jù)悲关，節(jié)省了內(nèi)存空間谎僻；
如果非主鍵索引的葉子節(jié)點(diǎn)也存儲(chǔ)一份數(shù)據(jù)，如果通過(guò)非主鍵索引插入數(shù)據(jù)寓辱，那么要向主鍵索引對(duì)應(yīng)的行數(shù)據(jù)進(jìn)行同步艘绍，那么會(huì)帶來(lái)數(shù)據(jù)一致性問(wèn)題★ぃ可以通過(guò)事務(wù)的方式解決诱鞠，我們都知道使用事務(wù)后，就會(huì)對(duì)性能有所消耗这敬。
聯(lián)合索引結(jié)構(gòu)
聯(lián)合索引的底層存儲(chǔ)結(jié)構(gòu)長(zhǎng)什么樣航夺？
定義聯(lián)合索引(員工級(jí)別，員工姓名崔涂，員工出生年月)敷存，將聯(lián)合索引按照索引順序放入節(jié)點(diǎn)中，新插入節(jié)點(diǎn)時(shí)，先按照聯(lián)合索引中的員工級(jí)別比較锚烦，如果相同會(huì)按照是員工姓名比較，如果員工級(jí)別和員工姓名都相同 最后是員工的出生年月比較帝雇′潭恚可以從圖中從上到下，從左到右看尸闸，第一個(gè)B+樹的節(jié)點(diǎn) 是通過(guò)聯(lián)合索引的員工級(jí)別比較的彻亲，第二個(gè)節(jié)點(diǎn)是 員工級(jí)別相同，會(huì)按照員工姓名比較吮廉，第三個(gè)節(jié)點(diǎn)是 員工級(jí)別和員工姓名都相同苞尝，會(huì)按照員工出生年月比較。
