也許你經常用mysql，也會經常用索引，但是對索引的原理和高級功能卻并不知道，我們在這里一起學習下。
InnoDB存儲索引
在數據庫中，如果索引太多，應用程序的性能可能會受到影響；如果索引太少，又會對查詢性能產生影響。所以，我們要追求兩者的一個平衡點，足夠多的索引帶來查詢性能提高，又不因為索引過多導致修改數據等操作時負載過高。
InnoDB支持3種常見索引：
● 哈希索引
● B+ 樹索引
● 全文索引
我們接下來要詳細講解的就是B+ 樹索引和全文索引。
哈希索引
學習哈希索引之前，我們先了解一些基礎的知識：哈希算法。哈希算法是一種常用的算法，時間復雜度為O(1)。它不僅應用在索引上，各個數據庫應用中也都會使用。
哈希表
哈希表（Hash Table）也稱散列表，由直接尋址表改進而來。
在該表中U表示關鍵字全集，K表示實際存在的關鍵字，右邊的數組（哈希表）表示在內存中可以直接尋址的連續空間，哈希表中每個插槽關聯的單向鏈表中存儲實際數據的真實地址。
如果右邊的數組直接使用直接尋址表，那么對于每一個關鍵字K都會存在一個h[K]且不重復，這樣存在一些問題，如果U數據量過大，那么對于計算機的可用容量來說有點不實際。而如果集合K占比U的比例過小，則分配的大部分空間都要浪費。
因此我們使用哈希表，我們通過一些函數h(k)來確定映射關系，這樣讓離散的數據盡可能均勻分布的利用數組中的插槽，但會有一個問題，多個關鍵字映射到同一個插槽中，這種情況稱為碰撞（collision），數據庫中采用最簡單的解決方案：鏈接法（chaining）。也就是每個插槽存儲一個單項鏈表，所有碰撞的元素會依次形成鏈表中的一個結點，如果不存在，則鏈表指向為NULL。
而使用的函數h(k)成為哈希函數，它必須能夠很好的進行散列。最好能夠避免碰撞或者達到最小碰撞。一般為了更好的處理哈希的關鍵字，我們會將其轉換為自然數，然后通過除法散列、乘法散列或者全域散列來實現。數據庫一般使用除法散列，即當有m個插槽時，我們對每個關鍵字k進行對m的取模：h(k) = k % m。
InnoDB存儲引擎中的哈希算法
InnoDB存儲引擎使用哈希算法來查找字典，沖突機制采用鏈表，哈希函數采用除法散列。對于緩沖池的哈希表，在緩存池中的每頁都有一個chain指針，指向相同哈希值的頁。對于除法散列，m的值為略大于2倍緩沖池頁數量的質數。如當前innodb_buffer_pool_size大小為10M，則共有640個16KB的頁，需要分配1280個插槽，而略大于的質數為1399，因此會分配1399個槽的哈希表，用來哈希查詢緩沖池中的頁。
而對于將每個頁轉換為自然數，每個表空間都有一個space_id，用戶要查詢的是空間中某個連續的16KB的頁，即偏移量（offset），InnoDB將space_id左移20位，再加上space_id和offset，即K=space_id
自適應哈希索引
自適應哈希索引采用上面的哈希表實現，屬于數據庫內部機制，DBA不能干預。它只對字典類型的查找非常快速，而對范圍查找等卻無能為力，如：
select * from t where f='100'；
我們可以查看自適應哈希索引的使用情況：
mysql> show engine innodb statusG; *************************** 1. row *************************** Type: InnoDB Name: Status: ===================================== 2019-05-13 23:32:21 7f4875947700 INNODB MONITOR OUTPUT ===================================== Per second averages calculated from the last 32 seconds ... ------------------------------------- INSERT BUFFER AND ADAPTIVE HASH INDEX ------------------------------------- Ibuf: size 1, free list len 1226, seg size 1228, 0 merges merged operations: insert 0, delete mark 0, delete 0 discarded operations: insert 0, delete mark 0, delete 0 Hash table size 276671, node heap has 1288 buffer(s) 0.16 hash searches/s, 16.97 non-hash searches/s
我們可以看到自適應哈希的使用情況，可以通過最后一行的hash searches/non-hash searches來判斷使用哈希索引的效率。
我們可以使用innodb_adaptive_hash_index參數來禁用或啟用此特性，默認開啟。
B+ 樹索引
B+ 樹索引是目前關系型數據庫系統中查找最為常用和有效的索引，其構造類似于二叉樹，根據鍵值對快速找到數據。B+ 樹（balance+ tree）由B樹（banlance tree 平衡二叉樹）和索引順序訪問方法（ISAM: Index Sequence Access Method）演化而來，這幾個都是經典的數據結構。而MyISAM引擎最初也是參考ISAM數據結構設計的。
基礎數據結構
想要了解B+ 樹數據結構，我們先了解一些基礎的知識。
二分查找法
又稱為折半查找法，指的是將數據順序排列，通過每次和中間值比較，跳躍式查找，每次縮減一半的范圍，快速找到目標的算法。其算法復雜度為log2(n)，比順序查找要快上一些。
如圖所示，從有序列表中查找48，只需要3步：
詳細的算法可以參考二分查找算法。
二叉查找樹
二叉查找樹的定義是在一個二叉樹中，左子樹的值總是小于根鍵值，根鍵值總是小于右子樹的值。在我們查找時，每次都從根開始查找，根據比較的結果來判斷繼續查找左子樹還是右子樹。其查找的方法非常類似于二分查找法。
平衡二叉樹
二叉查找樹的定義非常寬泛，可以任意構造，但是在極端情況下查詢的效率和順序查找一樣，如只有左子樹的二叉查找樹。
若想構造一個性能最大的二叉查找樹，就需要該樹是平衡的，即平衡二叉樹（由于其發明者為G. M. Adelson-Velsky 和 Evgenii Landis，又被稱為AVL樹）。其定義為必須滿足任何節點的兩個子樹的高度最大差為1的二叉查找樹。平衡二叉樹相對結構較優，而最好的性能需要建立一個最優二叉樹，但由于維護該樹代價高，因此一般平衡二叉樹即可。
平衡二叉樹查詢速度很快，但在樹發生變更時，需要通過一次或多次左旋和右旋來達到樹新的平衡。這里不發散講。
B+ 樹
了解了基礎的數據結構后，我們來看下B+ 樹的實現，其定義十分復雜，簡單來說就是在B樹上增加規定：
1、葉子結點存數據，非葉子結點存指針
2、所有葉子結點從左到右用雙向鏈表記錄
目標是為磁盤或其他直接存取輔助設備設計的一種平衡查找樹。在該樹中，所有的記錄都按鍵值的大小放在同一層的葉子節點上，各葉子節點之間有指針進行連接（非連續存儲），形成一個雙向鏈表。索引節點按照平衡樹的方式構造，并存在指針指向具體的葉子節點，進行快速查找。
下面的B+ 樹為數據較少時，此時高度為2，每頁固定存放4條記錄，扇出固定為5（圖上灰色部分）。葉子節點存放多條數據，是為了降低樹的高度，進行快速查找。
當我們插入28、70、95 3條數據后，B+ 樹由于數據滿了，需要進行頁的拆分。此時高度變為3，每頁依然是4條記錄，雙向鏈表未畫出但是依然是存在的，現在可以看出來是一個平衡二叉樹的雛形了。
InnoDB的B+ 樹索引
InnoDB的B+ 樹索引的特點是高扇出性，因此一般樹的高度為2~4層，這樣我們在查找一條記錄時只用I/O 2~4次。當前機械硬盤每秒至少100次I/O/s，因此查詢時間只需0.02~0.04s。
數據庫中的B+ 樹索引分為聚集索引（clustered index）和輔助索引（secondary index）。它們的區別是葉子節點存放的是否為一整行的完整數據。
聚集索引
聚集索引就是按照每張表的主鍵（唯一）構造一棵B+ 樹，同時葉子節點存放整行的完整數據，因此將葉子節點稱為數據頁。由于定義了數據的邏輯順序，聚集索引也能快速的進行范圍類型的查詢。
聚集索引的葉子節點按照邏輯順序連續存儲，葉子節點內部物理上連續存儲，作為最小單元，葉子節點間通過雙向指針連接，物理存儲上不連續，邏輯存儲上連續。
聚集索引能夠針對主鍵進行快速的排序查找和范圍查找，由于是雙向鏈表，因此在逆序查找時也非常快。
我們可以通過explain命令來分析MySQL數據庫的執行計劃：
# 查看表的定義，可以看到id為主鍵，name為普通列 mysql> show create table dimensionsConf; | Table | Create Table | dimensionsConf | CREATE TABLE `dimensionsConf` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(20) DEFAULT NULL, `remark` varchar(1024) NOT NULL, PRIMARY KEY (`id`), FULLTEXT KEY `fullindex_remark` (`remark`) ) ENGINE=InnoDB AUTO_INCREMENT=178 DEFAULT CHARSET=utf8 | 1 row in set (0.00 sec) # 先測試一個非主鍵的name屬性排序并查找，可以看到沒有使用到任何索引，且需要filesort（文件排序），這里的rows為輸出行數的預估值 mysql> explain select * from dimensionsConf order by name limit 10G; *************************** 1. row *************************** id: 1 select_type: SIMPLE table: dimensionsConf type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 57 Extra: Using filesort 1 row in set (0.00 sec) # 再測試主鍵id的排序并查找，此時使用主鍵索引，在執行計劃中沒有了filesort操作，這就是聚集索引帶來的優化 mysql> explain select * from dimensionsConf order by id limit 10G; *************************** 1. row *************************** id: 1 select_type: SIMPLE table: dimensionsConf type: index possible_keys: NULL key: PRIMARY key_len: 4 ref: NULL rows: 10 Extra: NULL 1 row in set (0.00 sec) # 再查找根據主鍵id的范圍查找，此時直接根據葉子節點的上層節點就可以快速得到范圍，然后讀取數據 mysql> explain select * from dimensionsConf where id>10 and id<10000G; *************************** 1. row *************************** id: 1 select_type: SIMPLE table: dimensionsConf type: range possible_keys: PRIMARY key: PRIMARY key_len: 4 ref: NULL rows: 56 Extra: Using where 1 row in set (0.00 sec)
輔助索引
輔助索引又稱非聚集索引，其葉子節點不包含行記錄的全部數據，而是包含一個書簽（bookmark），該書簽指向對應行數據的聚集索引，告訴InnoDB存儲引擎去哪里查找具體的行數據。輔助索引與聚集索引的關系就是結構相似、獨立存在，但輔助索引查找非索引數據需要依賴于聚集索引來查找。
全文索引
我們通過B+ 樹索引可以進行前綴查找，如：
select * from blog where content like 'xxx%';
只要為content列添加了B+ 樹索引（聚集索引或輔助索引），就可快速查詢。但在更多情況下，我們在博客或搜索引擎中需要查詢的是某個單詞，而不是某個單詞開頭，如：
select * from blog where content like '%xxx%';
此時如果使用B+ 樹索引依然是全表掃描，而全文檢索（Full-Text Search）就是將整本書或文章內任意內容檢索出來的技術。
倒排索引
全文索引通常使用倒排索引（inverted index）來實現，倒排索引和B+ 樹索引都是一種索引結構，它需要將分詞（word）存儲在一個輔助表（Auxiliary Table）中，為了提高全文檢索的并行性能，共有6張輔助表。輔助表中存儲了單詞和單詞在各行記錄中位置的映射關系。它分為兩種：
- inverted file index（倒排文件索引），表現為{單詞，單詞所在文檔ID}
- full inverted index（詳細倒排索引），表現為{單詞，(單詞所在文檔ID, 文檔中的位置)}
對于這樣的一個數據表：
倒排文件索引類型的輔助表存儲為：
詳細倒排索引類型的輔助表存儲為，占用更多空間，也更好的定位數據，比提供更多的搜索特性：
全文檢索索引緩存
輔助表是存在與磁盤上的持久化的表，由于磁盤I/O比較慢，因此提供FTS Index Cache（全文檢索索引緩存）來提高性能。FTS Index Cache是一個紅黑樹結構，根據（word, list）排序，在有數據插入時，索引先更新到緩存中，而后InnoDB存儲引擎會批量進行更新到輔助表中。
當數據庫宕機時，尚未落盤的索引緩存數據會自動讀取并存儲，配置參數innodb_ft_cache_size控制緩存的大小，默認為32M，提高該值，可以提高全文檢索的性能，但在故障時，需要更久的時間恢復。
在刪除數據時，InnoDB不會刪除索引數據，而是保存在DELETED輔助表中，因此一段時間后，索引會變得非常大，可以通過optimize table命令手動刪除無效索引記錄。如果需要刪除的內容非常多，會影響應用程序的可用性，參數innodb_ft_num_word_optimize控制每次刪除的分詞數量，默認為2000，用戶可以調整該參數來控制刪除幅度。
全文檢索限制
全文檢索存在一個黑名單列表（stopword list），該列表中的詞不需要進行索引分詞，默認共有36個，如the單詞。你可以自行調整：
mysql> select * from information_schema.INNODB_FT_DEFAULT_STOPWORD; +-------+ | value | +-------+ | a | | about | | an | | are | | as | | at | | be | | by | | com | | de | | en | | for | | from | | how | | i | | in | | is | | it | | la | | of | | on | | or | | that | | the | | this | | to | | was | | what | | when | | where | | who | | will | | with | | und | | the | | www | +-------+ 36 rows in set (0.00 sec)
其他限制還有：
● 每張表只能有一個全文檢索索引
● 多列組合的全文檢索索引必須使用相同的字符集和字符序，不了解的可以參考二分查找算法
● 不支持沒有單詞界定符（delimiter）的語言，如中文、日語、韓語等
全文檢索
我們創建一個全文索引：
mysql> create fulltext index fullindex_remark on dimensionsConf(remark); Query OK, 0 rows affected, 1 warning (0.39 sec) Records: 0 Duplicates: 0 Warnings: 1 mysql> show warnings; +---------+------+--------------------------------------------------+ | Level | Code | Message | +---------+------+--------------------------------------------------+ | Warning | 124 | InnoDB rebuilding table to add column FTS_DOC_ID | +---------+------+--------------------------------------------------+ 1 row in set (0.00 sec)
全文檢索有兩種方法：
● 自然語言（Natural Language），默認方法，可省略：（IN NATURAL LANGUAE MODE）
● 布爾模式（Boolean Mode）：（IN BOOLEAN MODE）
自然語言還支持一種擴展模式，后面加上：（WITH QUERY EXPANSION）。
其語法為MATCH()…AGAINST()，MATCH指定被查詢的列，AGAINST指定何種方法查詢。
自然語言檢索
mysql> select remark from dimensionsConf where remark like '%baby%'; +-------------------+ | remark | +-------------------+ | a baby like panda | | a baby like panda | +-------------------+ 2 rows in set (0.00 sec) mysql> select remark from dimensionsConf where match(remark) against('baby' IN NATURAL LANGUAGE MODE); +-------------------+ | remark | +-------------------+ | a baby like panda | | a baby like panda | +-------------------+ 2 rows in set (0.00 sec) # 查看下執行計劃，使用了全文索引排序 mysql> explain select * from dimensionsConf where match(remark) against('baby'); +----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+ | 1 | SIMPLE | dimensionsConf | fulltext | fullindex_remark | fullindex_remark | 0 | NULL | 1 | Using where | +----+-------------+----------------+----------+------------------+------------------+---------+------+------+-------------+ 1 row in set (0.00 sec)
我們也可以查看各行數據的相關性，是一個非負的浮點數，0代表沒有相關性：
mysql> select id,remark,match(remark) against('baby') as relevance from dimensionsConf; +-----+-----------------------+--------------------+ | id | remark | relevance | +-----+-----------------------+--------------------+ | 106 | c | 0 | | 111 | 運營商 | 0 | | 115 | a baby like panda | 2.1165735721588135 | | 116 | a baby like panda | 2.1165735721588135 | +-----+-----------------------+--------------------+ 4 rows in set (0.01 sec)
布爾模式檢索
MySQL也允許用修飾符來進行全文檢索，其中特殊字符會有特殊含義：
- +: 該word必須存在
- -: 該word必須排除
- （no operator）: 該word可選，如果出現，相關性更高
- @distance: 查詢的多個單詞必須在指定范圍之內
- >: 出現該單詞時增加相關性
- <:>
- ~: 出現該單詞時相關性為負
- *: 以該單詞開頭的單詞
- “: 表示短語
# 代表必須有a baby短語，不能有man，可以有lik開頭的單詞，可以有panda， select remark from dimensionsConf where match(remark) against('+"a baby" -man lik* panda' IN BOOLEAN MODE);
擴展查詢
當查詢的關鍵字太短或不夠清晰時，需要用隱含知識來進行檢索，如database關聯的MySQL/DB2等。但這個我并沒太明白怎么使用，后續補充吧。
類似的使用是：
select * from articles where match(title,body) against('database' with query expansion);
推薦學習：二分查找算法
