一、索引類型

1.B+樹(shù)

為什么是B+樹(shù)而不是B樹(shù)？

首先看看B樹(shù)和B+樹(shù)在結(jié)構(gòu)上的區(qū)別

B樹(shù)結(jié)構(gòu)：

B+樹(shù)：

可以看到：

• B樹(shù)在每個(gè)節(jié)點(diǎn)上都有衛(wèi)星數(shù)據(jù)(數(shù)據(jù)表中的一行數(shù)據(jù))，而B(niǎo)+樹(shù)只在葉子節(jié)點(diǎn)上有衛(wèi)星數(shù)據(jù)。這意味著相同大小的磁盤扇區(qū)，B+樹(shù)可以存儲(chǔ)的葉子節(jié)點(diǎn)更多，磁盤IO次數(shù)更少；同樣也意味著B(niǎo)+樹(shù)的查找效率更穩(wěn)定，而B(niǎo)樹(shù)數(shù)據(jù)查詢的最快時(shí)間復(fù)雜度是O(1)。
• B樹(shù)的每個(gè)節(jié)點(diǎn)只出現(xiàn)一次，B+樹(shù)的所有節(jié)點(diǎn)都會(huì)出現(xiàn)在葉子節(jié)點(diǎn)中。B+樹(shù)的所有葉子節(jié)點(diǎn)形成一個(gè)升序鏈表，適合區(qū)間范圍查找，而B(niǎo)樹(shù)則不適合。
  

2.MyISAM和InnoDB的B+樹(shù)索引實(shí)現(xiàn)方式的區(qū)別(聚簇索引和非聚簇索引)？

首先需要了解聚簇索引和非聚簇索引。

聚簇索引：

在聚簇索引中，葉子頁(yè)包含了行的全部數(shù)據(jù)，節(jié)點(diǎn)頁(yè)值包含索引列。InnoDB通過(guò)主鍵聚集數(shù)據(jù)，如果沒(méi)有定義主鍵則選擇一個(gè)唯一的非空索引列代替；如果沒(méi)有這樣的索引，InnoDB會(huì)隱式定義一個(gè)主鍵來(lái)作為聚簇索引。

聚簇索引的數(shù)據(jù)分布：

?在聚簇索引中，除了主鍵索引，還有二級(jí)索引。二級(jí)索引中的葉子節(jié)點(diǎn)存儲(chǔ)的不是“行指針”，而是主鍵值，并以此作為指向行的“指針”。這意味著通過(guò)二級(jí)索引查找行，存儲(chǔ)引擎需要找到二級(jí)索引的葉子節(jié)點(diǎn)獲得對(duì)應(yīng)的主鍵值，然后根據(jù)這個(gè)值去聚簇索引中查找對(duì)應(yīng)的行，也稱為“回表”。當(dāng)然，可以通過(guò)覆蓋索引避免回表或者InnoDB的自適應(yīng)索引能夠減少這樣的重復(fù)工作。

注意：聚簇索引中每一個(gè)葉子節(jié)點(diǎn)不止包含完整的數(shù)據(jù)行，還包括事務(wù)ID、用于事務(wù)和MVCC的回滾指針。

3.非聚簇索引

非聚簇索引的主鍵索引和二級(jí)索引在結(jié)構(gòu)上沒(méi)有什么不同，都在葉子節(jié)點(diǎn)上存儲(chǔ)指向數(shù)據(jù)的物理地址的“行指針”。

聚簇索引的主鍵索引和二級(jí)索引：

非聚簇索引的主鍵索引和二級(jí)索引：

4.聚簇索引的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

把相關(guān)數(shù)據(jù)保存在一起（比如用用戶ID把用戶的全部郵件聚集在一起），否則每次數(shù)據(jù)讀取就可能導(dǎo)致一次磁盤IO
數(shù)據(jù)訪問(wèn)更快，把索引和數(shù)據(jù)保存在同一個(gè)B+樹(shù)中，通常在聚簇索引中獲取數(shù)據(jù)比在非聚簇索引中查找更快
使用覆蓋查詢可以直接利用頁(yè)節(jié)點(diǎn)中的主鍵值

缺點(diǎn)：

如果所有數(shù)據(jù)都可以放在內(nèi)存中，順序訪問(wèn)不再那么必要，聚簇索引沒(méi)有優(yōu)勢(shì)
插入速度依賴于插入順序，隨機(jī)插入會(huì)導(dǎo)致頁(yè)分裂，造成空洞，使用OPTIMIZE TABLE重建表
每次插入、更新、刪除都需要維護(hù)索引的變化，代價(jià)很高
二級(jí)索引可能比想象中大，因?yàn)樵诠?jié)點(diǎn)中包含了引用行的主鍵列

5.哈希索引

哈希索引基于哈希表實(shí)現(xiàn)，只有精確匹配索引所有列的查詢才有效，這意味著，哈希索引適用于等值查詢。

具體實(shí)現(xiàn)：對(duì)于每一行數(shù)據(jù)，存儲(chǔ)引擎都會(huì)對(duì)所有的索引列計(jì)算一個(gè)哈希碼，哈希索引將所有的哈希碼存儲(chǔ)在索引中，同時(shí)在哈希表中保存指向每個(gè)數(shù)據(jù)行的指針。

在MySQL中，只有Memory引擎顯式支持哈希索引，當(dāng)然Memory引擎也支持B樹(shù)索引。

注意:Memory引擎支持非唯一哈希索引，解決沖突的方式是以鏈表的形式存放多個(gè)哈希值相同的記錄指針。

6.自適應(yīng)哈希索引

InnoDB注意到某些索引值被使用得非常頻繁時(shí)，會(huì)在內(nèi)存中基于B+樹(shù)索引之上再創(chuàng)建一個(gè)哈希索引，這樣就讓B+樹(shù)索引也具有哈希索引的一些優(yōu)點(diǎn)，比如快速的哈希查找。

到此這篇關(guān)于MySQL索引底層數(shù)據(jù)結(jié)構(gòu)詳情的文章就介紹到這了,更多相關(guān)MySQL索引底層數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！