MySQL についての私の理解パート 2: インデックス

mysql チュートリアル コラムでは、今日のインデックス関連の知識を紹介します。

MySQL シリーズの 2 番目の記事では、インデックス タイプ、データ モデル、インデックス実行プロセス、左端のプレフィックス原則など、MySQL のインデックス作成に関するいくつかの問題について主に説明します。 、インデックスの失敗とインデックスのプッシュダウンなど。

私が初めてインデックスについて学んだのは、2 年生のデータベース原理コースでした。クエリ ステートメントが非常に遅い場合は、特定のフィールドにインデックスを追加することでクエリの効率を向上させることができます# ＃＃。

もう 1 つの非常に古典的な例があります: データベースを辞書、インデックスをディレクトリと考えることができます。辞書のディレクトリを使用して単語をクエリすると、インデックスの役割が反映されます。 。

1. インデックスの種類

MySQL では、インデックスのロジックやフィールドの特性に基づいて、インデックスは通常のインデックス、一意のインデックス、主キー インデックス、 Union インデックスとプレフィックス インデックス。

通常のインデックス: 制限のない最も基本的なインデックス。
• 一意のインデックス: インデックス列の値は一意である必要があります。
• 主キー インデックス: 特別な一意のインデックス。主キーとしての値を空にすることはできません。
• 結合インデックス: 結合インデックスは、インデックス列に複数のフィールドを持つ通常のインデックスです。
• 左端の接頭辞の原則を考慮する必要があります。
接頭辞インデックス: 文字型の最初の数文字、またはバイナリ型の最初の数バイトにインデックスを付けます。

物理ストレージとは区別される別のインデックス分類、クラスター化インデックスと非クラスター化インデックスがあります。

クラスター化インデックス: インデックスの順序はデータの格納順序と一致しており、そのリーフ ノードにはデータ行が格納されます。
• 非クラスター化インデックス: 非クラスター化インデックスのリーフ ノードにはクラスター化インデックスの値が格納され、クラスター化インデックスに基づいて作成されます。

簡単に言うと、いわゆるクラスター化インデックスとは、インデックス キーとデータ行が一緒になっていることを意味し、非クラスター化インデックスのインデックス キーに対応する値は、クラスター化インデックス。

2. インデックス データ構造

インデックスの実装に使用される一般的なデータ構造には、ハッシュ テーブル、順序付けされた配列、検索ツリーなどがあります。

2.1 ハッシュ インデックス

ハッシュ テーブルは、データをキーと値の形式で保存するコンテナです。HashMap と同様に、ハッシュ インデックスも特定のハッシュ関数を通じてキーを計算します。インデックス値を取得し、キーに対応する値を配列の対応する位置に格納します。ハッシュ関数によって計算された同じインデックス値を持つ 2 つのキーがある場合 (ハッシュの競合が発生する)、配列内のこの位置はリンクされたリストになり、すべての値を同じハッシュ値で保存します。

したがって、一般に、ハッシュ テーブル内の等価クエリの時間計算量は O(1) に達する可能性がありますが、ハッシュの競合の場合は、リンク リスト内のすべての値をさらに走査する必要があります。条件に合うデータは見つかるでしょうか？

さらに、ハッシュ関数によって計算されたインデックスが不規則であることを考慮すると、ハッシュ テーブルはすべてのキーが完全にハッシュ化され、スペースを無駄にすることなくキーが均等に分散されることを望んでいます。つまり、ハッシュ テーブルは非シーケンシャルであるため、間隔クエリにハッシュ テーブルを使用すると非常に時間がかかります。ソートの場合も同様です。

したがって、ハッシュ テーブルは同等のクエリにのみ適しています。

2.2 順序付き配列

名前が示すように、順序付き配列はキーの順序で配置された配列です。等価なクエリの時間計算量は、バイナリ クエリを使用すると O(logN) に達することがあります。ハッシュテーブルよりも劣ります。

ただし、順序付き配列による範囲クエリの方が効率的です。まずバイナリ クエリによって最小値 (または最大値) を見つけ、次に別の境界まで逆にたどります。

並べ替えに関しては、順序付けされた配列は本質的に順序付けされており、自然に並べ替えられます。もちろん、並べ替えフィールドはインデックス フィールドではないため、これについては個別に説明します。

しかし、順序付き配列には欠点があり、配列の要素が連続して順序付けされているため、このときに新しいデータ行を挿入すると、順序付き配列の順序性を維持するために、データ行をさらに大きくする必要があります。要素キーよりもすべての要素が 1 単位後ろに移動され、挿入できるスペースが確保されます。そして、この方法でインデックスを維持するコストは非常に高くなります。

したがって、順序付けされた配列は、衣服が初期化された後に更新されなくなるデータを格納するのに適しています。

2.3 検索ツリー

データ構造を知っている人は、検索ツリーがクエリ時間計算量 O(logN) であり、更新時間計算量も O(logN) データであることを知っているはずです。構造。したがって、ハッシュ テーブルや順序付けされた配列と比較して、検索ツリーではクエリと更新の両方の側面が考慮されます。 MySQL で最も一般的に使用されるデータ モデルが検索ツリーであるのは、このためです。

インデックスがディスク上に保存されることを考慮すると、検索木が二分木の場合、子ノードは左右 2 つしか持てません。大量のデータ比較がある場合、二分木はMySQL がクエリを実行するとき、ツリーの高さによって過剰なディスク I/O 時間が発生し、クエリの効率が低下する可能性があります。

2.4 フルテキスト インデックス

さらに、フルテキスト インデックスがあり、逆インデックスを確立することで、フィールドが含まれているかどうかを判断する問題を解決します。

転置インデックスは、全文検索対象の文書または文書グループ内の単語の格納場所のマッピングを保存するために使用されます。転置インデックスを通じて、次の内容を含む文書のリストを迅速に取得できます。この言葉をもとにしたこの言葉。

キーワードで検索する場合、全文インデックスが便利です。

3. InnoDB の BTree インデックス

3.1 B ツリー

これは比較的単純な B ツリーです。

画像ソース: Data Structure Visualizations

上記のサンプル画像からも、この B ツリーの下部にあることがわかります。リーフ ノードはすべての要素を順番に保存しますが、非リーフ ノードはインデックス列の値のみを保存します。

3.2 BTree インデックスの図示

InnoDB では、BTree に基づくインデックス モデルが最も一般的に使用されますが、ここでは InnoDB の BTree インデックスの構造を示す実際の例を示します。

CREATE TABLE `user`  (  `id` int(11) NOT NULL,  `name` varchar(36) DEFAULT NULL,  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,  INDEX `nameIndex`(`name`) USING BTREE
) ENGINE = InnoDB;-- 插入数据insert into user1(id,name,age) values (1,'one',21),(2,'two',22),(3,'three',23),(4,'four',24),(5,'five',25);复制代码

このテーブルには 2 つのフィールドしかありません。主キー ID と名前フィールドです。また、インデックス列として名前フィールドを持つ BTree インデックスが確立されます。

主キー ID フィールドに基づくインデックスは主キー インデックスとも呼ばれ、そのインデックス ツリー構造は次のとおりです: インデックス ツリーの非リーフ ステージには主キー ID の値が格納され、その値はリーフ ノードに格納されるのは、次の図に示すように、主キー id に対応するデータ行全体です。主キー インデックスのリーフ ノードには、対応する主キー ID が格納されます。 データ行全体である主キー インデックスは、クラスター化インデックスとも呼ばれます。

名前フィールドを列として持つインデックス ツリーでは、非リーフ ノードもインデックス列の値を格納し、リーフ ステージに格納される値は 主キーの値です。 id

は、次の図に示すように表示されます。

3.3 インデックス実行プロセス

まず、ユーザー テーブルの id=1 のデータ行をクエリする次の SQL 文を見てください。

select * from user where id=1;复制代码

この SQL の実行プロセスは非常に簡単です。ストレージ エンジンは、主キー ID のインデックス ツリーを調べます。ID=1 が見つかると、ID=1 のデータ行を返します。インデックス ツリー (主キーにより値は一意であるため、ヒット ターゲットが見つかった場合、検索は停止され、結果セットが直接返されます)。

3.3.1 表に戻る

次に、主キーインデックスとは少し状況が異なりますが、通常のインデックスを使用したクエリを見てみましょう。

select * from user where name='one';复制代码

上記の SQL クエリ ステートメントのプロセスは次のとおりです: まず、ストレージ エンジンは通常のインデックス名列のインデックス ツリーを検索します。名前が 1 に等しいレコードがヒットすると、ストレージ エンジンはは非常に重要な手順を実行する必要があります。：

表に戻る

。

通常のインデックスのインデックス ツリーのサブノードには主キーの値が格納されるため、クエリ ステートメントで主キー ID とインデックス列以外のフィールドをクエリする必要がある場合は、主キー インデックスに戻る必要があります。主キー ID の値に基づいて、ツリー内でクエリを実行して主キー ID に対応するデータ行全体を取得し、クライアントが必要とするフィールドを取得した後、その行を結果セットに追加します。

その後、ストレージ エンジンは、name='one'

を満たさない最初のレコードが見つかるまでインデックス ツリーの検索を続け、最終的にヒットしたすべてのレコードをクライアントに返します。 。

通常のインデックス

からクエリされた主キー ID 値に基づいて、主キー インデックス内のデータ行全体をクエリするプロセスを と呼び、テーブル リターンと呼びます。

データの量が非常に大きい場合、テーブルの戻りは非常に時間がかかるプロセスであるため、テーブルの戻りを回避するように努める必要があります。これにより、テーブルの戻りを回避するためにカバーインデックスを使用するという次の質問につながります。

3.3.2 インデックスのカバー

前の table return の質問に次のような記述があることに気づいたかどうかわかりませんが、「クエリ ステートメントで主キーをクエリする必要がある場合」 ID とインデックス列 "... 以外のフィールド" このシナリオでは、テーブルを返すことによって他のクエリ フィールドを取得する必要があります。言い換えれば、クエリ ステートメントで主キー ID とインデックス列のフィールドのみをクエリする必要がある場合、テーブルを返す必要はありません。

このプロセスを分析してみましょう。まず、結合インデックスを作成します。

alter table user add index name_age ('name','age');复制代码

このインデックス ツリーの構造図は次のようになります。

結合インデックス インデックス ツリーの子ノードの順序は次のとおりです。ソートするには、

order by name, age

と似ており、通常のインデックスと同様に、そのインデックスに対応する値が主キーの値になります。

select name,age from user where name='one';复制代码

上面这条 SQL 是查询所有 name='one' 记录的 name 和 age 字段，理想的执行计划应该是搜索刚刚建立的联合索引。

与普通索引一样，存储引擎会搜索联合索引，由于联合索引的顺序是先按照 name 再按照 age 进行排序的，所以当找到第一个 name 不是 one 的索引时，才会停止搜索。

而由于 SQL 语句查询的只是 name 和 age 字段，恰好存储引擎命中查询条件时得到的数据正是 name, age 和 id 字段，已经包含了客户端需要的字段了，所以就不需要再回表了。

我们把只需要在一棵索引树上就可以得到查询语句所需要的所有字段的索引成为覆盖索引，覆盖索引无须进行回表操作，速度会更快一些，所以我们在进行 SQL 优化时可以考虑使用覆盖索引来优化。

4. 最左前缀原则

上面所举的例子都是使用索引的情况，事实上在项目中复杂的查询语句中，也可能存在不使用索引的情况。首先我们要知道，MySQL 在执行 SQL 语句的时候一张表只会选择一棵索引树进行搜索，所以一般在建立索引时需要尽可能覆盖所有的查询条件，建立联合索引。

而对于联合索引，MySQL 会遵循最左前缀原则：查询条件与联合索引的最左列或最左连续多列一致，那么就可以使用该索引。

为了详细说明最左前缀原则，同时说明最左前缀原则的一些特殊情况。

5. 索引失效场景

即便我们根据最左前缀的原则创建了联合索引，还是会有一些特殊的场景会导致索引失效，下面举例说明。

假设有一张 table 表，它有一个联合索引，索引列为 a,b,c 这三个字段，这三个字段的长度均为10。

CREATE TABLE `demo`  (  `a` varchar(1) DEFAULT NULL,  `b` varchar(1) DEFAULT NULL,  `c` varchar(1) DEFAULT NULL,  INDEX `abc_index`(`a`, `b`, `c`) USING BTREE
) ENGINE = InnoDB;复制代码

5.1 全字段匹配

第一种情况是查询条件与索引字段全部一致，并且用的是等值查询，如：

select * from demo where a='1' and b='1' and c='1';select * from demo where c='1' and a='1' and b='1';复制代码

输出上述两条 SQL 的执行计划来看它们使用索引的情况。

mysql> explain select * from demo where a='1' and b='1' and c='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref               | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 18      | const,const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)

mysql> explain select * from demo where c='1' and a='1' and b='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref               | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 18      | const,const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)复制代码

第一条 SQL 很显然能够用到联合索引。

从执行计划中可以看到，第二条 SQL 与第一条 SQL 使用的索引以及索引长度是一致的，都是使用 abc_index 索引，索引长度为 18 个字节。

按理说查询条件与索引的顺序不一致，应该不会用到索引，但是由于 MySQL 有优化器存在，它会把第二条 SQL 优化成第一条 SQL 的样子，所以第二条 SQL 也使用到了联合索引 abc_index。

综上所述，全字段匹配且为等值查询的情况下，查询条件的顺序不一致也能使用到联合索引。

5.2 部分字段匹配

第二种情况是查询条件与索引字段部分保持一致，这里就需要遵循最左前缀的原则，如：

select * from demo where a='1' and b='1';select * from demo where a='1' and c='1';复制代码

上述的两条查询语句分别对应三个索引字段只用到两个字段的情况，它们的执行计划是：

mysql> explain select * from demo where a='1' and b='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref         | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 12      | const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+1 row in set, 1 warning (0.00 sec)

mysql> explain select * from demo where a='1' and c='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref   | rows | filtered | Extra                    |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 6       | const |    1 |   100.00 | Using where; Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+1 row in set, 1 warning (0.00 sec)复制代码

从它们的执行计划可以看到，这两条查询语句都使用到了 abc_index 索引，不同的是，它们使用到索引的长度分别是：12、6 字节。

在这里需要额外提一下索引长度的计算方式，对于本例中声明为 varchar(1) 类型的 a 字段，它的索引长度= 1 * (3) + 1 + 2 = 6。

• 第一个数字 1 是该字段声明时的长度。
• 第二个数字 3 是该字段字符类型的长度：utf8=3, gbk=2, latin1=1。
• 第三个数字 1 是该字段的默认类型，若默认允许 NULL，第三个数字是 1，因为 NULL 需要一个字节的额外空间；若默认不允许 NULL，这里应该是0。
• 第四个数字 2 是 varchar 类型的变长字段需要附加的字节。

所以这两条查询语句使用索引的情况是：

1. 使用联合索引，索引长度为 12 字节，使用到的索引字段是 a,b 字段；
2. 使用联合索引，索引长度为 6 字节，使用到的索引字段是 a 字段；

由此可见：最左前缀原则要求，查询条件必须是从索引最左列开始的连续几列。

5.3 范围查询

第三种情况是查询条件用的是范围查询（,!=,=,between,like）时，如：

select * from demo where a='1' and b!='1' and c='1';复制代码

这两条查询语句的执行计划是：

mysql> EXPLAIN select * from demo where a='1' and b!='1' and c='1';
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+| id | select_type | table | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+|  1 | SIMPLE      | demo  | NULL       | range | abc_index     | abc_index | 12      | NULL |    2 |    10.00 | Using where; Using index |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+1 row in set, 1 warning (0.00 sec)复制代码

从执行计划可以看到，第一条 SQL 使用了联合索引，且索引长度为 12 字节，即用到了 a,b 两个字段；第二条 SQL 也使用了联合索引，索引长度为 6 字节，仅使用了联合索引中的 a 字段。

综上所述，在全字段匹配且为范围查询的情况下，也能使用联合索引，但只能使用到联合索引中第一个出现范围查询条件的字段。

需要注意的是：

• like 必须要求是左模糊匹配才能用到索引，因为字符类型字段的索引树也是有序的。
• between 并不一定是范围查询，它相当于使用 in 多值精确匹配，所以 between 并不会因为是范围查询就让联合索引后面的索引列失效。

5.4 查询条件为函数或表达式

第四种情况是查询条件中带有函数或特殊表达式的，比如：

select * from demo where id + 1 = 2;select * from demo where concat(a, '1') = '11';复制代码

可能由于数据的原因（空表），我输出的执行计划是使用了联合索引的，但是事实上，在查询条件中，等式不等式左侧的字段包含表达式或函数时，该字段是不会用到索引的。

至于原因，是因为使用函数或表达式的情况下，索引字段本身的值已不具备有序性。

5.5 其他索引失效的场景

• 查询影响行数大于全表的25%
• 查询条件使用 (!=), not in, is not null
• in 查询条件中值数据类型不一致，MySQL 会将所有值转化为与索引列一致的数据类型，从而无法使用索引

6. 索引下推

上文中已经罗列了联合索引的实际结构、最左前缀原则以及索引失效的场景，这里再说一下索引下推这个重要的优化规则。

select * from demo where a > '1' and b='1';

mysql> explain select * from demo where a > '1' and b='1';
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+| id | select_type | table | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+|  1 | SIMPLE      | demo  | NULL       | range | abc_index     | abc_index | 6       | NULL |    1 |    10.00 | Using index condition |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+1 row in set, 1 warning (0.00 sec)复制代码

上面这条查询语句，从它的执行计划也可以看出，它使用的索引长度为 6 个字节，只用到了第一个字段。

所以 MySQL 在查询过程中，只会对第一个字段 a 进行 a > '1' 的条件判断，当满足条件后，存储引擎并不会进行 b=1 的判断， 而是通过回表拿到整个数据行之后再进行判断。

这好像很蠢，就算索引只用到了第一个字段，但明明索引树中就有 b 字段的数据，为什么不直接进行判断呢？

听上去好像是个 bug，其实在未使用索引下推之前整个查询逻辑是：由存储引擎检索索引树，就算索引树中存在 b 字段的值，但由于这条查询语句的执行计划使用了联合索引但没有用到 b 字段，所以也无法进行 b 字段的条件判断，当存储引擎拿到满足条件（a>'1'）的数据后，再由 MySQL 服务器进行条件判断。

在 MySQL5.6 版本中对这样的情况进行优化，引入索引下推技术：在搜索索引树的过程中，就算没能用到联合索引的其他字段，也能优先对查询条件中包含且索引也包含的字段进行判断，减少回表次数，提高查询效率。

在使用索引下推优化之后，b 字段作为联合索引列，又存在于查询条件中，同时又没有在搜索索引树时被使用到，MySQL 服务器会把查询条件中关于 b 字段的部分也传给存储引擎，存储引擎会在搜索索引树命中数据之后再进行 b 字段查询条件的判断，满足的才会加入结果集。

Ps: 执行计划中 Extra 字段的值包含 Using index condition 就代表使用到了索引下推。

7. 温故知新

1. 索引分类？聚簇索引结构？非聚簇索引结构？
2. 常用的实现索引的数据模型？
3. B+树索引的执行流程？
4. 什么是回表？如何优化？
5. 什么是覆盖索引？
6. 什么是最左前缀原则？
7. 索引在哪些情况下可能会失效？
8. 什么是索引下推？

更多相关免费学习推荐：mysql教程(视频)

以上がMySQL についての私の理解パート 2: インデックスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。