深入理解Mysql索引底層數(shù)據(jù)結(jié)構(gòu)與算法

一.索引的本質(zhì)

索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)

二.索引數(shù)據(jù)結(jié)構(gòu)

1.二叉樹

2.紅黑樹

? ??\color{red}{缺點:當(dāng)數(shù)據(jù)量龐大的時候,紅黑樹高度不可控,容易使樹的高度太大,不利于快速檢索數(shù)據(jù)}

3.Hash表

??\color{red}{優(yōu)點:對檢索條件進(jìn)行hash運算,然后通過hash表得到磁盤數(shù)據(jù)映射地址,可以很快獲取數(shù)據(jù),跟數(shù)據(jù)量大小不成正比}

4.B-Tree

? ? 1.葉節(jié)點具有相同的深度,葉節(jié)點的指針為空

? ? 2.所有索引元素不重復(fù)

? ? 3.節(jié)點中的數(shù)據(jù)索引從左到右遞增排序\color{red}{缺點:B-Tree中每個節(jié)點中帶有data數(shù)據(jù),這個data數(shù)據(jù)如果存儲Mysql中的一行數(shù)據(jù),這一行數(shù)據(jù)列數(shù)很多,就會占用磁盤空間,使節(jié)點變少,樹的高度也不可控}

B-Tree

5.B+Tree

? ? 1.非葉子節(jié)點不存儲data,可以放更多的索引

? ? 2.葉子節(jié)點包含所有索引字段

? ? 3.葉子節(jié)點用指針連接,提高區(qū)間訪問的性能(體現(xiàn)在做范圍查詢的時候)? ??


B+Tree

三.MyISAM存儲引擎索引實現(xiàn)

? ? ? ? MyISAM索引文件(MYI)和數(shù)據(jù)文件(MYD)是分離的(非聚集)


四.InnoDB索引實現(xiàn)(聚集)

?1.表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)文件

?2.聚集索引-葉節(jié)點包含了完整的數(shù)據(jù)記錄(觀察最后的葉子結(jié)點)

?3.為什么InnoDB表必須有主鍵,并且推薦使用整型的自增主鍵?

\color{red}{底層采用B+Tree,所以必須有主鍵}

? ?\color{red}{整型容易比較大小,葉子結(jié)點自增的利于維護(hù),不至于導(dǎo)致結(jié)點分裂和平衡}

4.為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點存儲的是主鍵值?(一致性和節(jié)省存儲空間)

? ??\color{red}{因為主鍵索引的時候已經(jīng)存儲了所有的行數(shù)據(jù),沒必要再非主鍵索引的葉子結(jié)點再去存儲一遍}


五.聯(lián)合索引

? ? 底層的數(shù)據(jù)結(jié)構(gòu)長什么樣子??

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容