Prinzipien und Algorithmen des MySQL InnoDB-Index

Vielleicht verwenden Sie häufig MySQL und Indizes, kennen aber die Prinzipien und erweiterten Funktionen von Indizes nicht. Lassen Sie uns hier gemeinsam lernen.

<span style="font-size: 20px;">InnoDB</span>Speicherindex

Wenn in der Datenbank zu viele Indizes vorhanden sind, wird der Die Leistung der Anwendung kann beeinträchtigt werden. Wenn zu wenige Indizes vorhanden sind, wird die Abfrageleistung beeinträchtigt. Daher müssen wir einen Gleichgewichtspunkt zwischen beiden anstreben, um die Abfrageleistung zu verbessern, aber aufgrund zu vieler Indizes nicht zu viel Last beim Ändern von Daten und anderen Vorgängen verursachen.

InnoDBUnterstützt 3 gängige Indizes:

●Hash-Index

●B+ Baumindex

●Volltextindex

Was wir als nächstes im Detail erklären werden, ist B+ Baumindex und Volltextindex.

Hash-Index

Bevor wir den Hash-Index lernen, verstehen wir zunächst einige Grundkenntnisse: Hash-Algorithmus. Der Hash-Algorithmus ist ein häufig verwendeter Algorithmus mit einer Zeitkomplexität von O(1). Es wird nicht nur in Indizes verwendet, sondern auch in verschiedenen Datenbankanwendungen.

Hash-Tabelle

Hash-Tabelle （Hash Table） wird auch Hash-Tabelle genannt und ist eine Verbesserung gegenüber der Direktadressierungstabelle.

In dieser Tabelle stellt U den vollständigen Satz von Schlüsselwörtern dar, K stellt die tatsächlichen Schlüsselwörter dar und das Array (Hash-Tabelle) auf der rechten Seite stellt dar, dass es direkt sein kann Der kontinuierliche Speicherplatz der Hash-Tabelle speichert die tatsächliche Adresse der tatsächlichen Daten in der unidirektional verknüpften Liste, die jedem Slot in der Hash-Tabelle zugeordnet ist.

Wenn das Array auf der rechten Seite direkt die direkte Adressierungstabelle verwendet, gibt es für jedes Schlüsselwort K eins ohne Duplizierung. Dies führt zu einigen Problemen. dann für den Computer Von der nutzbaren Kapazität her etwas unpraktisch. Und wenn das Verhältnis von Sammlung h[K] zu K zu klein ist, wird der größte Teil des zugewiesenen Speicherplatzes verschwendet. U

Also verwenden wir eine Hash-Tabelle und einige Funktionen

, um die Zuordnungsbeziehung zu bestimmen, damit die diskreten Daten mithilfe der Slots im Array so gleichmäßig wie möglich verteilt werden können, aber das wird so sein Ein Problem besteht darin, dass mehrere Schlüsselwörter demselben Slot zugeordnet sind. Diese Situation wird als Kollision h(k) bezeichnet und die einfachste Lösung wird in der Datenbank verwendet: die Link-Methode （collision）. Das heißt, jeder Slot speichert eine einfach verknüpfte Liste und alle kollidierenden Elemente bilden nacheinander einen Knoten in der verknüpften Liste. Wenn dieser nicht vorhanden ist, zeigt die verknüpfte Liste auf （chaining）. NULL

und die verwendete Funktion

wird zur Hash-Funktion, die gut hashen kann. Es ist am besten, Kollisionen zu vermeiden oder zu minimieren. Um gehashte Schlüsselwörter besser verarbeiten zu können, konvertieren wir sie im Allgemeinen in natürliche Zahlen und implementieren sie dann durch Divisions-Hashing, Multiplikations-Hashing oder globales Hashing. Datenbanken verwenden im Allgemeinen Divisions-Hashing, das heißt, wenn es m Slots gibt, nehmen wir Modulo m für jeden Schlüssel k: h(k). h(k) = k % m

<strong>InnoDB<code><span style="font-size: 18px;">InnoDB</span>Hash-Algorithmus in der Speicher-Engine

InnoDBSpeicher-Engine Ein Hash Der Algorithmus wird zum Nachschlagen des Wörterbuchs verwendet, der Kollisionsmechanismus verwendet eine verknüpfte Liste und die Hash-Funktion verwendet Divisions-Hashing. Für die Pufferpool-Hash-Tabelle verfügt jede Seite im Pufferpool über einen chain-Zeiger, der auf die Seite mit demselben Hash-Wert zeigt. Für einen Divisions-Hash ist der Wert von m eine Primzahl, die etwas größer als das 2-fache der Anzahl der Pufferpoolseiten ist. Wenn die aktuelle Größe von innodb_buffer_pool_size 10M ist, müssen 640个16KB Seiten und 1280 Slots zugewiesen werden. Die etwas größere Primzahl ist 1399, sodass eine Hash-Tabelle mit 1399 Slots erstellt wird zugewiesen, wird zum Hashen von Seiten im Abfragepufferpool verwendet.

Was die Konvertierung jeder Seite in eine natürliche Zahl betrifft, so verfügt jeder Tabellenbereich über ein space_id. Was der Benutzer abfragen möchte, ist eine Seite mit einem fortlaufenden 16KB im Bereich, also dem Offset （offset）, InnoDB verschiebt space_id um 20 Bits nach links, plus space_id und offset, also K=space_id, und verwendet dann Division, um in jeden Slot zu hashen.

Adaptiver Hash-Index

Der adaptive Hash-Index wird mithilfe der obigen Hash-Tabelle implementiert, die ein interner Mechanismus der Datenbank ist, DBA Kann nicht eingreifen. Es ist nur für Wörterbuchtyp-Suchen sehr schnell, kann aber nichts für Bereichssuchen usw. tun, wie zum Beispiel:

select * from t where f='100'；

Wir können die Verwendung des adaptiven Hash-Index überprüfen:

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

Das können wir siehe Die Verwendung von adaptivem Hashing kann anhand des hash searches/non-hash searches in der letzten Zeile beurteilt werden, um die Effizienz der Verwendung des Hash-Index zu beurteilen.

Wir können den Parameter innodb_adaptive_hash_index verwenden, um diese Funktion zu deaktivieren oder zu aktivieren, die standardmäßig aktiviert ist.

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

B+ Der Baumindex ist derzeit der am häufigsten verwendete und effektivste Index für die Suche in relationalen Datenbanksystemen. Der Aufbau ähnelt einem Binärbaum und Daten können anhand von Schlüssel-Wert-Paaren schnell gefunden werden. B+ Tree（balance+ tree） hat sich aus BTree（banlance tree 平衡二叉树） und der Index-Sequenzzugriffsmethode （ISAM: Index Sequence Access Method） entwickelt, die allesamt klassische Datenstrukturen sind. Die MyISAM-Engine wurde ursprünglich unter Bezugnahme auf die ISAM-Datenstruktur entwickelt.

Grundlegende Datenstruktur

Um die B+ Baumdatenstruktur zu verstehen, verstehen wir zunächst einige Grundkenntnisse.

Binäre Suchmethode

Auch als halbierte Suchmethode bekannt, bezieht sie sich auf das Anordnen der Daten in der richtigen Reihenfolge, den Vergleich jedes Mal mit dem Zwischenwert und das Durchführen eines Überspringens Suche Ein Algorithmus, der die Reichweite um die Hälfte reduziert und das Ziel schnell findet. Die Komplexität des Algorithmus beträgt log2(n), was schneller ist als die sequentielle Suche.

Wie in der Abbildung gezeigt, erfordert die Suche nach 48 aus einer geordneten Liste nur 3 Schritte:

Der detaillierte Algorithmus kann Siehe Binärer Suchalgorithmus.

Binärer Suchbaum

Die Definition eines binären Suchbaums ist, dass in einem Binärbaum der Wert des linken Teilbaums immer kleiner als der Wurzelschlüsselwert ist. und der Wurzelschlüsselwert ist immer kleiner als der Wert des rechten Teilbaums. Wenn wir suchen, beginnen wir jedes Mal mit der Suche von der Wurzel aus und entscheiden anhand des Vergleichsergebnisses, ob die Suche im linken Teilbaum oder im rechten Teilbaum fortgesetzt werden soll. Die Suchmethode ist der binären Suchmethode sehr ähnlich.

Balanced Binary Tree

Die Definition eines binären Suchbaums ist sehr weit gefasst und kann beliebig konstruiert werden, aber In extremen Fällen ist die Abfrageeffizienz dieselbe wie bei der sequentiellen Suche, beispielsweise bei einem binären Suchbaum mit nur einem linken Teilbaum.

Wenn Sie einen binären Suchbaum mit maximaler Leistung erstellen möchten, muss der Baum ausgeglichen sein, dh ein ausgeglichener Binärbaum (da sein Erfinder ist G. M. Adelson-Velsky und Evgenii Landis, auch bekannt als AVL Bäume). Es ist als binärer Suchbaum definiert, der den maximalen Höhenunterschied der beiden Teilbäume jedes Knotens zu 1 erfüllen muss. Der ausgeglichene Binärbaum hat eine relativ bessere Struktur und die beste Leistung erfordert die Einrichtung eines optimalen Binärbaums. Aufgrund der hohen Kosten für die Pflege des Baums ist jedoch im Allgemeinen ein ausgeglichener Binärbaum ausreichend.

Die Abfrage eines ausgewogenen Binärbaums ist sehr schnell, aber wenn sich der Baum ändert, sind eine oder mehrere Links- und Rechtsdrehungen erforderlich, um ein neues Gleichgewicht des Baums zu erreichen. Ich werde hier nicht darüber sprechen.

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

B+Nachdem wir die grundlegende Datenstruktur verstanden haben, werfen wir einen Blick darauf Die Definition der Implementierung des B-Baums ist sehr kompliziert. Sie besteht darin, Vorschriften zum

-Baum hinzuzufügen:

1

2. Alle Blattknoten werden in einer doppelt verknüpften Liste von links nach rechts aufgezeichnet

Das Ziel ist ein ausgewogener Suchbaum, der für Festplatten oder andere Hilfsgeräte mit Direktzugriff konzipiert ist. In diesem Baum werden alle Datensätze entsprechend der Größe des Schlüsselwerts auf den Blattknoten derselben Ebene platziert. Es gibt Zeiger zwischen den Blattknoten, die verbunden werden müssen (nicht kontinuierliche Speicherung), wodurch eine doppelt verknüpfte Liste entsteht. Der Indexknoten ist wie ein ausgeglichener Baum aufgebaut und es gibt Zeiger, die auf bestimmte Blattknoten verweisen, um eine schnelle Suche zu ermöglichen. Wenn der

-Baum unter B+2 weniger Daten enthält, beträgt die Höhe 4, jede Seite ist auf die Speicherung von 5-Datensätzen festgelegt und der Fan-Out ist auf
(der graue Teil) festgelegt im Bild). Blattknoten speichern mehrere Daten, um die Höhe des Baums zu reduzieren und schnelle Suchvorgänge durchzuführen.

28、70、95Wenn wir 3 B+ Datenelemente einfügen, muss der 3-Baum in Seiten aufgeteilt werden, da die Daten voll sind. Zu diesem Zeitpunkt ändert sich die Höhe auf 4 und jede Seite enthält noch
-Datensätze. Die doppelt verknüpfte Liste wird nicht gezeichnet, ist aber weiterhin vorhanden. Es ist ersichtlich, dass es sich um den Prototyp eines ausgeglichenen Binärbaums handelt.

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

Baumindex

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/157484689554534Prinzipien%20und%20Algorithmen%20des%20MySQL%20InnoDB-Index" title="157484689554534Prinzipien und Algorithmen des MySQL InnoDB-Index" alt="Prinzipien und Algorithmen des MySQL InnoDB-Index"></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教程

Das obige ist der detaillierte Inhalt vonPrinzipien und Algorithmen des MySQL InnoDB-Index. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!