1.InnoDB存儲(chǔ)引擎索引概述

InnoDB支持以下幾種常見(jiàn)的索引：

• B+樹(shù)索引：傳統(tǒng)意義上的索引余佛，目前關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)中查找最為常用和最為有效的索引挺邀。B+樹(shù)索引并不能找到一個(gè)給定鍵值的具體行玛臂，只能找到數(shù)據(jù)行所在的頁(yè)剩辟，然后通過(guò)把頁(yè)讀入到內(nèi)存，再在內(nèi)存中進(jìn)行查找，最后得到要查找的數(shù)據(jù)滚秩。
• 全文索引
• 哈希索引：自適應(yīng)的，InnoDB會(huì)根據(jù)表的使用情況自動(dòng)為表生成哈希索引淮捆，不能人為干預(yù)是否在一張表中生成哈希索引郁油。

2.數(shù)據(jù)結(jié)構(gòu)預(yù)算法

①二分查找法（binary search）

也稱為折半查找法本股，基本思想是：將記錄按有序化（遞增或遞減）排列，在查找過(guò)程中采用跳躍式方式查找已艰，即先以有序數(shù)列的中點(diǎn)位置為比較對(duì)象痊末，如果要的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分哩掺，否則為右半部分凿叠。通過(guò)一次比較，將查找區(qū)間縮小一半嚼吞。

每頁(yè)P(yáng)age Directory中的槽是按照主鍵的順序存放的盒件，對(duì)于某一條具體記錄的查詢，是通過(guò)對(duì)Page Directory進(jìn)行二分查找得到的舱禽。

②二叉查找樹(shù)和平衡二叉樹(shù)

B+樹(shù)是通過(guò)二叉查找樹(shù)炒刁，再由平衡二叉樹(shù)，B樹(shù)演化而來(lái)誊稚。

二叉查找樹(shù)：左子樹(shù)的鍵值總是小于跟的鍵值翔始，右子樹(shù)的鍵值總是大于根的鍵值。

若想最大性能地構(gòu)造一顆二叉查找樹(shù)里伯，需要這棵二叉查找樹(shù)是平衡的城瞎，從而引出新的定義——平衡二叉樹(shù)，或稱為AVL樹(shù)疾瓮。

平衡二叉樹(shù)：首先符合二叉查找樹(shù)的定義脖镀，其次必須滿足任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差為1.

對(duì)一顆平衡樹(shù)的維護(hù)是有一定開(kāi)銷的，不過(guò)平衡二叉樹(shù)多用于內(nèi)存結(jié)構(gòu)對(duì)象中狼电，因此維護(hù)的開(kāi)銷相對(duì)較小蜒灰。

3.B+樹(shù)

B+樹(shù)是為磁盤或其他直接存取輔助設(shè)備設(shè)計(jì)的一種平衡查找樹(shù)。在B+樹(shù)中肩碟，所有記錄節(jié)點(diǎn)都是按鍵值的大小順序存放在同一層的葉子節(jié)點(diǎn)上强窖，由各葉子節(jié)點(diǎn)指針進(jìn)行連接。

例：B+樹(shù)高度為2削祈，每頁(yè)可存放4條記錄翅溺，扇出（fan out）為5

①B+樹(shù)的插入操作

基礎(chǔ)：

依次插入：28、70岩瘦、95

可以看到，不管怎么變化窿撬，B+樹(shù)總是會(huì)保持平衡启昧。但是為了保持平衡對(duì)于新插入的鍵值可能需要做大量的拆分頁(yè)操作。因?yàn)锽+樹(shù)結(jié)構(gòu)主要用于磁盤劈伴，頁(yè)的拆分意味著磁盤的操作密末，所以應(yīng)該在可能的情況下盡量減少頁(yè)的拆分操作握爷，因此，B+樹(shù)同樣提供了類似于平衡二叉樹(shù)的旋轉(zhuǎn)功能严里。

如插入70時(shí)新啼，實(shí)際是如下情況：

②B+樹(shù)的刪除操作

填充因子：50%是填充因子可設(shè)的最小值

基礎(chǔ)：

依次刪除：70、25刹碾、60

4.B+樹(shù)索引

B+樹(shù)索引的本質(zhì)是B+樹(shù)在數(shù)據(jù)庫(kù)中的實(shí)現(xiàn)燥撞。但是B+索引在數(shù)據(jù)庫(kù)中有一個(gè)特點(diǎn)是高扇出性，因此在數(shù)據(jù)庫(kù)中迷帜，B+樹(shù)的高度一般都在2~4層物舒，也就是說(shuō)查找某一鍵值的行記錄時(shí)最多只需要2到4次IO。

B+樹(shù)索引分為聚集索引和輔助索引戏锹，內(nèi)部都是B+樹(shù)的冠胯，葉子節(jié)點(diǎn)存放著所有的數(shù)據(jù)。聚集索引和輔助索引不同的是锦针，葉子節(jié)點(diǎn)存放的是否是一整行的信息荠察。

①聚集索引（clustered index）

聚集索引就是按照每張表的主鍵構(gòu)造一棵B+樹(shù)，同時(shí)葉子節(jié)點(diǎn)中存放的即為整張表的行記錄數(shù)據(jù)奈搜，也將聚集索引的葉子節(jié)點(diǎn)稱為數(shù)據(jù)頁(yè)悉盆。聚集索引的這個(gè)特性決定了索引組織表中數(shù)據(jù)也是索引的一部分。同B+樹(shù)結(jié)構(gòu)一樣媚污，每個(gè)數(shù)據(jù)頁(yè)都通過(guò)一個(gè)雙向鏈表來(lái)進(jìn)行鏈接舀瓢。

由于實(shí)際的數(shù)據(jù)頁(yè)只能按照一棵B+樹(shù)進(jìn)行排序，因此每張表只能擁有一個(gè)聚集索引耗美。

②輔助索引（secondary index）

也稱為非聚集索引京髓。葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)。葉子節(jié)點(diǎn)除了包含鍵值以外商架，每個(gè)葉子節(jié)點(diǎn)中的索引行中還包含了一個(gè)書(shū)簽堰怨，該書(shū)簽用來(lái)告訴InnoDB哪里可以找到與索引相對(duì)應(yīng)的行數(shù)據(jù)。由于InnoDB表是索引組織表蛇摸，因此InnoDB的輔助索引的書(shū)簽就是相應(yīng)行數(shù)據(jù)的聚集索引鍵备图。

輔助索引的存在并不影響數(shù)據(jù)在聚集索引中的組織，因此每張表上可以有多個(gè)輔助索引赶袄。

當(dāng)通過(guò)輔助索引尋找數(shù)據(jù)時(shí)揽涮，假設(shè)輔助索引樹(shù)的高度為3，聚集索引樹(shù)的高度同樣為3饿肺，查找一個(gè)完整行數(shù)據(jù)所在的頁(yè)需要6次邏輯IO訪問(wèn)蒋困。（先遍歷輔助索引樹(shù)找到指定主鍵，再通過(guò)主鍵對(duì)聚集索引樹(shù)查找）

5.Cardinality值

并不是在所有的查詢條件中出現(xiàn)的列都需要添加索引敬辣。對(duì)于生命時(shí)候添加B+樹(shù)索引雪标，一般經(jīng)驗(yàn)是零院，在訪問(wèn)表中很少一部分時(shí)使用B+樹(shù)索引才有意義。

對(duì)于性別字段村刨、地區(qū)字段告抄、類型字段，它們可取值的范圍很小嵌牺，稱為低選擇性打洼。按性別查詢時(shí)，得到的結(jié)果可能是該表50%的數(shù)據(jù)髓梅，這時(shí)添加B+樹(shù)索引是完全沒(méi)有必要的拟蜻。相反如果某個(gè)字段的取值范圍很廣，幾乎沒(méi)有重復(fù)枯饿，即屬于高選擇性酝锅，則此時(shí)使用B+樹(shù)索引是最適合的。例如奢方，對(duì)于姓名字段搔扁。

怎樣查看索引是否是高選擇性的呢？可以通過(guò)show index from table結(jié)果中的列Cardinality來(lái)觀察蟋字。Cardinality表示索引中不重復(fù)記錄數(shù)量的預(yù)估值稿蹲，注意這不是一個(gè)準(zhǔn)確值。實(shí)際應(yīng)用中鹊奖，Cardinality/n_rows_in_table應(yīng)盡可能地接近1.如果非常小苛聘，那么用戶需要考慮是否還有必要?jiǎng)?chuàng)建這個(gè)索引。

6.B+樹(shù)索引的使用

①聯(lián)合索引

聯(lián)合索引本質(zhì)上來(lái)說(shuō)也是一棵B+樹(shù)忠聚，不同的是聯(lián)合索引的鍵值的數(shù)量不是1设哗，而是大于等于2。

如鑒定兩個(gè)整型的列a两蟀、b組成聯(lián)合索引：

B+樹(shù)索引先按第一個(gè)列a來(lái)排序网梢，列a相同的再按列b來(lái)排序。所以where a=xx and b=xxx和where a= xx 都可以使用（a赂毯，b）聯(lián)合索引战虏，但是where b=xxx就不可以使用這棵B+樹(shù)索引了。

聯(lián)合索引的好處是已經(jīng)對(duì)第二個(gè)鍵值進(jìn)行了排序處理党涕。

聯(lián)合索引（a烦感，b，c）

可以直接通過(guò)聯(lián)合索引得到結(jié)果：

select ... from table where a=xxx order by b

select ... from table where a=xxx and b=xxx order by c

聯(lián)合索引不能直接得到結(jié)果膛堤，還需要執(zhí)行一次filesort排序操作手趣，因?yàn)樗饕齛，c并未排序：

select ... from table where a=xxx order by c

②覆蓋索引

或稱為索引覆蓋骑祟，即從輔助索引中就可以得到查詢的記錄回懦，而不需要查詢聚集索引中的記錄。（查詢的列都是輔助索引列）

使用覆蓋索引的好處：輔助索引不包含整行記錄的所有信息次企，故其大小要遠(yuǎn)小于聚集索引怯晕，因此可以減少大量的IO操作。

輔助索引包含了主鍵信息缸棵，因此其葉子節(jié)點(diǎn)存放數(shù)據(jù)為（primary key1,primary key2,...,key1,key2,...）舟茶。下列語(yǔ)句都可以僅使用一次輔助聯(lián)合索引來(lái)完成查詢：

select key2 from table where key1=xxx;

select primary key2,key2 from table where key1=xxx;

select primary key1,key2 from table where key1=xxx;

select primary key1,primary key2,key2 from table where key1=xxx;

覆蓋索引另一個(gè)好處是對(duì)某些統(tǒng)計(jì)問(wèn)題而言的。

例：buy_log堵第，輔助索引userId:userId, userId_2: (userId, buy_date)

select count(*) from buy_log;//使用userId索引

select count(*) from buy_log where buy_date>='2011-01-01' and buy_date<'2011-02-01';//使用userId_2索引

③優(yōu)化器選擇不使用索引的情況

用輔助索引范圍查詢吧凉，且數(shù)據(jù)量占整個(gè)表蠻大一部分時(shí)（20%左右），優(yōu)化器會(huì)通過(guò)聚集索引來(lái)查找數(shù)據(jù)（表掃描）踏志。

因?yàn)檩o助索引上沒(méi)有整行數(shù)據(jù)阀捅，如果對(duì)輔助索引查詢到指定主鍵后，還需要一次查聚集索引來(lái)查找整行數(shù)據(jù)的信息针余。雖然輔助索引中數(shù)據(jù)是順序存放的饲鄙，但再一次進(jìn)行書(shū)簽查找的數(shù)據(jù)則是無(wú)序的，因此變?yōu)榱舜疟P上的離散讀操作圆雁。但是離散讀是遠(yuǎn)遠(yuǎn)慢于順序讀的忍级。

可以強(qiáng)制使用 force index 來(lái)強(qiáng)制使用某個(gè)索引，如果認(rèn)為使用輔助索引可以帶來(lái)更好的性能伪朽，可以使用force index轴咱。

如：select * from orderDetails force index(orderId) where orderId > 10000 and orderId < 102000;

7.全文檢索

B+樹(shù)索引對(duì)于 like ‘xxx%’是支持的，但是對(duì)于 like ‘%xxx%’就需要進(jìn)行索引的掃描來(lái)得到結(jié)果了烈涮。

全文檢索是將存儲(chǔ)于數(shù)據(jù)庫(kù)中的整本書(shū)或整篇文章的任意內(nèi)容信息查找出來(lái)的技術(shù)朴肺，它可以根據(jù)需要獲得全文中有關(guān)文章、節(jié)跃脊、段宇挫、句、詞等信息酪术，也可以進(jìn)行各種統(tǒng)計(jì)和分析器瘪。

InnoDB 1.2x版本開(kāi)始，InnoDB存儲(chǔ)引擎開(kāi)始支持全文索引绘雁，其支持MyISAM存儲(chǔ)引擎的全部功能橡疼，并且還支持其他的一些特性。

①倒排索引（inverted index）

全文檢索通常使用倒排索引來(lái)實(shí)現(xiàn)庐舟。它在輔助表（auxiliary table）中存儲(chǔ)了單詞與單詞自身在一個(gè)或多個(gè)文檔中所在位置之間的映射欣除。這通常利用關(guān)聯(lián)數(shù)組實(shí)現(xiàn)，擁有兩種表現(xiàn)形式：

• inverted file index挪略，其表現(xiàn)形式為{單詞历帚，單詞所在文檔的ID}
• full inverted index滔岳，其表現(xiàn)形式為{單詞，（單詞所在文檔的ID挽牢，在具體文檔中的位置）}

如：

②InnoDB全文檢索

InnoDB采用 full inverted index的方式谱煤。

示例：

create table fts_a(FTS_DOC_ID bigint unsigned auto_increment not null, body text, primary key(FTS_DOC_ID));

插入數(shù)據(jù)

create fulltext index idx_fts on fts_a(body);

set global innodb_ft_aux_table='cs/fts_a';

select * from information_schema.INNODB_FT_INDEX_TABLE;

當(dāng)前InnoDB存儲(chǔ)引擎的全文檢索還存在以下的限制：

• 每張表只能有一個(gè)全文檢索的索引
• 由多列組合而成的全文檢索的索引列必須使用相同的字符集與排序規(guī)則
• 不支持沒(méi)有單詞界定符的語(yǔ)言，如中文禽拔、日語(yǔ)刘离、漢語(yǔ)等。

③全文檢索

MySQL數(shù)據(jù)庫(kù)支持全文檢索（full-text-search）的查詢睹栖，語(yǔ)法為：