MySQL InnoDB索引原理與演算法

也許你常用MySQL，也會常用索引，但對索引的原理和進階功能卻不知道，我們在這裡一起學習下。

<span style="font-size: 20px;">InnoDB</span>#儲存索引

在資料庫中，如果索引太多，應用程式的效能可能會受到影響；如果索引太少，又會對查詢效能產生影響。所以，我們要追求兩者的一個平衡點，足夠多的索引帶來查詢效能提高，又不因為索引過多導致修改資料等操作時負載過高。

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。

<span style="font-size: 18px;">InnoDB</span>儲存引擎中的雜湊演算法

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 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

我們可以看到自適應哈希的使用情況，可以透過最後一行的hash searches/non-hash searches來判斷使用雜湊索引的效率。

我們可以使用innodb_adaptive_hash_index參數來停用或啟用此特性，預設為開啟。

<span style="font-size: 20px;">B </span>樹索引

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的二元查找樹。平衡二元樹相對結構較優，而最好的性能需要建立一個最優二叉樹，但由於維護該樹代價高，因此一般平衡二叉樹即可。

平衡二元樹查詢速度很快，但在樹發生變更時，需要透過一次或多次左旋和右旋來達到樹新的平衡。這裡不發散講。

<span style="font-size: 18px;">B </span> 樹

#了解了基礎的資料結構後，我們來看下B 樹的實現，其定義十分複雜，簡單來說就是在B樹上增加規定：

1、葉子結點存數據，非葉子結點存指針

2、所有葉子結點從左到右用雙向鍊錶記錄

#目標是為磁碟或其他直接存取輔助設備設計的一種平衡查找樹。在該樹中，所有的記錄都按鍵值的大小放在同一層的葉子節點上，各葉子節點之間有指針進行連接（非連續存儲），形成一個雙向鍊錶。索引節點按照平衡樹的方式構造，並存在指標指向特定的葉子節點，進行快速查找。

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

當我們插入28、70、95 3條資料後，B 樹由於資料滿了，需要進行頁的拆分。此時高度變為3，每頁依然是4筆記錄，雙向鍊錶未畫出但是依然是存在的，現在可以看出來是一個平衡二元樹的雛形了。

<span style="font-size: 18px;">InnoDB</span><span style="font-size: 18px;">B </span> 樹索引

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 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的排序并查找，此时使用主键索引，在执行计划中没有了filesort操作，这就是聚集索引带来的优化
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)

# 再查找根据主键id的范围查找，此时直接根据叶子节点的上层节点就可以快速得到范围，然后读取数据
mysql> explain select * from dimensionsConf where id>10 and id<p><strong>辅助索引</strong></p><p>辅助索引又称非聚集索引，其叶子节点不包含行记录的全部数据，而是包含一个书签<code>（bookmark）</code>，该书签指向对应行数据的聚集索引，告诉<code>InnoDB</code>存储引擎去哪里查找具体的行数据。辅助索引与聚集索引的关系就是结构相似、独立存在，但辅助索引查找非索引数据需要依赖于聚集索引来查找。<br></p><p><img src="https://img.php.cn/upload/image/639/959/687/157484689554534MySQL%20InnoDB%E7%B4%A2%E5%BC%95%E5%8E%9F%E7%90%86%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95" title="157484689554534MySQL InnoDB索引原理與演算法" alt="MySQL InnoDB索引原理與演算法"></p><p><span   style="max-width:90%"><strong>全文索引</strong></span></p><p>我们通过<code>B+</code> 树索引可以进行前缀查找，如：</p><pre class="brush:php;toolbar:false">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)

其他限制还有：

　●　每张表只能有一个全文检索索引

　●　多列组合的全文检索索引必须使用相同的字符集和字符序，不了解的可以参考MySQL乱码的原因和设置UTF8数据格式

　●　不支持没有单词界定符（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);

推荐学习：MySQL教程

以上是MySQL InnoDB索引原理與演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！