前言
磁盤存取時(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ì)按照員工出生年月比較。