MySQL InnoDB 인덱스 원칙 및 알고리즘

MySQL을 자주 사용하고 인덱스도 사용하지만 인덱스의 원리와 고급 기능을 모르실 수도 있습니다. 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

🎜 <span style="max-width:90%">InnoDB</span>스토리지 색인🎜🎜 데이터베이스에 인덱스가 너무 많으면 애플리케이션 성능이 영향을 받을 수 있고, 인덱스가 너무 적으면 쿼리 성능이 영향을 받을 수 있습니다. 따라서 둘 사이의 균형점을 추구해야 합니다. 인덱스가 충분하면 쿼리 성능이 향상되지만 인덱스가 너무 많아 데이터 수정 및 기타 작업 시 너무 많은 부하가 발생하지 않습니다. 🎜🎜InnoDB는 3 공통 인덱스를 지원합니다. 🎜🎜● 해시 인덱스 🎜🎜● B+ 트리 인덱스 🎜🎜● 전체 텍스트 인덱스 🎜🎜us 다음으로 자세히 설명드릴 것은 B+ 트리 인덱스와 전체 텍스트 인덱스입니다. 🎜🎜해시 인덱스🎜🎜해시 인덱스를 배우기 전에 먼저 몇 가지 기본 지식인 해시 알고리즘을 이해해야 합니다. 해시 알고리즘은 O(1)의 시간 복잡도를 가지며 일반적으로 사용되는 알고리즘입니다. 인덱스뿐만 아니라 다양한 데이터베이스 애플리케이션에서도 사용됩니다. 🎜🎜해시 테이블🎜🎜해시 테이블(Hash Table)을 해시 테이블이라고도 하는데, 직접 주소 지정 테이블이 개선되었습니다. 🎜🎜
이 표에서 U는 전체 키워드 집합을 나타내고, K는 실제 키워드를 나타내며, 오른쪽의 배열(해시 테이블)은 직접 처리할 수 있는 키워드를 나타냅니다. 메모리의 연속 공간, 해시 테이블의 각 슬롯과 관련된 단방향 연결 목록에 저장된 실제 데이터의 실제 주소입니다. 🎜🎜오른쪽 배열이 직접 주소 지정 테이블을 사용하는 경우 각 키워드 K에 대해 중복 없이 h[K]가 있게 됩니다. 이로 인해 U 데이터 양이 발생하면 문제가 발생할 수 있습니다. 너무 큽니다. 컴퓨터의 사용 가능한 용량에 비해 약간 비실용적입니다. 그리고 U에 대한 K 설정의 비율이 너무 작으면 할당된 공간의 대부분이 낭비됩니다. 🎜🎜그래서 우리는 해시 테이블을 사용하여 h(k) 함수를 통해 매핑 관계를 결정하므로 이산 데이터가 배열의 슬롯을 사용하여 최대한 균등하게 분산될 수 있습니다. 문제가 될 것입니다. 여러 키워드가 동일한 슬롯에 매핑되는 경우 이러한 상황을 충돌 (충돌)이라고 하며 데이터베이스에서 가장 간단한 해결책이 채택됩니다: 연결 방법 (체인) 코드>. 즉, 각 슬롯은 단일 연결 리스트를 저장하고, 충돌하는 모든 요소는 차례로 연결 리스트의 노드를 형성합니다. 노드가 없으면 연결 리스트는 NULL을 가리킵니다. 🎜🎜h(k)를 사용한 함수는 해시 함수가 되는데, 해시가 잘 되어야 합니다. 충돌을 피하거나 충돌을 최소화하는 것이 가장 좋습니다. 일반적으로 해시된 키워드를 더 잘 처리하기 위해 이를 자연수로 변환한 다음 나누기 해싱, 곱셈 해싱 또는 글로벌 해싱을 통해 구현합니다. 데이터베이스는 일반적으로 분할 해싱을 사용합니다. 즉, 슬롯이 m개인 경우 각 키 k에 대해 모듈로 m을 사용합니다. h(k) = k % m. 🎜🎜<span style="max-width:90%">InnoDB</span>스토리지 엔진의 해시 알고리즘 span>🎜🎜InnoDB스토리지 엔진은 해시 알고리즘을 사용하여 사전을 찾고, 충돌 메커니즘은 연결 목록을 사용하고, 해시 함수는 분할 해싱을 사용합니다. 버퍼 풀 해시 테이블의 경우 버퍼 풀의 각 페이지에는 동일한 해시 값이 있는 페이지를 가리키는 체인 포인터가 있습니다. 분할 해시의 경우 m 값은 버퍼 풀 페이지 수의 2배보다 약간 큰 소수입니다. 현재 innodb_buffer_pool_size 크기가 10M인 경우 총 640 16KB 페이지가 있고 1280 슬롯이 필요합니다. 약간 더 큰 소수는 1399이므로 1399 슬롯이 있는 해시 테이블이 쿼리 버퍼 풀의 페이지를 해시하기 위해 할당됩니다. 🎜🎜각 페이지를 자연수로 변환하기 위해 각 테이블스페이스에는 space_id가 있습니다. 사용자가 쿼리하려는 것은 해당 공간에서 연속적인 16KB 페이지입니다. 오프셋 (offset), InnoDB는 space_id를 20 비트와 space_id 및 <code>offset(예: K=space_id)은 나누기를 사용하여 각 슬롯에 해시됩니다. 🎜🎜<span style="font-size: 18px;"><strong>적응형 해시 인덱스</strong></span>🎜🎜적응형 해시 인덱스는 위의 해시 테이블을 사용하여 구현되며 데이터베이스의 내부 메커니즘입니다. , <code>DBA가 개입할 수 없습니다. 사전 유형 조회의 경우 매우 빠르지만 다음과 같은 범위 조회 등에 대해서는 아무 작업도 수행할 수 없습니다. 🎜

# 查看表的定义，可以看到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🎜 적응형 해시 인덱스의 사용법을 볼 수 있습니다. 🎜<pre class="brush:php;toolbar:false">select * from blog where content like 'xxx%';

🎜 적응형 해시의 사용법을 볼 수 있습니다. 해시 인덱스 사용의 효율성은 마지막 줄의 해시 검색/비해시 검색으로 판단할 수 있습니다. 🎜

기본적으로 활성화되어 있는 이 기능을 innodb_adaptive_hash_index 매개변수를 사용하여 비활성화하거나 활성화할 수 있습니다. 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="max-width:90%">B+</span> 树

了解了基础的数据结构后，我们来看下B+ 树的实现，其定义十分复杂，简单来说就是在B树上增加规定：

1、叶子结点存数据，非叶子结点存指针

2、所有叶子结点从左到右用双向链表记录

目标是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在该树中，所有的记录都按键值的大小放在同一层的叶子节点上，各叶子节点之间有指针进行连接（非连续存储），形成一个双向链表。索引节点按照平衡树的方式构造，并存在指针指向具体的叶子节点，进行快速查找。

下面的B+ 树为数据较少时，此时高度为2，每页固定存放4条记录，扇出固定为5（图上灰色部分）。叶子节点存放多条数据，是为了降低树的高度，进行快速查找。

当我们插入28、70、95 3条数据后，B+ 树由于数据满了，需要进行页的拆分。此时高度变为3，每页依然是4条记录，双向链表未画出但是依然是存在的，现在可以看出来是一个平衡二叉树的雏形了。

<span style="max-width:90%">InnoDB</span>的<span style="font-size: 18px;">B+</span><span style="font-size: 20px;">B+ </span>트리 인덱스

🎜🎜B+ 트리 인덱스는 현재 관계형 데이터베이스 시스템에서 검색에 가장 일반적으로 사용되고 효과적인 인덱스로, 그 구조는 이진 트리와 유사하며 키-값 쌍을 기반으로 데이터를 빠르게 찾을 수 있습니다. B+ 트리 (balance+ tree)는 B트리 (밴런스 트리 균형 이진 트리)와 인덱스 순차 접근 방식으로 구성됩니다. (ISAM: Index Sequence Access Method)가 발전하여 모두 고전적인 데이터 구조입니다. MyISAM 엔진은 원래 ISAM 데이터 구조를 참조하여 설계되었습니다. 🎜🎜🎜기본 데이터 구조 🎜🎜🎜🎜 B+ 트리 데이터 구조를 이해하려면 먼저 몇 가지 기본 지식을 이해해야 합니다. 🎜🎜이진 검색 방법 🎜🎜🎜은 반 검색 방법이라고도 하는데, 데이터를 순서대로 정렬하고 매번 중간 값과 비교하여 건너뛰기 검색을 수행하고 범위를 1만큼 줄이는 알고리즘을 말합니다. 매번 절반씩 빠르게 목표를 찾습니다. 알고리즘 복잡도는 log2(n)로 순차 검색보다 빠릅니다. 🎜🎜그림에 표시된 것처럼 주문 목록에서 48을 검색하려면 3 단계만 필요합니다.
🎜🎜🎜🎜자세한 알고리즘은 이진 검색 알고리즘. 🎜🎜이진 검색 트리🎜🎜🎜이진 검색 트리의 정의는 이진 트리에서 왼쪽 하위 트리의 값은 항상 루트 키 값보다 작고, 루트 키 값은 항상 하위 트리의 값보다 작다는 것입니다. 오른쪽 하위 트리의 값 검색을 할 때마다 루트부터 검색을 시작하고, 비교 결과를 토대로 왼쪽 하위 트리를 계속 검색할지 오른쪽 하위 트리를 계속 검색할지 판단합니다. 검색 방법은 이진 검색 방법과 매우 유사합니다.
🎜🎜🎜🎜균형 이진 트리🎜🎜🎜 이진 검색 트리의 정의는 매우 광범위하고 임의로 구성할 수 있지만 극단적인 경우 쿼리 효율성은 이진 검색 트리와 같은 순차 검색과 동일합니다. 왼쪽 하위 트리만.
🎜🎜🎜🎜최대 성능의 이진 검색 트리를 구성하려면 균형이 잡힌 트리, 즉 균형 이진 트리가 필요합니다(발명자가 G. M. Adelson-Velsky 및 Evgenii Landis, AVL 트리라고도 함). 모든 노드의 두 하위 트리 높이의 최대 차이를 1로 만족해야 하는 이진 검색 트리로 정의됩니다. 균형 이진 트리는 상대적으로 더 나은 구조를 가지며 최상의 성능을 위해서는 최적의 이진 트리 구축이 필요합니다. 그러나 트리 유지 비용이 높기 때문에 일반적으로 균형 이진 트리로 충분합니다. 🎜🎜균형 이진 트리 쿼리는 매우 빠르지만, 트리가 변경되면 트리에서 새로운 균형을 이루기 위해 하나 이상의 왼쪽 및 오른쪽 회전이 필요합니다. 여기서는 그것에 대해 이야기하지 않겠습니다. 🎜🎜🎜B+🎜🎜 tree🎜🎜🎜🎜기본 데이터 구조를 이해한 후 B+ 트리의 구현을 살펴보겠습니다. 매우 복잡합니다. B 트리에 규정을 추가하는 것입니다. 🎜🎜1. 리프 노드는 데이터를 저장하고, 리프 노드가 아닌 노드는 포인터를 저장합니다. 🎜🎜목표는 디스크 또는 기타 직접 액세스 보조 장치용으로 설계된 균형 잡힌 검색 트리입니다. 이 트리에서는 모든 레코드가 키 값의 크기에 따라 동일한 레이어의 리프 노드에 배치되어 연결(비연속 저장)되는 리프 노드 사이에 포인터가 있어 이중 연결 목록을 형성합니다. 인덱스 노드는 균형 트리 방식에 따라 구성되며, 빠른 검색을 위해 특정 리프 노드를 가리키는 포인터가 있습니다. 🎜🎜아래 B+ 트리에 데이터가 적을 때 높이는 2이고 각 페이지는 고정 팬아웃을 사용하여 4 레코드를 저장합니다. 5(사진의 회색 부분)입니다. 리프 노드는 트리 높이를 줄이고 빠른 검색을 수행하기 위해 여러 데이터 조각을 저장합니다.
🎜🎜🎜🎜 28, 70, 95 3개의 데이터를 삽입하면 데이터가 가득 차서 B+ 트리를 분할해야 합니다. . 이때 높이는 3이 되고, 각 페이지에는 여전히 4개의 레코드가 남아 있습니다. 이중 연결 목록은 그려지지 않았지만 여전히 존재하는 것을 알 수 있습니다. 균형 잡힌 이진 트리의 프로토타입.
🎜🎜🎜🎜🎜InnoDB🎜🎜's🎜🎜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 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%20%EC%9D%B8%EB%8D%B1%EC%8A%A4%20%EC%9B%90%EC%B9%99%20%EB%B0%8F%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98" 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!