InnoDB存儲索引

在數(shù)據(jù)庫中，如果索引太多，應(yīng)用程序的性能可能會受到影響；如果索引太少，又會對查詢性能產(chǎn)生影響。所以，我們要追求兩者的一個平衡點，足夠多的索引帶來查詢性能提高，又不因為索引過多導(dǎo)致修改數(shù)據(jù)等操作時負(fù)載過高。

InnoDB支持3種常見索引：

• 哈希索引
• B+樹索引
• 全文索引

我們接下來要詳細(xì)講解的就是B+樹索引和全文索引。

哈希索引

學(xué)習(xí)哈希索引之前，我們先了解一些基礎(chǔ)的知識：哈希算法。哈希算法是一種常用的算法，時間復(fù)雜度為O(1)。它不僅應(yīng)用在索引上，各個數(shù)據(jù)庫應(yīng)用中也都會使用。

哈希表

哈希表（Hash Table）也稱散列表，由直接尋址表改進而來。

在該表中U表示關(guān)鍵字全集，K表示實際存在的關(guān)鍵字，右邊的數(shù)組（哈希表）表示在內(nèi)存中可以直接尋址的連續(xù)空間，哈希表中每個插槽關(guān)聯(lián)的單向鏈表中存儲實際數(shù)據(jù)的真實地址。

如果右邊的數(shù)組直接使用直接尋址表，那么對于每一個關(guān)鍵字K都會存在一個h[K]且不重復(fù)，這樣存在一些問題，如果U數(shù)據(jù)量過大，那么對于計算機的可用容量來說有點不實際。而如果集合K占比U的比例過小，則分配的大部分空間都要浪費。

因此我們使用哈希表，我們通過一些函數(shù)h(k)來確定映射關(guān)系，這樣讓離散的數(shù)據(jù)盡可能均勻分布的利用數(shù)組中的插槽，但會有一個問題，多個關(guān)鍵字映射到同一個插槽中，這種情況稱為碰撞（collision），數(shù)據(jù)庫中采用最簡單的解決方案：鏈接法（chaining）。也就是每個插槽存儲一個單項鏈表，所有碰撞的元素會依次形成鏈表中的一個結(jié)點，如果不存在，則鏈表指向為NULL。

而使用的函數(shù)h(k)成為哈希函數(shù)，它必須能夠很好的進行散列。最好能夠避免碰撞或者達(dá)到最小碰撞。一般為了更好的處理哈希的關(guān)鍵字，我們會將其轉(zhuǎn)換為自然數(shù)，然后通過除法散列、乘法散列或者全域散列來實現(xiàn)。數(shù)據(jù)庫一般使用除法散列，即當(dāng)有m個插槽時，我們對每個關(guān)鍵字k進行對m的取模：h(k) = k % m。

InnoDB存儲引擎中的哈希算法

InnoDB存儲引擎使用哈希算法來查找字典，沖突機制采用鏈表，哈希函數(shù)采用除法散列。對于緩沖池的哈希表，在緩存池中的每頁都有一個chain指針，指向相同哈希值的頁。對于除法散列，m的值為略大于2倍緩沖池頁數(shù)量的質(zhì)數(shù)。如當(dāng)前innodb_buffer_pool_size大小為10M，則共有640個16KB的頁，需要分配1280個插槽，而略大于的質(zhì)數(shù)為1399，因此會分配1399個槽的哈希表，用來哈希查詢緩沖池中的頁。

而對于將每個頁轉(zhuǎn)換為自然數(shù)，每個表空間都有一個space_id，用戶要查詢的是空間中某個連續(xù)的16KB的頁，即偏移量（offset），InnoDB將space_id左移20位，再加上space_id和offset，即K=space_id<<20+space_id+offset，然后使用除法散列到各個槽中。

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

自適應(yīng)哈希索引采用上面的哈希表實現(xiàn)，屬于數(shù)據(jù)庫內(nèi)部機制，DBA不能干預(yù)。它只對字典類型的查找非?？焖伲鴮Ψ秶檎业葏s無能為力，如：

select * from t where f='100'；

我們可以查看自適應(yīng)哈希索引的使用情況：

mysql> show engine innodb status\G;
*************************** 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

我們可以看到自適應(yīng)哈希的使用情況，可以通過最后一行的hash searches/non-hash searches來判斷使用哈希索引的效率。

我們可以使用innodb_adaptive_hash_index參數(shù)來禁用或啟用此特性，默認(rèn)開啟。

B+樹索引

B+樹索引是目前關(guān)系型數(shù)據(jù)庫系統(tǒng)中查找最為常用和有效的索引，其構(gòu)造類似于二叉樹，根據(jù)鍵值對快速找到數(shù)據(jù)。B+樹（balance+ tree）由B樹（banlance tree 平衡二叉樹）和索引順序訪問方法（ISAM: Index Sequence Access Method）演化而來，這幾個都是經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。而MyISAM引擎最初也是參考ISAM數(shù)據(jù)結(jié)構(gòu)設(shè)計的。

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

想要了解B+樹數(shù)據(jù)結(jié)構(gòu)，我們先了解一些基礎(chǔ)的知識。

二分查找法

又稱為折半查找法，指的是將數(shù)據(jù)順序排列，通過每次和中間值比較，跳躍式查找，每次縮減一半的范圍，快速找到目標(biāo)的算法。其算法復(fù)雜度為log2(n)，比順序查找要快上一些。

如圖所示，從有序列表中查找48，只需要3步：

詳細(xì)的算法可以參考二分查找算法。

二叉查找樹

二叉查找樹的定義是在一個二叉樹中，左子樹的值總是小于根鍵值，根鍵值總是小于右子樹的值。在我們查找時，每次都從根開始查找，根據(jù)比較的結(jié)果來判斷繼續(xù)查找左子樹還是右子樹。其查找的方法非常類似于二分查找法。

平衡二叉樹

二叉查找樹的定義非常寬泛，可以任意構(gòu)造，但是在極端情況下查詢的效率和順序查找一樣，如只有左子樹的二叉查找樹。

若想構(gòu)造一個性能最大的二叉查找樹，就需要該樹是平衡的，即平衡二叉樹（由于其發(fā)明者為G. M. Adelson-Velsky和Evgenii Landis，又被稱為AVL樹）。其定義為必須滿足任何節(jié)點的兩個子樹的高度最大差為1的二叉查找樹。平衡二叉樹相對結(jié)構(gòu)較優(yōu)，而最好的性能需要建立一個最優(yōu)二叉樹，但由于維護該樹代價高，因此一般平衡二叉樹即可。

平衡二叉樹查詢速度很快，但在樹發(fā)生變更時，需要通過一次或多次左旋和右旋來達(dá)到樹新的平衡。這里不發(fā)散講。

B+樹

了解了基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)后，我們來看下B+樹的實現(xiàn)，其定義十分復(fù)雜，簡單來說就是在B樹上增加規(guī)定：

1. 葉子結(jié)點存數(shù)據(jù)，非葉子結(jié)點存指針
2. 所有葉子結(jié)點從左到右用雙向鏈表記錄

目標(biāo)是為磁盤或其他直接存取輔助設(shè)備設(shè)計的一種平衡查找樹。在該樹中，所有的記錄都按鍵值的大小放在同一層的葉子節(jié)點上，各葉子節(jié)點之間有指針進行連接（非連續(xù)存儲），形成一個雙向鏈表。索引節(jié)點按照平衡樹的方式構(gòu)造，并存在指針指向具體的葉子節(jié)點，進行快速查找。

下面的B+ 樹為數(shù)據(jù)較少時，此時高度為2，每頁固定存放4條記錄，扇出固定為5（圖上灰色部分）。葉子節(jié)點存放多條數(shù)據(jù)，是為了降低樹的高度，進行快速查找。

當(dāng)我們插入28、70、953條數(shù)據(jù)后，B+ 樹由于數(shù)據(jù)滿了，需要進行頁的拆分。此時高度變?yōu)?/span>3，每頁依然是4條記錄，雙向鏈表未畫出但是依然是存在的，現(xiàn)在可以看出來是一個平衡二叉樹的雛形了。

InnoDB的B+樹索引

InnoDB的B+樹索引的特點是高扇出性，因此一般樹的高度為2~4層，這樣我們在查找一條記錄時只用I/O2~4次。當(dāng)前機械硬盤每秒至少100次I/O/s，因此查詢時間只需0.02~0.04s。

數(shù)據(jù)庫中的B+樹索引分為聚集索引（clustered index）和輔助索引（secondary index）。它們的區(qū)別是葉子節(jié)點存放的是否為一整行的完整數(shù)據(jù)。

聚集索引

聚集索引就是按照每張表的主鍵（唯一）構(gòu)造一棵B+樹，同時葉子節(jié)點存放整行的完整數(shù)據(jù)，因此將葉子節(jié)點稱為數(shù)據(jù)頁。由于定義了數(shù)據(jù)的邏輯順序，聚集索引也能快速的進行范圍類型的查詢。

聚集索引的葉子節(jié)點按照邏輯順序連續(xù)存儲，葉子節(jié)點內(nèi)部物理上連續(xù)存儲，作為最小單元，葉子節(jié)點間通過雙向指針連接，物理存儲上不連續(xù)，邏輯存儲上連續(xù)。

聚集索引能夠針對主鍵進行快速的排序查找和范圍查找，由于是雙向鏈表，因此在逆序查找時也非常快。

我們可以通過explain命令來分析MySQL數(shù)據(jù)庫的執(zhí)行計劃：

# 查看表的定義，可以看到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屬性排序并查找，可以看到?jīng)]有使用到任何索引，且需要filesort（文件排序），這里的rows為輸出行數(shù)的預(yù)估值
mysql> explain select * from dimensionsConf order by name limit 10\G;
*************************** 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的排序并查找，此時使用主鍵索引，在執(zhí)行計劃中沒有了filesort操作，這就是聚集索引帶來的優(yōu)化
mysql> explain select * from dimensionsConf order by id limit 10\G;
*************************** 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)

# 再查找根據(jù)主鍵id的范圍查找，此時直接根據(jù)葉子節(jié)點的上層節(jié)點就可以快速得到范圍，然后讀取數(shù)據(jù)
mysql> explain select * from dimensionsConf where id>10 and id<10000\G;
*************************** 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)

輔助索引

輔助索引又稱非聚集索引，其葉子節(jié)點不包含行記錄的全部數(shù)據(jù)，而是包含一個書簽（bookmark），該書簽指向?qū)?yīng)行數(shù)據(jù)的聚集索引，告訴InnoDB存儲引擎去哪里查找具體的行數(shù)據(jù)。輔助索引與聚集索引的關(guān)系就是結(jié)構(gòu)相似、獨立存在，但輔助索引查找非索引數(shù)據(jù)需要依賴于聚集索引來查找。

全文索引

我們通過B+樹索引可以進行前綴查找，如：

select * from blog where content like 'xxx%';

只要為content列添加了B+樹索引（聚集索引或輔助索引），就可快速查詢。但在更多情況下，我們在博客或搜索引擎中需要查詢的是某個單詞，而不是某個單詞開頭，如：

select * from blog where content like '%xxx%';

此時如果使用B+樹索引依然是全表掃描，而全文檢索（Full-Text Search）就是將整本書或文章內(nèi)任意內(nèi)容檢索出來的技術(shù)。

倒排索引

全文索引通常使用倒排索引（inverted index）來實現(xiàn)，倒排索引和B+樹索引都是一種索引結(jié)構(gòu)，它需要將分詞（word）存儲在一個輔助表（Auxiliary Table）中，為了提高全文檢索的并行性能，共有6張輔助表。輔助表中存儲了單詞和單詞在各行記錄中位置的映射關(guān)系。它分為兩種：

• inverted file index（倒排文件索引），表現(xiàn)為{單詞，單詞所在文檔ID}
• full inverted index（詳細(xì)倒排索引），表現(xiàn)為{單詞，(單詞所在文檔ID, 文檔中的位置)}

對于這樣的一個數(shù)據(jù)表：

倒排文件索引類型的輔助表存儲為：詳細(xì)倒排索引類型的輔助表存儲為，占用更多空間，也更好的定位數(shù)據(jù)，比提供更多的搜索特性：

全文檢索索引緩存

輔助表是存在與磁盤上的持久化的表，由于磁盤I/O比較慢，因此提供FTS Index Cache（全文檢索索引緩存）來提高性能。FTS Index Cache是一個紅黑樹結(jié)構(gòu)，根據(jù)（word, list）排序，在有數(shù)據(jù)插入時，索引先更新到緩存中，而后InnoDB存儲引擎會批量進行更新到輔助表中。

當(dāng)數(shù)據(jù)庫宕機時，尚未落盤的索引緩存數(shù)據(jù)會自動讀取并存儲，配置參數(shù)innodb_ft_cache_size控制緩存的大小，默認(rèn)為32M，提高該值，可以提高全文檢索的性能，但在故障時，需要更久的時間恢復(fù)。

在刪除數(shù)據(jù)時，InnoDB不會刪除索引數(shù)據(jù)，而是保存在DELETED輔助表中，因此一段時間后，索引會變得非常大，可以通過optimize table命令手動刪除無效索引記錄。如果需要刪除的內(nèi)容非常多，會影響應(yīng)用程序的可用性，參數(shù)innodb_ft_num_word_optimize控制每次刪除的分詞數(shù)量，默認(rèn)為2000，用戶可以調(diào)整該參數(shù)來控制刪除幅度。

全文檢索限制

全文檢索存在一個黑名單列表（stopword list），該列表中的詞不需要進行索引分詞，默認(rèn)共有36個，如the單詞。你可以自行調(diào)整：

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)

其他限制還有：

• 每張表只能有一個全文檢索索引
• 多列組合的全文檢索索引必須使用相同的字符集和字符序，不了解的可以參考MySQL亂碼的原因和設(shè)置UTF8數(shù)據(jù)格式
• 不支持沒有單詞界定符（delimiter）的語言，如中文、日語、韓語等

全文檢索

我們創(chuàng)建一個全文索引：

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），默認(rèn)方法，可省略：（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)

# 查看下執(zhí)行計劃，使用了全文索引排序
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)

我們也可以查看各行數(shù)據(jù)的相關(guān)性，是一個非負(fù)的浮點數(shù)，0代表沒有相關(guān)性：

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可選，如果出現(xiàn)，相關(guān)性更高
• @distance:查詢的多個單詞必須在指定范圍之內(nèi)
• >:出現(xiàn)該單詞時增加相關(guān)性
• <:出現(xiàn)該單詞時降低相關(guān)性
• ~:出現(xiàn)該單詞時相關(guān)性為負(fù)
• *:以該單詞開頭的單詞
• ":表示短語

# 代表必須有a baby短語，不能有man，可以有l(wèi)ik開頭的單詞，可以有panda，
select remark from dimensionsConf where match(remark) against('+"a baby" -man lik* panda' IN BOOLEAN MODE);

擴展查詢

當(dāng)查詢的關(guān)鍵字太短或不夠清晰時，需要用隱含知識來進行檢索，如database關(guān)聯(lián)的MySQL/DB2等。但這個我并沒太明白怎么使用，后續(xù)補充吧。

類似的使用是：

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

到此這篇關(guān)于MySQL InnoDB索引原理分析和算法解密的文章就介紹到這了,更多相關(guān)MySQL InnoDB索引原理和算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！