Principes et algorithmes de l'index MySQL InnoDB

Peut-être que vous utilisez souvent MySQL et des index, mais vous ne connaissez pas les principes et les fonctions avancées des index. Apprenons ensemble ici.

<span style="font-size: 20px;">InnoDB</span>Index de stockage

Dans la base de données, s'il y a trop d'index, le les performances de l'application peuvent en souffrir ; s'il y a trop peu d'index, les performances des requêtes seront affectées. Par conséquent, nous devons rechercher un point d'équilibre entre les deux. Un nombre suffisant d'index peut améliorer les performances des requêtes, mais ne provoque pas trop de charge lors de la modification des données et d'autres opérations en raison d'un trop grand nombre d'index.

InnoDBPrend en charge 3 les index communs :

● Index de hachage

● B+ Index d'arbre

● Index de texte intégral

Ce que nous expliquerons en détail ensuite est B+ l'index arborescent et l'index de texte intégral.

Indice de hachage

Avant d'apprendre l'index de hachage, nous comprenons d'abord quelques connaissances de base : l'algorithme de hachage. L'algorithme de hachage est un algorithme couramment utilisé avec une complexité temporelle de O(1). Il n'est pas seulement utilisé dans les index, mais également dans diverses applications de bases de données.

Table de hachage

La table de hachage （Hash Table） est également appelée table de hachage, qui est améliorée par rapport à la table d'adressage direct.

Dans ce tableau, U représente l'ensemble complet de mots-clés, K représente les mots-clés réels et le tableau (table de hachage) à droite représente qu'il peut être directement adressée en mémoire. L'espace continu de la table de hachage stocke l'adresse réelle des données réelles dans la liste chaînée unidirectionnelle associée à chaque emplacement de la table de hachage.

Si le tableau de droite utilise directement la table d'adressage direct, alors il y en aura un h[K] pour chaque mot-clé K sans duplication. Cela posera quelques problèmes si la quantité de données U est trop importante. puis pour l'ordinateur Un peu peu pratique en terme de capacité utilisable. Et si la proportion de collecte K par rapport à U est trop faible, la majeure partie de l'espace alloué sera gaspillée.

Nous utilisons donc une table de hachage, et nous utilisons certaines fonctions h(k) pour déterminer la relation de mappage, afin que les données discrètes puissent être distribuées aussi uniformément que possible en utilisant les emplacements du tableau, mais il y aura un problème, plusieurs mots-clés sont mappés sur le même emplacement. Cette situation est appelée une collision （collision）, et la solution la plus simple est utilisée dans la base de données : la méthode des liens （chaining）. Autrement dit, chaque emplacement stocke une liste chaînée, et tous les éléments en collision formeront à leur tour un nœud dans la liste chaînée. Si elle n'existe pas, la liste chaînée pointe vers NULL.

et la fonction utilisée h(k) devient la fonction de hachage, qui doit pouvoir bien hacher. Il est préférable d'éviter les collisions ou de minimiser les collisions. Généralement, afin de mieux gérer les mots-clés hachés, nous les convertirons en nombres naturels, puis les implémenterons via un hachage de division, un hachage de multiplication ou un hachage global. Les bases de données utilisent généralement le hachage par division, c'est-à-dire que lorsqu'il y a m slots, on prend modulo m pour chaque clé k : h(k) = k % m.

<code><span style="font-size: 18px;">InnoDB</span>InnoDBAlgorithme de hachage dans le moteur de stockage

InnoDBchainmoteur de stockage Un hachage L'algorithme est utilisé pour rechercher le dictionnaire, une liste chaînée est utilisée comme mécanisme de collision et un hachage de division est utilisé comme fonction de hachage. Pour la table de hachage du pool tampon, chaque page du pool tampon possède un pointeur m pointant vers la page avec la même valeur de hachage. Pour un hachage de division, la valeur de 2 est un nombre premier légèrement supérieur à innodb_buffer_pool_size fois le nombre de pages du pool de mémoire tampon. Si la taille actuelle de 10M est 640个16KB, il y a 1280 pages et 1399 emplacements doivent être alloués. Le nombre premier légèrement plus grand est 1399, donc une table de hachage de

emplacements sera alloué , utilisé pour hacher les pages dans le pool de tampons de requête.

space_idQuant à la conversion de chaque page en nombre naturel, chaque espace table a un 16KB Ce que l'utilisateur souhaite interroger est une page d'un （offset） continu dans l'espace, c'est-à-dire le décalage <.>, InnoDB décale space_id gauche de 20 bits, plus space_id et offset, c'est-à-dire K=space_id, puis utilise la division pour hacher dans chaque emplacement.

Index de hachage adaptatif

L'index de hachage adaptatif est implémenté à l'aide de la table de hachage ci-dessus, qui est un mécanisme interne de la base de données, DBA Impossible d'intervenir. Il n'est très rapide que pour les recherches de type dictionnaire, mais ne peut rien faire pour les recherches de plage, etc., telles que :

select * from t where f='100'；

Nous pouvons vérifier l'utilisation de l'index de hachage adaptatif :

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

Nous pouvons voir L'utilisation du hachage adaptatif peut être jugée par le hash searches/non-hash searches dans la dernière ligne pour juger de l'efficacité de l'utilisation de l'index de hachage.

Nous pouvons utiliser le paramètre innodb_adaptive_hash_index pour désactiver ou activer cette fonctionnalité, qui est activée par défaut.

<span style="font-size: 20px;">B+ </span>Index arborescent

B+ L'index arborescent est actuellement l'index le plus couramment utilisé et le plus efficace pour la recherche dans les systèmes de bases de données relationnelles. La construction est similaire à un arbre binaire et les données peuvent être rapidement trouvées sur la base de paires clé-valeur. B+ Tree（balance+ tree） a évolué à partir de BTree（banlance tree 平衡二叉树） et de la méthode d'accès séquentiel d'index （ISAM: Index Sequence Access Method）, qui sont toutes des structures de données classiques. Le moteur MyISAM a été initialement conçu en référence à la structure de données ISAM.

Structure de données de base

Pour comprendre la structure de données arborescente B+, nous comprenons d'abord quelques connaissances de base.

Méthode de recherche binaire

Également connue sous le nom de méthode de demi-recherche, elle consiste à organiser les données dans l'ordre, à comparer à chaque fois avec la valeur intermédiaire et à effectuer une sauter la recherche. Un algorithme qui réduit la portée de moitié et trouve rapidement la cible. Sa complexité d'algorithme est log2(n), ce qui est plus rapide que la recherche séquentielle.

Comme le montre la figure, la recherche de 48 à partir d'une liste ordonnée ne nécessite que 3 étapes :

L'algorithme détaillé peut be Reportez-vous à Algorithme de recherche binaire.

Arbre de recherche binaire

La définition d'un arbre de recherche binaire est que dans un arbre binaire, la valeur du sous-arbre gauche est toujours inférieure à la valeur de la clé racine, et la valeur de la clé racine est toujours inférieure à la valeur du sous-arbre droit. Lorsque nous effectuons une recherche, nous commençons la recherche à partir de la racine à chaque fois et jugeons s'il faut continuer la recherche dans le sous-arbre de gauche ou dans le sous-arbre de droite en fonction du résultat de la comparaison. La méthode de recherche est très similaire à la méthode de recherche binaire.

Arbre binaire équilibré

La définition d'un arbre de recherche binaire est très large et peut être construite arbitrairement, mais dans les cas extrêmes, l'efficacité de la requête est la même que celle d'une recherche séquentielle, telle qu'un arbre de recherche binaire avec uniquement un sous-arbre gauche.

Si vous souhaitez construire un arbre de recherche binaire avec des performances maximales, vous avez besoin que l'arbre soit équilibré, c'est-à-dire un arbre binaire équilibré (car son inventeur est G. M. Adelson-Velsky et Evgenii Landis, également appelés AVL arbres). Il est défini comme un arbre de recherche binaire qui doit satisfaire la différence de hauteur maximale des deux sous-arbres de n'importe quel nœud à 1. L'arbre binaire équilibré a une structure relativement meilleure, et les meilleures performances nécessitent l'établissement d'un arbre binaire optimal. Cependant, en raison du coût élevé de maintenance de l'arbre, un arbre binaire équilibré est généralement suffisant.

La requête d'arbre binaire équilibré est rapide, mais lorsque l'arbre change, une ou plusieurs rotations à gauche et à droite sont nécessaires pour atteindre un nouvel équilibre dans l'arbre. Je n’en parlerai pas ici.

<code><span style="font-size: 18px;">B+</span>B+ Arbre

B+Après avoir compris la structure de base des données, jetons un coup d'œil La définition de l'implémentation de l'arbre B est très compliquée. En termes simples, il s'agit d'ajouter des réglementations à l'arbre

 :

1.

2. Tous les nœuds feuilles sont enregistrés dans une liste doublement chaînée de gauche à droite

L'objectif est un arbre de recherche équilibré conçu pour les disques ou autres périphériques auxiliaires à accès direct. Dans cet arbre, tous les enregistrements sont placés sur les nœuds feuilles d'une même couche en fonction de la taille de la valeur clé. Il y a des pointeurs entre les nœuds feuilles à connecter (stockage non continu), formant une liste doublement chaînée. Le nœud d'index est construit à la manière d'un arbre équilibré et des pointeurs pointent vers des nœuds feuilles spécifiques pour une recherche rapide. Lorsque l'

arbre ci-dessous B+2 a moins de données, la hauteur est 4, chaque page est fixée pour stocker 5 enregistrements, et la diffusion est fixée à
(la partie grise sur la photo). Les nœuds feuilles stockent plusieurs éléments de données afin de réduire la hauteur de l'arborescence et d'effectuer des recherches rapides.

28、70、95Lorsque nous insérons 3 B+ éléments de données, l'arborescence 3 doit être divisée en pages car les données sont pleines. A ce moment, la hauteur passe à 4, et chaque page contient toujours
enregistrements. La liste doublement chaînée n'est pas dessinée mais existe toujours. On peut maintenant voir qu'il s'agit du prototype d'un arbre binaire équilibré.

<code><span style="font-size: 18px;">InnoDB</span><code><span style="font-size: 18px;">InnoDB</span><code><span style="font-size: 18px;">B+</span>B+

Index des arbres

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/157484689554534Principes%20et%20algorithmes%20de%20lindex%20MySQL%20InnoDB" title="157484689554534Principes et algorithmes de lindex MySQL InnoDB" alt="Principes et algorithmes de lindex 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教程

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!