索引的作用類似指向表中行的指針，能夠提高查詢速度。盡管索引可以提高查詢速度，但是不必要的索引會浪費(fèi)空間，并且在進(jìn)行插入、修改 和刪除時(shí)需要花費(fèi)額外的力氣去更改索引。
1. 在MySQL中使用索引
- CREATE方式
CREATE可以創(chuàng)建普通索引、唯一索引。CREATE INDEX index_name ON table_name (column_list); CREATE UNIQUE INDEX index_name ON table_name (column_list); - ALTER方式
ALTER可以創(chuàng)建普通索引、唯一索引和主鍵索引。ALTER TABLE table_name ADD INDEX (column_list); ALTER TABLE table_name ADD UNIQUE INDEX (column_list); ALTER TABLE table_name ADD PRIMARY KEY (column_list); - 建表時(shí)創(chuàng)建索引
2. 索引的結(jié)構(gòu)
MySQL中有許多中索引結(jié)構(gòu)，常用見的有兩種：B+Tree索引和Hash索引。
2.1 Hash索引
Hash索引顧名思義，基于哈希表實(shí)現(xiàn)的索引，只有精確匹配索引所有列的查詢時(shí)才有效。對于每一行數(shù)據(jù)，存儲引擎會對所有索引列計(jì)算哈希值，然后將哈希值存在哈希表中，同時(shí)哈希表中保存指向每行數(shù)據(jù)的指針。
對于哈希值相同的，采用“拉鏈法”解決哈希沖突，類似HashMap。
MySQL中Memory引擎才支持Hash索引。
Hash索引的局限性
- Hash索引只包含哈希值和行指針，而不存儲字段值，所以不能使用索引中的值來避免讀取行
- Hash索引數(shù)據(jù)并不是按照索引列的值順序存儲的，所以無法用于排序
- Hash索引也不支持部分索引匹配，因?yàn)镠ash索引始終使用的是索引列的全部內(nèi)容來計(jì)算哈希值的
- Hash索引只支持等值比較，包括
=、IN()、<>；并且不支持任何范圍查詢，例如WHERE age > 18 - 通常訪問Hash索引的數(shù)據(jù)非?？?，除非出現(xiàn)非常多的哈希沖突。因?yàn)楫?dāng)哈希沖突時(shí)，需要遍歷鏈表，一一比較行指針指向的行數(shù)據(jù)是否匹配
2.2 B+Tree索引
B+Tree索引可以說是最常見、最普遍使用的索引了，它的結(jié)構(gòu)是一個(gè)多叉搜索樹。
B+Tree的索引結(jié)構(gòu)解釋
它有以下特點(diǎn)：
- 一個(gè)節(jié)點(diǎn)內(nèi)的key從左到右是非遞減數(shù)列
- 與B-Tree不同，因?yàn)椴⒉皇撬泄?jié)點(diǎn)都具有相同的域，所以B+Tree中葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)一般大小不同。
- 非葉子節(jié)點(diǎn)不存儲data，只存儲key
- 葉子節(jié)點(diǎn)不存儲指針
- 每個(gè)葉子節(jié)點(diǎn)間有一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針【數(shù)據(jù)庫系統(tǒng)對B+Tree做的優(yōu)化】，它的目的是提高區(qū)間的訪問性能，如圖如果要查詢key為10到40的所有數(shù)據(jù)，當(dāng)找到10后，只需要順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)。
每個(gè)節(jié)點(diǎn)可以算作一個(gè)磁盤塊。真實(shí)的數(shù)據(jù)存儲在葉子節(jié)點(diǎn)里，非葉子節(jié)點(diǎn)不存儲真實(shí)數(shù)據(jù)，只存儲指引索引方向的數(shù)據(jù)項(xiàng)。
B+Tree查找過程
如果所以，如果要查找數(shù)據(jù)項(xiàng)30，那么首先會把磁盤塊1加載到內(nèi)存，此時(shí)發(fā)生一次IO，在內(nèi)存中利用二分查找確定30在20和50之間，通過磁盤塊1的第一個(gè)指針找到磁盤塊2的地址；然后把磁盤塊2加載到內(nèi)存，發(fā)生第二次IO，30在24和40之間，通過指針將磁盤塊6加載到內(nèi)存，發(fā)生第三次IO；最后在內(nèi)存中查找到數(shù)據(jù)項(xiàng)30，結(jié)束查詢，總共發(fā)生了三次IO。
估算一下：MySQL將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁，這樣每個(gè)節(jié)點(diǎn)只需要一次IO就可以完全載入。從上面過程我們可知，利用B+Tree查詢的話會發(fā)生h次IO。利用InnoDB引擎估算一下，InnoDB引擎頁的大小默認(rèn)為16KB，假設(shè)主鍵類型為BIGINT（8 byte），指針類型一般也為4或8個(gè)byte，也就是說一個(gè)頁中大概可以存儲16KB/(8 byte + 8 byte)≈1K個(gè)索引，也就是說一個(gè)高度為3的B+Tree索引可以維護(hù)10^3 * 10^3 * 10^3條記錄。當(dāng)然實(shí)際情況與這里計(jì)算的肯定有不同，但是可以知道B+Tree可以將一次查詢的IO次數(shù)控制在一個(gè)很小的次數(shù)。
B+Tree性質(zhì)
- 通過上面的分析，我們知道一個(gè)頁（節(jié)點(diǎn)）內(nèi)索引列越小，可以存放的數(shù)據(jù)項(xiàng)的數(shù)量就越多，樹的高度越低。這就是為什么要求索引字段要盡量小。這也是為什么B+Tree把真實(shí)的數(shù)據(jù)放到葉子節(jié)點(diǎn)而不是內(nèi)層節(jié)點(diǎn)，一旦放到內(nèi)層節(jié)點(diǎn)，磁盤塊的數(shù)據(jù)項(xiàng)會大幅度下降，導(dǎo)致樹增高。當(dāng)數(shù)據(jù)項(xiàng)等于1時(shí)將會退化成線性表。
-
【重要】左前綴原則。當(dāng)B+Tree的數(shù)據(jù)項(xiàng)是復(fù)合的數(shù)據(jù)結(jié)構(gòu)，比如
(name,sex,age)的時(shí)候，B+Tree是按照從左到右的順序來建立搜索樹的，比如當(dāng)(張三,male,18)來檢索的時(shí)候，B+Tree會優(yōu)先比較name來確定下一步的所搜方向，如果name相同再依次比較sex和age，最后得到檢索的數(shù)據(jù)；但當(dāng)(male,18)這樣的沒有name的數(shù)據(jù)來的時(shí)候，B+Tree就不知道如何檢索數(shù)據(jù)，因?yàn)榻+Tree的時(shí)候第一個(gè)比較因子是name，所以必須要先根據(jù)name來搜索才能知道下一步怎么查詢。比如當(dāng)(張三,18)這樣的數(shù)據(jù)來檢索時(shí)，B+Tree可以用name來指定搜索方向，但下一個(gè)字段sex的缺失，所以只能把名字等于張三的數(shù)據(jù)都找到，然后再匹配age是18的數(shù)據(jù)。
2.3 Hash索引與B+Tree索引區(qū)別
- 因?yàn)镠ash索引是直接取哈希值，所以通常在等值查詢時(shí)Hash索引要快很多，前提是該哈希值的哈希沖突較少的情況下
- 根據(jù)上文可知，Hash索引不支持范圍查詢，B+Tree索引支持范圍查詢。因?yàn)樵扔行虻臄?shù)據(jù)在經(jīng)過哈希算法后，有可能變得不是連續(xù)的了，就沒法利用索引完成范圍查詢
- 同理，Hash索引無法利用索引完成排序以及模糊查詢，例如
LIKE 'xxx%' - 同理，Hash索引不支持多列索引的左前綴匹配原則
- B+Tree索引搜索效率比較平均，在大量哈希沖突情況下，Hash索引搜索效率很低
3. MySQL索引實(shí)現(xiàn)
3.1 MyISAM索引實(shí)現(xiàn)
MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉子節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。
這里設(shè)表一共有三列，假設(shè)我們以Col1為主鍵，則圖8是一個(gè)MyISAM表的主索引（Primary key）示意?？梢钥闯鯩yISAM的索引文件僅僅保存數(shù)據(jù)記錄的地址。在MyISAM中，主索引和輔助索引（Secondary key）在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)。如果我們在Col2上建立一個(gè)輔助索引，則此索引的結(jié)構(gòu)如下圖所示：
同樣也是一顆B+Tree，data域保存數(shù)據(jù)記錄的地址。因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。
MyISAM的索引方式也叫做非聚簇索引的，之所以這么稱呼是為了與InnoDB的聚簇索引區(qū)分。
3.2 InnoDB索引實(shí)現(xiàn)
雖然InnoDB也使用B+Tree作為索引結(jié)構(gòu)，但具體實(shí)現(xiàn)方式卻與MyISAM截然不同。
第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。從上文知道，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而在InnoDB中，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這個(gè)索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。
上圖是InnoDB主索引（同時(shí)也是數(shù)據(jù)文件）的示意圖，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個(gè)可以唯一標(biāo)識數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長度為6個(gè)字節(jié)，類型為長整形。
第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域。例如，下圖為定義在Col3上的一個(gè)輔助索引：
這里以英文字符的ASCII碼作為比較準(zhǔn)則。聚簇索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。
了解不同存儲引擎的索引實(shí)現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助，例如知道了InnoDB的索引實(shí)現(xiàn)后，就很容易明白為什么不建議使用過長的字段作為主鍵，因?yàn)樗休o助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調(diào)的字段作為主鍵在InnoDB中不是個(gè)好主意，因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整，十分低效，而使用自增字段作為主鍵則是一個(gè)很好的選擇。
3.3 聚簇索引和非聚簇索引
從上文可知：
- 聚簇索引，數(shù)據(jù)文件本身就是索引文件，即將索引與數(shù)據(jù)放在一起
- 非聚簇索引，將數(shù)據(jù)與索引分開存儲，葉子節(jié)點(diǎn)存儲了指向數(shù)據(jù)位置的地址，直接指向數(shù)據(jù)行
在InnoDB中，輔助索引訪問數(shù)據(jù)時(shí)總需要二次查找
假設(shè)有如下表
- InnoDB聚簇索引
- 利用
id列進(jìn)行搜索時(shí)，將主鍵作為主索引，行數(shù)據(jù)存儲在葉子節(jié)點(diǎn)中，數(shù)據(jù)文件就是主鍵索引文件。如果利用WHERE id = 7這樣的條件查找主鍵索引，則按照B+Tree的算法找到對應(yīng)葉子節(jié)點(diǎn)，之后就可以獲得行數(shù)據(jù)。 - 如果按照
name列為條件進(jìn)行搜索，則需要兩個(gè)步驟：第一步在輔助索引B+Tree中檢索name為Breke，到達(dá)葉子節(jié)點(diǎn)獲得對應(yīng)主鍵10；第二部使用主鍵10在主索引B+Tree中在執(zhí)行一次檢索操作，最終找到葉節(jié)點(diǎn)即可獲得整行數(shù)據(jù)。
- 利用
- MyIASM非聚簇索引
非聚簇索引的主索引B+Tree和輔助索引B+Tree看上去沒有什么區(qū)別，節(jié)點(diǎn)結(jié)構(gòu)完全一致，只是存儲的內(nèi)容不同而已：主索引存儲的是面向主鍵的信息，輔助索引存儲的是面向輔助列的信息。表的數(shù)據(jù)單獨(dú)存在數(shù)據(jù)文件中，兩棵樹都是在葉子節(jié)點(diǎn)中使用一個(gè)地址執(zhí)行真正的表數(shù)據(jù)。
