Zhang San を見つけるための要件が​​あります。二分探索木を使用しない場合、7 回検索する必要があります。二分探索木を使用すると、必要な値を見つけるのに 4 回の検索だけで済みます。欲しい。
上記によると、確かに二分探索木を使用するとクエリの数は削減できますが、データベース内のデータが 1、2、3、4、5 と順番に増加していく場合はどうなるか考えたことはありますか? 6、7? 二分探索木を使い続けると、リンク リストになります。したがって、7 を見つけたい場合は、7 回検索し、テーブルを 7 回スキャンする必要があります。これはインデックスを作成しないことと変わりませんが、これもデメリットの 1 つです。次の図は例です。

2) バランス型バイナリ ツリー: AVL ツリーとも呼ばれ、左右のサブツリー間の高さの差の絶対値は 1 を超えません。 、 、および 左側と右側のサブツリーは両方とも平衡型二分木であり、AVL ツリーは発明された最も初期の自己平衡型二分探索ツリーです。 AVL ツリーでは、任意のノードの 2 つのサブツリー間の最大高さの差は 1 のみであるため、高さバランスの取れたツリーとも呼ばれます。クエリ、追加、削除は、平均でも最悪の場合でも O(log n) です。追加と削除では、ツリーのバランスを再調整するために 1 回以上のツリーの回転が必要になる場合があります。
二分木を導入する目的は、二分木探索の効率を向上させ、木の平均探索長を短縮することです。そのためには、各二分木にノードを挿入するときに木の構造を調整する必要があります。二分木探索はバランスを維持できるため、ツリーの高さが低くなり、ツリー探索の平均長が短くなる可能性があります。
バランス型バイナリ ツリーの特性は次のとおりです。
1. その左のサブツリーと右のサブツリーは両方とも AVL ツリーです
2. 左のサブツリーと右のサブツリーの高さの差が超えることはできません1
例:
3) 赤黒の木 : 赤黒の木は、上にある木であることがわかります。バランスの取れたバイナリ ツリー 赤黒ツリー このツリーは「完全なバランス」を追求するのではなく、バランス要件を部分的に達成することのみを追求し、回転要件を軽減してパフォーマンスを向上させます。さらに、その設計により、アンバランスは 3 回転以内に解決されます。赤黒ツリーでは、アルゴリズムの時間計算量は AVL と同じであり、統計的パフォーマンスにより AVL ツリーの方が高くなります。したがって、赤黒ツリーは、バランス二分木と比較して、厳密な意味でのバランス二分木ではなく、赤黒ツリーの挿入・削除効率は高く、クエリ効率は相対的に低くなります。ただし、この 2 つの間のクエリ効率の違いは、比較すると基本的に無視できるほどです。赤黒木の特徴は次のとおりです。
1. ノードは赤または黒です。
2. ルート ノードは黒です。
3. 各赤いノードの 2 つの子ノードは黒です。 (赤いノードの子は黒いノードでなければなりません)
4. 任意のノードからその各リーフまでのすべてのパスには、同じ数の黒いノードが含まれます。
したがって、赤黒ツリーは黒バランスのツリーであり、左側のサブツリーと右側のサブツリーの高さの差が 2 を超えることはありません。赤いノードの親ノードと子ノードは黒いノードのみにすることができます。
サンプル画像:

4) BTree (B ツリー) : もちろん、上記の赤黒ツリー、パフォーマンスは非常に優れています高い。上図を例にすると、ツリーの高さは最大4で、データは合計9個ですが、Mysqlデータベースの場合、数百万、数千万のデータが存在します。ツリーの高さは計り知れません。たとえば、数百、1 万個のデータの場合、データのクエリには 30 ～ 50 回、またはそれ以上のディスク IO 時間が必要ですが、これでは明らかに Mysql インデックスの効率的なクエリ効率を満たせません。したがって、ツリーの高さを制御すると、ディスク IO リクエストの数が大幅に削減され、高さを 4 に制御すると、データのクエリに必要なディスク IO は 4 回だけになります。
しかし、ツリーの高さはどうやって制御するのでしょうか? 赤黒ツリーはノードごとに 1 つの要素しか格納しません。各ノードに複数の要素が格納されたらどうなるでしょうか? これで高さの問題は解決できます。疑問を持つ学生もいるはずです。すべて入力してくださいすべての要素をノード上に配置すると、高さの値は 1 になります。高速ではないでしょうか。このように考えるのは間違いなく間違いです。Mysql にはディスク IO を処理するたびにサイズ制限があり、Mysql では各ノードのサイズが 16K に制限されています。 MySQL の制限ノード サイズを確認したい学生は、次の SQL を実行できます。
'Innodb_page_size' のようなグローバル ステータスを表示します
次の図は、BTree の特性を示す例として使用されます
BTree:
1. すべてのインデックス要素は繰り返されません
2. ノード データ インデックスは左から右に増加します
3. リーフ ノードの深さは同じで、リーフ ノードのポインタは空です
4. リーフ ノードと非リーフ ノードの両方にインデックスとデータが格納されます

5) B ツリー : 上で述べたように、BTree はツリーの高さを制御し、Mysql のインデックス作成のニーズを満たすことができますが、最終的には Mysq インデックスの実装がは BTree ではなく B Tree ですが、Mysql が B-tree に少し手を加えて B-tree を取得したものであり、B-tree のアップグレード版であることもわかります。
例として図を見てみましょう:

この図からわかるように、非リーフ ノードはインデックスのみを格納し、データは格納しません。また、ノード間ではポインタが使用されます。リーフノードが接続されています。 B ツリーのリーフ ノードと非リーフ ノードの両方にインデックスとデータが格納され、リーフ ノードのポインタは空です。B ツリーはデータをリーフ ノードに配置するため、非リーフ ノードはインデックスとデータを格納できます。毎回、より多くのインデックス ディスク IO からより多くのインデックスを取得することもできます。
B ツリーの機能は次のとおりです:
1. 非リーフ ノードにはデータは保存されず、インデックス (冗長) と下位レベルのポインターのみが保存され、さらに多くのインデックスを配置できます。
2 .リーフ ノードにはすべてのインデックス フィールドとデータが含まれます
3. リーフ ノードはインターバル アクセスのパフォーマンスを向上させるためにダブル ポインターで接続されます

Baidu で描画された B ツリーと多くのブログ それは間違っています、穴を避けなければなりません。
Mysql による B ツリーの公式説明に興味がある場合は、チェックしてください。
リンク: Mysql 公式 Web サイト.

4. インデックスの分類

1. インデックスのストレージの関連付けによる分類: 大きく 2 つのカテゴリに分かれます
1.) クラスター化インデックス (クラスター化インデックス) : リーフ ノードには完全なデータ レコードが含まれており、テーブルに返す必要はありません。
2.) 非クラスター化インデックス: テーブル を返し、二次ツリー検索を実行する必要があります。これはパフォーマンスに影響します。

1.1) MySQL には、MyISAM と InnoDB という 2 つの一般的に使用されるストレージ エンジンがあることは誰もが知っていますが、2 つのストレージ エンジンの基礎となるデータ ストレージ構造を実際に理解していますか?
説明するための例として写真を取り上げます:
test.myisam テーブルは MyISAM ストレージ エンジンであり、アクター テーブルは InnoDB ストレージ エンジンです。MyISAM ストレージ エンジンには 3 つのストレージ エンジンがあることがわかります。ファイル、つまりfrmとMYD、MYIはfrm-frameの略で分かりやすい テーブルの構造を格納する MYD-MYDataにデータが格納される MYI-MYIndexにインデックスが格納される インデックスとデータが格納されるInnoDB には frm と IBD のみがあり、frm も格納されるテーブルの構造は同じであり、IBD ファイルにはインデックスとデータが格納される点が InnoDB や MyISAM とは異なります。
次の図は、MyISAM ストレージ エンジンの主キー インデックスにテーブルの戻り操作が必要であることを示す例として使用されます (非クラスター化インデックス)
ここで、15 には主キーが格納されます。インデックス、0x07 には行レコードのディスク ファイル アドレス ポインタ 15 の場所が格納されます。たとえば、15 のデータを見つけたい場合は、まず主キー インデックス ツリーを通じて 15 に対応するポインタを見つけ、次にこのポインタを見つけてから、MyD ファイルに移動して特定のデータを見つけます。2 つの手順が必要です。このプロセスはテーブル リターン操作と呼ばれます。
2.1) 次の図は、InnoDB ストレージ エンジンの主キー インデックスがテーブルの戻り操作を必要としないことを示す例として使用されています。 (クラスター化インデックス)
InnoDB ストレージ エンジン サブノードは、まず行 15 にインデックスを格納し、15 より下の列にはインデックスが配置されている行の他のすべてのフィールドを格納します。必要に応じて、2 回目のツリー検索を行わずに、15 のデータを直接見つけることができます。

2. 機能別分類: 主に 5 つのカテゴリに分類されます
2.1 主キー インデックス: InnoDB の主キー インデックスはテーブルの戻り操作を必要としません
2.2 通常のインデックス (セカンダリ インデックス): InnoDB の通常のインデックスはテーブルの戻り操作が必要ですが、セカンダリ インデックスの場合は、デフォルトで主キーとの結合インデックスになります。
2.3 一意のインデックス
2.4 フルテキスト インデックス
2.5 共用体インデックス: 左端の接頭辞の原則を満たす必要があります

3. 2.2 で、通常のインデックスにはテーブルの戻り操作が必要であると述べましたが、テーブルの戻り操作を必要としない通常のインデックスはありますか? 答えは「はい」です。特定のクエリでは、インデックスはすでにクエリのニーズをカバーしているため、これをカバーインデックスと呼びます。このとき、テーブルに戻る必要はありません。
カバーインデックスを使用するとツリー検索の数が減り、クエリのパフォーマンスが大幅に向上するため、カバーインデックスの使用は一般的なパフォーマンス 最適化 の手段です。

例: 以下は、このテーブルの初期化ステートメントです。

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),
(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

上記のテーブル T で、s​​elect * from T (k は 3 ～ 5) を実行すると、ツリー検索操作は何回実行する必要があり、スキャンされる行は何行になりますか?
次に、この SQL クエリ ステートメントの実行フローを見てみましょう。下の写真を見てください。

1.) k インデックス ツリーでレコード k=3 を検索し、ID = 300 を取得します。
2.)
次に、次の手順に進みます。 ID インデックス ツリーは、ID=300;3 に対応する R3 を見つけます。)
k インデックス ツリーの次の値 k=5 を取得し、ID=500;4 を取得します。 .)
ID インデックス ツリーに戻り、ID=500 に対応する R4 を見つけます; 5.)

この処理のうち、主キーインデックスツリー検索に戻る処理をテーブルリターン

実行されたステートメントが select ID from T where k between 3 and 5 の場合、現時点では、ID の値を確認するだけでよく、ID の値はすでに k インデックスに含まれています。ツリーなので、直接提供できます。クエリ結果をテーブル に返す必要はありません。つまり、このクエリでは、インデックス k にクエリ要件が「covered

1.)
結合インデックスの 1 つの列にのみ null 値が含まれる場合、インデックスは無効になります。 2.)
計算後のインデックスは無効になります。すべてのインデックスが無効です。3.)
クエリ条件で関数を使用すると、インデックスが失敗します4.)
で != または を使用します。 where 句演算子を使用すると、インデックス障害が発生します。5.)
or の使用は避けてください。インデックス障害が発生します。6.)
ファジー クエリを使用すると、インデックス障害が発生します。次のように使用できます。 like '%a%'7 の代わりに、like ' a%' を使用します。)
カバーするインデックスを使用し、select * ステートメントを減らすようにしてください 8。)
左端を満たすようにしてください。プレフィックス ルール。インデックス 9 の列はスキップせず、左端の列から開始します。)

create table employees(
id int primary key auto_increment comment '主键自增',
name varchar(30) not null default '' comment'名字',
age int not null default 1 comment '年龄',
id_card varchar(40) not null default '' comment '身份证号',
position varchar(40) not null default '' comment '位置'
);

-- 创建联合索引
create index name_index on employees (name,age,position);

-- 插入一条数据
insert into employees(name,age,id_card,position) values('张三',15,
'201124199011035321','北京');

--  下面以10条sql测试，注意建立的联合索引顺序是 name，age，position
1.explain select * from employees where age=15 and position='北京' and name='张三';

2.explain select * from employees where name='张三' and age=15 and position='北京';

3.explain select * from employees where age=15 and name='张三';

4.explain select * from employees where position='北京' and name='张三';

5.explain select * from employees where position='北京' and age=15;

6.explain select * from employees where position='北京' and age>15 and name='张三';

7.explain select * from employees where position='北京';

8.explain select * from employees where age=15;

9.explain select * from employees where name='张三';

10.explain select * from employees where name != '张三';

以上10条sql有哪些是索引失效，有哪些是索引没有失效的呢？
相信同学们已经有了答案，但是答案对不对呢，下面我们一起分析下。
首先说第1条，查询条件把3个索引全部用上了，但是索引的顺序有变化，由name，age，position变成
了age，position，name，想到这里肯定有很多同学给出的答案就是索引失效，但是事实证明这个结果
是错的，索引生效，肯定有很多同学疑惑，为什么呢，这条sql不满足最左原则法则呀，这就要涉及到sql
的执行流程了，这里博主简单说下，sql执行有1个优化器的过程，优化器的作用之一就是索引的选择优化，
所以优化器帮我们把索引的顺序变成正确的了，所以索引生效。
下面是第1条按照索引顺序sql和第2条没有按照索引顺序sql的执行结果。

执行结果入下图：可以发现全部生效。

想学习sql的执行流程的可以看博主的另一篇关于sql执行流程的文章哦。
有的同学有疑问了，那最左原则没有用了吗？
答案：有用的。

现在我们说下第3、4、5条sql
第3条：
explain select * from employees where age=15 and name='张三';
sql在执行的时候，优化器替我们把索引的顺序优化了，由 age -> name 变成 name -> age，这时
索引是生效的。
第4条：
explain select * from employees where position='北京' and name='张三';
索引顺序优化为name - > position,但是这时索引只有name索引生效，position没有生效，因为我
们建立的索引顺序是 name  -> age - > position，你会发现跳过了age，索引本质也是一棵树，少
了一个节点，下面的索引当然不会生效了，这就没有满足最左原则法则。
第5条：
explain select * from employees where position='北京' and age=15;
这就和第4条sql一样的道理了，第一个索引都不见了，后面的不可能生效。

执行结果如下：

下面说第6条sql，剩下的sql都是和之前的sql一样的道理。
explain select * from employees where position='北京' and age>15 and name='张三';
这条sql我们会发现，把索引字段全部使用了并且当作条件查询，不一样的是age是范围查找，优化器替我
们把索引顺序优化成 name  -> age - > position ，按照我们索引优化第2条：在列上做计算索引失效，范围之后的索引全部失效，想必答案同学们都知道了。

执行结果如下：

推奨学習: mysql ビデオ チュートリアル