MySQL InnoDB インデックスの原則とアルゴリズム-mysql チュートリアル-php.cn

MySQL をよく使うし、インデックスもよく使うけど、インデックスの原理や高度な機能を知らないという方もいると思いますので、ここで一緒に学びましょう。

MySQL InnoDB インデックスの原則とアルゴリズム

#InnoDBストレージインデックスデータベースでは、インデックスが多すぎるとアプリケーションのパフォーマンスに影響する可能性があり、インデックスが少なすぎるとクエリのパフォーマンスに影響する可能性があります。インデックスが多すぎるとクエリのパフォーマンスが向上しますが、インデックスが多すぎるとデータ変更やその他の操作で過剰な負荷がかかるため、両者のバランスポイントを追求する必要があります。

InnoDB

3 共通インデックスをサポート: #●ハッシュインデックス

ツリーインデックス

●全文インデックス

次に詳しく説明するのは、

ツリーインデックスと全文インデックスです。

#ハッシュインデックス

ハッシュインデックスを学習する前に、まずハッシュアルゴリズムという基本的な知識を理解します。ハッシュアルゴリズムは、時間計算量が O(1) である一般的に使用されるアルゴリズムです。インデックスだけでなく、さまざまなデータベースアプリケーションでも使用されます。

ハッシュテーブル

ハッシュテーブル（ハッシュテーブル） ハッシュテーブルとも呼ばれ、ダイレクトアドレッシングテーブルで構成されます。改善されました。

この表では、

はキーワードの完全なセットを表し、 MySQL InnoDB インデックスの原則とアルゴリズム K
は実際のキーワードを表し、右側の配列 (ハッシュ) table) メモリ内で直接アドレス指定できる連続空間を表し、実際のデータの実アドレスは、ハッシュテーブルの各スロットに関連付けられた一方向リンクリストに格納されます。右側の配列がダイレクトアドレッシングテーブルを直接使用している場合、キーワード K ごとに h[K] が繰り返しなく存在することになり、問題が発生します。の U データは大きすぎて、コンピュータの利用可能な容量に対して実用的ではありません。また、コレクション

と U の比率が小さすぎる場合、割り当てられたスペースのほとんどが無駄になります。そこで、ハッシュテーブルを使用し、いくつかの関数 h(k) を通じてマッピング関係を決定します。これにより、離散データが、配列ですが、複数のキーワードが同じスロットにマッピングされる問題が発生します。この状況は衝突

(衝突)

と呼ばれます。最も単純な解決策はデータベースで使用されます: リンクメソッド (チェーン) 。つまり、各スロットには単一リンクリストが格納され、衝突するすべての要素がリンクリスト内のノードを順番に形成します。ノードが存在しない場合、リンクリストは NULL を指します。使用される関数 h(k) はハッシュ関数となり、適切にハッシュ化できる必要があります。衝突を避けるか、衝突を最小限に抑えることが最善です。一般に、ハッシュ化されたキーワードをより適切に処理するには、キーワードを自然数に変換し、除算ハッシュ、乗算ハッシュ、またはグローバルハッシュを通じて実装します。データベースは通常、除算ハッシュを使用します。つまり、スロットが m 個ある場合、各キー k に対して法 m を計算します:

h(k) = k % m

。 #InnoDB

ストレージエンジンのハッシュアルゴリズムInnoDBストレージエンジンはハッシュアルゴリズムを使用して辞書を検索し、競合メカニズムはリンクリストを使用し、ハッシュ関数は分割ハッシュを使用します。バッファープールのハッシュテーブルの場合、バッファープール内の各ページには、同じハッシュ値を持つページを指す chain

ポインターがあります。除算ハッシュの場合、

m の値は、バッファプールページ数の 2 倍よりわずかに大きい素数です。現在の innodb_buffer_pool_size サイズが 10M の場合、合計 640 16KB ページがあり、1280 スロットを割り当てる必要があります。素数は 1399 よりわずかに大きいため、クエリバッファプール内のページをハッシュするために、1399 スロットを持つハッシュテーブルが割り当てられます。 各ページを自然数に変換するために、各テーブルスペースには space_id が付けられています。ユーザーがクエリしたいのは、スペース内の連続する 16KB

です。ページ、つまり、オフセット

(オフセット) 、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

ログイン後にコピー

アダプティブハッシュの使用は、最後の行の ハッシュ検索/非ハッシュ検索によって判断され、ハッシュインデックスの使用効率を判断できます。

innodb_adaptive_hash_index パラメータを使用して、この機能を無効または有効にできます。この機能はデフォルトで有効になっています。

B ツリーインデックス

B ツリーインデックスは現在リレーショナルデータベースシステムでの検索に最も一般的に使用され、効果的なインデックス。その構造はバイナリツリーに似ており、キーと値のペアに基づいてデータを迅速に見つけることができます。 B tree（バランスツリー）は、Btree（バランスツリーバランス二分木）とインデックス逐次アクセス方式（ISAM）で構成されます。 : シーケンスアクセスメソッドから進化したインデックス)、これらはすべて古典的なデータ構造です。 MyISAM エンジンは、もともと ISAM データ構造を参照して設計されました。

基本的なデータ構造

B ツリーデータ構造を理解するには、まずいくつかの基本的な知識を理解します。

二分探索法

半探索法とも呼ばれ、データを順番に並べ、その都度中間値と比較してスキップする方法です。検索: 範囲を半分に減らし、ターゲットを素早く見つけるアルゴリズム。アルゴリズムの複雑さは log2(n) で、順次検索よりも高速です。

図に示すように、順序付きリストから 48 を検索するには、3 の手順のみが必要です。

MySQL InnoDB インデックスの原則とアルゴリズム

詳細なアルゴリズムについては、二分探索アルゴリズムを参照してください。

二分探索ツリー

二分探索ツリーの定義は、二分木では、左のサブツリーの値は常にルートキーの値よりも小さいということです。そしてルートキーの値は常に右のサブツリーの値より小さくなります。検索する際は毎回ルートから検索を開始し、比較結果に基づいて左の部分木を検索し続けるか右の部分木を検索し続けるかを判断します。検索方法は二分探索方法と非常によく似ています。

MySQL InnoDB インデックスの原則とアルゴリズム

バランス二分木

二分探索木の定義は非常に幅広く、任意に構築できますが、極端な場合、クエリ効率は、左側のサブツリーのみを含む二分探索ツリーなどの順次検索と同じになります。

MySQL InnoDB インデックスの原則とアルゴリズム

最大のパフォーマンスを備えた二分探索ツリーを構築したい場合は、ツリーのバランスが取れている必要があります。つまり、バランスの取れた二分木が必要です。 G. M. Adelson-Velsky および Evgenii Landis であり、AVL ツリーとしても知られています)。これは、任意のノードの 2 つのサブツリーの最大高さの差を 1 まで満たさなければならない二分探索木として定義されます。バランスのとれたバイナリツリーは比較的優れた構造を持ち、最高のパフォーマンスを得るには最適なバイナリツリーを確立する必要がありますが、ツリーの維持コストが高いため、通常はバランスのとれたバイナリツリーで十分です。

バランスのとれたバイナリツリークエリは非常に高速ですが、ツリーが変化すると、1 回以上の左右の回転を通じてツリーの新しいバランスを実現する必要があります。ここではそれについては話しません。

B  ツリー

基本的なデータ構造を理解した後、見てみましょう B ツリーの実装の定義は非常に複雑ですが、簡単に言うと、B ツリーに規則を追加することです:

1. リーフノードにはデータが格納され、非リーフノードストアポインター

2.すべてのリーフノードは、左から右への二重リンクリストに記録されます

目標は、ディスクまたはその他の直接アクセス補助デバイス用に設計されたバランスの取れた検索ツリーです。。このツリーでは、キー値の大きさに応じてすべてのレコードが同じ階層の葉ノードに配置され、葉ノード間にはポインタが接続され（非連続記憶）、二重連結リストが形成されます。インデックスノードはバランスツリー法に従って構築されており、迅速な検索のために特定のリーフノードを指すポインターがあります。

次の B ツリーのデータが少ない場合、高さは 2 になり、各ページは 4 レコードを格納するように固定されます。ファンout 5 (図の灰色の部分) に固定されます。リーフノードは、ツリーの高さを減らし、迅速な検索を実行するために、複数のデータを格納します。

MySQL InnoDB インデックスの原則とアルゴリズム

28、70、95 3 個のデータを挿入すると、B ツリーにはデータがいっぱいあるため、ページを分割する必要があります。このとき、高さは 3 に変わり、各ページには 4 のレコードが残っています。二重リンクのリストは描画されませんが、まだ存在しています。バランスの取れた二分木のプロトタイプ。

MySQL InnoDB インデックスの原則とアルゴリズム

InnoDBB  ツリーインデックス #

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辅助索引辅助索引又称非聚集索引，其叶子节点不包含行记录的全部数据，而是包含一个书签<code>（bookmark）</code>，该书签指向对应行数据的聚集索引，告诉<code>InnoDB</code>存储引擎去哪里查找具体的行数据。辅助索引与聚集索引的关系就是结构相似、独立存在，但辅助索引查找非索引数据需要依赖于聚集索引来查找。 <img src="https://img.php.cn/upload/image/639/959/687/157484689554534MySQL%20InnoDB%20%E3%82%A4%E3%83%B3%E3%83%87%E3%83%83%E3%82%AF%E3%82%B9%E3%81%AE%E5%8E%9F%E5%89%87%E3%81%A8%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" title="157484689554534MySQL InnoDB インデックスの原則とアルゴリズム" alt="MySQL InnoDB インデックスの原則とアルゴリズム">全文索引我们通过<code>B+</code> 树索引可以进行前缀查找，如：<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 中国語 Web サイトの他の関連記事を参照してください。