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

常見的索引：

1 B+ 數(shù)索引

2 全文索引

3 哈希索引 ： 哈希索引是自適應(yīng)的， InnoDB 存儲(chǔ)引擎根據(jù)表的使用情況自動(dòng)為表生成哈希索引。

注意： B+ 數(shù)中 B 不是代表二叉（binary）， 而是代表平衡（balance）, 因?yàn)?B+ 數(shù)是從最早的平衡二叉樹演化過來的， 但是 B+ 數(shù)不是一個(gè)二叉樹。

B+ 數(shù)索引并不能找到一個(gè)給定鍵值的具體行。 B+ 數(shù)索引能找到的只是被查找數(shù)據(jù)所在的頁。 然后數(shù)據(jù)庫通過把頁讀入到內(nèi)存， 再在內(nèi)存中進(jìn)行查找， 最后得到要查找的數(shù)據(jù)。

5.2 數(shù)據(jù)結(jié)構(gòu)與算法

5.2.1 二分查找法

每頁 Page Directory 中的槽 是按照主鍵的順序存放的， 對(duì)于某一條具體記錄的查詢時(shí)通過對(duì) Page Directory 進(jìn)行二分查找得到的。（待理解）

5.2.2 二叉搜索樹和平衡二叉樹

在二叉查找樹中， 左子樹的鍵值總是小于根的鍵值， 右子樹的鍵值總是大于根的鍵值。

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

5.3 B+ 樹

5.3.1 B+ 數(shù)的插入操作

因?yàn)?B+ 數(shù)結(jié)構(gòu)主要用于磁盤， 頁的拆分意味著磁盤的操作， 所以應(yīng)該在可能的情況下盡量減少頁的拆分拆分。 因此， B+ 數(shù)同樣提供了類似于平衡二叉樹的旋轉(zhuǎn)（Rotation）功能。(待理解)

5.3.2 B+ 數(shù)的刪除操作

與插入不同的是， 刪除根據(jù)填充因子的變化來衡量。

5.4 B+ 數(shù)索引

B+ 索引在數(shù)據(jù)庫中一個(gè)特點(diǎn)是高扇出性， 因此在數(shù)據(jù)庫中， B+ 數(shù)的高度一般都在 2~4 層。

B+ 數(shù)索引分為聚集索引（clustered index）和輔助索引（secondary index） ，內(nèi)部都是 B+ 數(shù)， 葉子節(jié)點(diǎn)存放著所有的數(shù)據(jù). 不同的是， 葉子節(jié)點(diǎn)存放的是否是一整行的信息。（存放所有數(shù)據(jù)存疑）

5.4.1 聚集索引 **

每張表只能擁有一個(gè)聚集索引。

// 通過 py_innodb_page_info 工具分析表空間。page level 為 0000 的即是數(shù)據(jù)頁。 要分析 page // level 為 0001 的頁， 當(dāng)前聚集索引的 B+ 樹高度為 2 ， 該頁是 B+ 數(shù)的根??????????????????????????????????????? // 待實(shí)驗(yàn)

聚集索引的存儲(chǔ)并不是物理上連續(xù)的， 而是邏輯上連續(xù)的。 這其中有兩點(diǎn)： 一是頁通過雙向鏈表鏈接， 按照主鍵順序排序； 另一點(diǎn)是每個(gè)頁中的記錄也是通過雙向鏈表進(jìn)行維護(hù)的， 物理存儲(chǔ)上可以同樣不按照主鍵存儲(chǔ)。

聚集索引的另一個(gè)好處是， 它對(duì)于主鍵排序查找和范圍查找速度非?？臁?/p>

可以看到雖然使用 order by 對(duì)記錄進(jìn)行排序， 但在實(shí)際過程中并沒有進(jìn)行 filesort 操作。

另一個(gè)是范圍查詢（range query）， 如果要查找主鍵某一個(gè)范圍內(nèi)的數(shù)據(jù)， 通過葉子節(jié)點(diǎn)的上層中間節(jié)點(diǎn)就可以得到頁的范圍， 之后直接讀取數(shù)據(jù)頁即可。

rows 代表一個(gè)估計(jì)的值而不是一個(gè)確切的值。

??????????????????????????????????

5.4.2 輔助索引 **

當(dāng)通過輔助索引來尋找數(shù)據(jù)時(shí)， InnoDB 存儲(chǔ)引擎會(huì)遍歷輔助索引并通過葉級(jí)別的指針獲得執(zhí)行指向聚集索引的主鍵， 然后通過主鍵索引來找到一個(gè)完整的行記錄。

5.4.3 B+ 樹索引的分裂

5.4.4 B+ 樹索引的管理

1 索引管理

查看索引信息， show index from t；

Cardinality: 非常關(guān)鍵的值， 表示索引中唯一值的數(shù)據(jù)估計(jì)值。

Cardinality 值非常關(guān)鍵， 優(yōu)化器會(huì)根據(jù)這個(gè)值來判斷是否使用這個(gè)索引， 但這個(gè)值并不是實(shí)時(shí)更新的， 即并非每次索引的更新都會(huì)更新該值，因?yàn)檫@樣代價(jià)太大了。如果需要更新索引 Cardinality 的信息， 可以使用 analyze table 命令。

2 Fast Index Creation(快速索引創(chuàng)建)

由于 FIC 在索引創(chuàng)建的過程中對(duì)表加上了 S 鎖， 因此在創(chuàng)建過程中只能對(duì)該表進(jìn)行讀操作， 若有大量事務(wù)需要對(duì)目標(biāo)進(jìn)行寫操作， 那么數(shù)據(jù)庫的服務(wù)同樣不可用。 此外， FIC 方式只限定于輔助索引， 對(duì)于主鍵的創(chuàng)建和刪除同樣需要重建一張表。

3 Online Schema Change（在線結(jié)構(gòu)改變）

Mysql 5.6 版本開始支持 Online DDL 操作， 其允許輔助索引創(chuàng)建的同時(shí)， 還允許其他如 insert， update， delete 這類 DML 操作， 極大地提高了 MySQL 在生產(chǎn)環(huán)境的可用性。

其他

主鍵與聚集索引的區(qū)別：

問題：

聚集索引， 與 輔助索引 分別位于 B 數(shù)的什么位置？

1 若為聚集索引， 樹高為 3 的樹，最多搜索 3 次 IO

2 若為輔助索引，

輔助索引：

http://www.zhaochenxi.com/2015/07/03/mysql-innodb%E8%BE%85%E5%8A%A9%E7%B4%A2%E5%BC%95/

5.5 Cardinality （基數(shù)值）

5.5.1 什么是Cardinality

如果某個(gè)字段的取值范圍很廣， 幾乎沒有重復(fù)， 即屬于高選擇性， 此時(shí)使用 B+ 數(shù)索引最合適。通過 show index 結(jié)構(gòu)中 Cardinality 來判斷高選擇性。

5.5.2 InnoDB 存儲(chǔ)引擎的Cardinality統(tǒng)計(jì) **

在 InnoDB 存儲(chǔ)引擎中， Cardinality 統(tǒng)計(jì)信息的更新發(fā)生在兩個(gè)操作中： Insert 和 update。 不可能每次 insert 和 update 更新 Cardinality 信息， 這樣會(huì)增加系統(tǒng)負(fù)擔(dān)， 對(duì)于大表統(tǒng)計(jì)， 時(shí)間成本太大。

Cardinality 信息的更新策略：

一 表中 1 / 16 的數(shù)據(jù)已經(jīng)發(fā)生過變化

二 stat_modified_counter > 2 000 000 000

第一種策略為自從上次統(tǒng)計(jì) Cardinality 信息后， 表中 1 / 16 的數(shù)據(jù)已經(jīng)發(fā)生變化。

第二種情況考慮的是， 如果表中某一行數(shù)據(jù)頻繁地進(jìn)行更新操作， 這時(shí)表中的數(shù)據(jù)實(shí)際并沒有增加， 實(shí)際發(fā)生變化的還是這一行數(shù)據(jù)。stat_modified_counter, 用來表示發(fā)生變化的次數(shù)， 當(dāng) stat_modified_counter 大于 2 000 000 000 時(shí)， 則同樣需要更新 Cardinality 信息。

第三種 即為 analyze table 來手動(dòng)更新。?

參數(shù) innodb_stats_sample_pages 設(shè)置統(tǒng)計(jì) Cardinality 時(shí)每次采樣頁的數(shù)量， 默認(rèn)為 8. ?參數(shù) innodb_stats_method 用來判斷如何對(duì)待索引的 NULL 值記錄， 默認(rèn)值為 nulls_equal, 表示 將 NULL 值記錄視為相等的記錄。 其有效值還有 nulls_unequal, nulls_ignored.

5.6 B+ 樹索引的使用

5.6.1 不同應(yīng)用中 B+ 數(shù)索引的使用。

5.6.2 聯(lián)合索引 **

對(duì)于查詢 select * from table where a=xxx and b=xxx , 顯然可以使用（a, b） 聯(lián)合索引； 對(duì)于單個(gè) a 列的查詢 select * from table where a=xxx, 也可以使用 （a, b）索引。 但對(duì)于 b 列的查詢 select * from table where b=xxx, 則不能使用 該聯(lián)合索引。// 葉子節(jié)點(diǎn)的 b 值， 1,2,1,4,1,2 顯然不是排序的。

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

5.6.3 覆蓋索引（covering index）

即從輔助索引中就可以得到查詢的記錄， 而不需要查詢聚集索引中的記錄。 使用覆蓋索引的一個(gè)好處是輔助索引不包含整行記錄的所有信息， 故其大小要遠(yuǎn)小于聚集索引， 因此可以減少大量的 IO 操作。

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

5.6.5 索引提示

使用 use index 來告訴優(yōu)化器可以選擇某索引：

select * from t use index(a) where a=1 and b=2;

use index 只是告訴優(yōu)化器可以選擇該索引， 實(shí)際上優(yōu)化器還是根據(jù)自己的判斷進(jìn)行選擇。 通過 force index 來指定某個(gè)索引來完成查詢。

5.6.6 Multi-Range Read 優(yōu)化 （沒看懂）

5.6.7 Index Condition Pushdown（ICP）優(yōu)化 （沒看懂）

5.7 哈希算法

5.7.1 哈希表

5.7.2 InnoDB 存儲(chǔ)引擎中的哈希算法

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

自適應(yīng)哈希索引由 innodb 存儲(chǔ)引擎自己控制的。 可以通過參數(shù) Innodb_adaptive_hash_index 來禁用或啟用該特性， 默認(rèn)為開啟。

5.8 全文檢索

5.8.1 概述

從 Innodb 1.2.x 開始， innodb 開始支持全文檢索， 支持 MyISAM 存儲(chǔ)引擎的全部功能， 并且還支持其他的一些特性。

5.8.2 反向索引，（叫倒排索引， 不能很好表達(dá) 索引從 關(guān)鍵詞 -> 文檔的關(guān)系）

全文檢索通常使用 inverted index (反向索引)來實(shí)現(xiàn)。 反向索引同 B+ 樹索引一樣， 也是一種索引結(jié)構(gòu)。 它在輔助表（auxiliary table）中存儲(chǔ)了單詞與單詞自身在一個(gè)或多個(gè)文檔所在的位置之間的映射。擁有兩種表現(xiàn)形式。

inverted file index ，表現(xiàn)形式為{單詞， 單詞所在文檔的 ID}

full inverted index ,表現(xiàn)形式為 {單詞， （單詞所在文檔的 ID， 在具體文檔中的位置）}

相比之下， full inverted index 占用更多的空間， 但是更好地定位數(shù)據(jù)， 并擴(kuò)充一些其他的搜索特性。

5.8.3 InnoDB 全文索引

問： Auxiliary ?table ,在什么位置？

Innodb 從 1.2.x 開始支持全文檢索， 采用 full inverted index 形式。

Auxiliary Table 是持久的表， 存放在磁盤上。 FTS Index Cache （全文檢索索引緩存）， 用來提高全文檢索的性能。

FTS Index Cache 是一個(gè)紅黑數(shù)結(jié)構(gòu)， 其根據(jù)（word , ilist） 進(jìn)行排序。Innodb 存儲(chǔ)引擎會(huì)批量對(duì) Auxiliary Table 進(jìn)行更新， 而不是每次插入后更新一次 Auxiliary Table.

設(shè)置 innodb_ft_aux_table 來觀察 反向索引的 auxiliary table。?

set global innodb_ft_aux_table = "test/fts_a";

在 information_schema 架構(gòu)的表 innodb_ft_index_table 得到表 fts_a 的分詞信息。

參數(shù) innodb_ft_cache_size 來控制 FTS Index Cache 的大小， 默認(rèn)為 32M.?

在 Innodb 中， 與 word 進(jìn)行映射的列 FTS_DOC_ID, 其類型必須是 BIGINT UNSIGNED NOT　NULL. 并且 INNODB會(huì)自動(dòng) 在該列上加入一個(gè)名叫 FTS_DOC_ID_INDEX 的 unique index. 上述操作都由 INNODB 自己完成， 用戶也可以在建表時(shí)自己添加 FTS_DOC_ID 以及相應(yīng)的 Unique Index.

文檔中分詞插入操作實(shí)在事務(wù)提交時(shí)完成， 然而對(duì)于刪除操作， 其在事務(wù)提交時(shí)， 不刪除磁盤 Auxiliary Table 中的記錄， 而只是刪除 FTS Cache Index 中的記錄。并將其保存在 DELETED auxiliary table 中。在 information_schema 庫中的 innodb_ft_deleted 表中觀察 FTS Document ID.

Innodb 提供了一種方式， 允許用戶手工將已經(jīng)刪除的記錄從索引中徹底刪除， 該命令為 optimize table. 因?yàn)樵撁钸€會(huì)進(jìn)行一些其他操作， 如 Cardinality 的重新統(tǒng)計(jì)， 若用戶僅對(duì) 反向索引進(jìn)行操作， 可以通過參數(shù) innodb_optimize_fulltext_only.

mysql>set global innodb_optimize_fulltext_only=1;

mysql>optimize table fts_a;

運(yùn)行 optimize table 可將記錄進(jìn)行徹底的刪除， 并且徹底刪除的文檔 ID 會(huì)記錄到表 INNODB_FT_BEING_DELETED 中。

stopword 列, 表示該列表中的 word 不需要對(duì)其進(jìn)行索引分詞操作。在 數(shù)據(jù)庫 information_schema 庫中， 表明 innodb_ft_default_stopword, 默認(rèn)有 36 個(gè)stopword. 此外用戶可以通過 參數(shù) innodb_ft_server_stopword_table 來定義 stopword 列表。如：

mysql>set global innodb_ft_server_stopword_table="test/user_stopword";

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

一 每張表只能有一個(gè)全文檢索的索引。

二 由多列組合而成的全文檢索的索引列必須使用相同的字符集與排序規(guī)則。

三 不支持沒有單詞界定符（delimiter）的語言， 如 中文， 日文， 韓語等。

創(chuàng)建全文索引：

create fulltext index idx_fts on fts_a(body);

5.8.4 全文檢索

1 Natural Lanuage (默認(rèn)的全文檢索查詢模式)

select * from fts_a where match(body) against('Porridge');

select fts_doc_id, body, match(body) against('Porridge' in natural language mode) as relevance from fts_a;

用 explain 的顯示中， type 顯示 fulltext, 即表示使用全文檢索的反向索引。

在 where 條件中使用 match 函數(shù)， 查詢返回的結(jié)果是根據(jù)相關(guān)性（relevance）進(jìn)行降序排列的， 即相關(guān)性最高的結(jié)果放在第一位。相關(guān)性依據(jù)以下四個(gè)條件：

一 word 是否在文檔中出現(xiàn)。

二word 在文檔中出現(xiàn)的次數(shù)。

三 word 在索引列中的數(shù)量。

四 多少個(gè)文檔包含該 word。

參數(shù) innodb_ft_min_token_size 和 innodb_ft_max_token_size 控制 innodb 存儲(chǔ)引擎查詢字符的長度。

2 Boolean

當(dāng)使用該修飾符時(shí)， 查詢字符串的前后字符會(huì)有特殊的含義， 如下例中 + 和 - 表示這個(gè)單詞必須出現(xiàn)， 或者一定不存在。

select * from fts_a where ?match(body) against('+please -hot' IN BOOLEAN MODE);

3 Query Expansion

mysql 還支持全文檢索的擴(kuò)展查詢。 這種查詢通常在查詢的關(guān)鍵詞太短， 用戶需要 implied knowledge(隱含只是時(shí))進(jìn)行。該查詢分兩個(gè)階段。

第一階段：根據(jù)搜索的單詞進(jìn)行全文索引查詢。

第二階段： 根據(jù)第一階段產(chǎn)生的分詞再進(jìn)行一次全文檢索查詢。

select * from articles where match(title, body) against('database' in natural language mode);

select * from articles where match(title, body) against('database' with query expansion);