本文非小馬原創(chuàng)，為學(xué)習(xí)總結(jié)筆記，作為日后復(fù)盤回顧邑退，感謝原作者分享竹宋，文末已注明出處，侵刪地技。
MySQL中索引實(shí)現(xiàn)的原理是什么蜈七？目前大部分?jǐn)?shù)據(jù)庫系統(tǒng)及文件系統(tǒng)都采用B-Tree(B樹)或其變種B+Tree(B+樹)作為索引結(jié)構(gòu)。B+Tree是數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)索引的首選數(shù)據(jù)結(jié)構(gòu)莫矗。在 MySQL 中,索引屬于存儲引擎級別的概念,不同存儲引擎對索引的實(shí)現(xiàn)方式是不同的飒硅。
樹砂缩，二叉樹（從左到右垂直有序），平衡二叉樹（左右高度限制）三娩，b樹庵芭，b+樹，完全二叉樹雀监，堆（上下每一層大小是有序的双吆，左右大小無序），大根堆会前，小根堆好乐。
一、MyISAM 索引實(shí)現(xiàn)
MyISAM 引擎使用 B+Tree 作為索引結(jié)構(gòu),葉節(jié)點(diǎn)的 data 域存放的是數(shù)據(jù)記錄的地址瓦宜。我們借用兩張圖來說明蔚万。
MyISAM 的索引方式也叫做“非聚集索引”,之所以這么稱呼是為了與 InnoDB的聚集索引區(qū)分。意思是临庇，索引中只保存著數(shù)據(jù)在表中的地址而不是保存數(shù)據(jù)本身反璃。
二、InnoDB 索引實(shí)現(xiàn)
InnoDB 也使用 B+Tree 作為索引結(jié)構(gòu),但具體實(shí)現(xiàn)方式卻與 MyISAM 截然不同苔巨。InnoDB 的數(shù)據(jù)文件本身就是索引文件版扩。從上文知道,MyISAM 索引文件和數(shù)據(jù)文件是分離的,索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB 中,表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個索引結(jié)構(gòu),這棵樹的葉點(diǎn)data 域保存了完整的數(shù)據(jù)記錄侄泽。這個索引的 key 是數(shù)據(jù)表的主鍵,因此 InnoDB 表數(shù)據(jù)文件本身就是主索引礁芦。
借用兩張圖來說明。
InnoDB 主索引(同時也是數(shù)據(jù)文件),可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄悼尾。這種索引叫做聚集索引柿扣。
三、總結(jié)
myisam中主鍵索引和輔助索引都是記錄數(shù)據(jù)在表中的地址闺魏，索引比較小未状，但查詢數(shù)據(jù)都需要二次查找。先根據(jù)索引找到數(shù)據(jù)地址再通過地址查找到表中的數(shù)據(jù)析桥。
innodb主鍵索引是聚簇的司草，索引樹中直接記錄了表數(shù)據(jù)，占空間比較大泡仗。輔助索引是非聚簇的埋虹，這和上面myisam一樣。啥意思呢娩怎？主鍵索引的查找只需要一次查找直接拿到數(shù)據(jù)搔课，非主鍵的索引查找需要二次查找。所以主鍵索引會比較快截亦。
彩蛋1：對于innodb而言爬泥，表沒有主鍵可以嗎柬讨？
可以，但是如果沒有主鍵袍啡，就是屬于輔助索引踩官，要多查一次索引。不過mysql會拿唯一鍵來自動創(chuàng)建為隱藏的主鍵索引葬馋，所以如果是對唯一鍵條件查詢卖鲤，其實(shí)沒有主鍵也不會多一次查找。因?yàn)?b>聚簇索引具有唯一性畴嘶，由于聚簇索引是將數(shù)據(jù)跟索引結(jié)構(gòu)放到一塊蛋逾，因此一個表僅有一個聚簇索引。聚簇索引默認(rèn)是主鍵窗悯，如果表中沒有定義主鍵区匣，InnoDB 會選擇一個唯一且非空的索引代替。如果沒有這樣的索引蒋院，InnoDB 會隱式定義一個主鍵（類似oracle中的RowId）來作為聚簇索引亏钩。聚簇索引是唯一的，InnoDB一定會有一個聚簇索引來保存數(shù)據(jù)欺旧。非聚簇索引一定存儲有聚簇索引的列值姑丑。
InnoDB聚簇索引選擇順序：
默認(rèn)選擇主鍵；
沒有主鍵辞友，選擇唯一的非空索引栅哀；
都沒有，則隱式定義一個主鍵称龙；
非聚簇索引留拾，數(shù)據(jù)存儲和索引分開，葉子節(jié)點(diǎn)存儲對應(yīng)的行鲫尊，需要二次查找痴柔，通常稱為[二級索引]或[輔助索引]。
彩蛋2：count函數(shù)會引起全表掃描嗎疫向？
InnoDB：count(主鍵) 全表掃描累加咳蔚，count(1)全表掃描累加，count(字段)分為字段可為空和字段不可為空搔驼，不可為空則讀到后累加谈火，可為空則讀到后判斷不為空累加。count(*) 不取值累加匙奴。除了 count(*)外其他都要取值基本上 count(*)是最快的堆巧。
MyISAM： 會記錄一張表的行數(shù)妄荔，count 時直接返回行數(shù)泼菌。
彩蛋3：我們經(jīng)常在DB工具中創(chuàng)建索引時選擇索引類型除了Btree還有個哈希類型?
是的谍肤。哈希類型的優(yōu)點(diǎn)：哈希表這種結(jié)構(gòu)適用于只有等值查詢的場景，新增方便哗伯。缺點(diǎn)：非有序荒揣，做區(qū)間查詢的速度是很慢，需要全部遍歷：干病系任！哈希索引也不支持多列聯(lián)合索引的最左匹配規(guī)則！虐块！
參考文獻(xiàn)：
