インデックスの定数モデル
インデックスの出現は、効率的なデータ検索を達成するために、唯一のそれはデータのデータ構造の効率的なインデックスを達成することができますので、インデックスの概念が導入されている多くは、最初の3つの一般的なデータ構造ハッシュテーブル、順序付き配列と検索ツリーを見てください。
- ハッシュテーブルは、キーとキーのペアで、値の値を見つけるためにキーを入力します。ハッシュテーブルの実装はとても簡単で、値を配列に入れ、ハッシュ関数を使ってキーを特定の位置に変換し、配列のこの位置に値を入れます。必然的に、複数のキー値がハッシュ関数によって同じ値に変換されることになります。この状況を処理する一つの方法は、連鎖リストを引き出すことです。現在、注文情報と注文番号snのテーブルを管理しており、注文番号snに基づいて注文情報を検索する必要があるとします。この時点での対応するハッシュインデックスは以下のようになります：
順序mと順序nは、計算されたmですが、それは問題ではない、チェーンテーブルが続く、あなたは順序_m最初に計算された順序_snがmとして計算されたクエリを実行する場合は、間隔の値を取るために、このケースは遅いです、あなたが1つずつトラバースする必要があります。だから、ハッシュテーブルは、等しい値のクエリのシナリオにのみ適しています。
順序付き配列は、等値クエリと範囲クエリの両方のシナリオで優れた性能を発揮しますが、順序を維持するコストは非常に高く、挿入と削除のたびに維持する必要があり、添え字を移動する必要があるため、順序付き配列インデックスは静的ストレージエンジンにしか適していません。クエリの効率だけを考えれば、順序配列は最高のデータ構造です。しかし、データを更新する必要がある場合、真ん中に行を挿入すると、その後ろにある行をすべて移動しなければならず、コストがかかりすぎるという問題があります。
Jump table , know that the chain table in each lookup need to traverse the table once, can you transform the chain table to improve the efficiency of the retrieval, you can use the idea of indexing the chain table to transform the chain table, part of the key extracted as a key node, if the retrieval efficiency is still too low, and then the key node of the key node of the key node of the key node of the key node of the key node of the key node of the key node of the key node of the key node of the key node of the key node of the key node.
バイナリ探索木は、バイナリ探索木として実装されたユーザーテーブルがある場合、次のようになります。
二分探索木の特徴は、各ノードの左の子は親ノードより小さく、親ノードは右の子より小さいことです。したがって、ID_card_n2を調べたい場合、図の検索順序に従えば、UserA -> UserC -> UserF -> User2の経路が得られます。この時間の複雑さはO(log(N))です。
検索プロセスを動画で表現するために、このツリーでの検索プロセスを次のように仮定します。
もちろん、クエリーの複雑さをO(log(N))に保つためには、ツリーをバランスの取れたバイナリーツリーにする必要があります。これを保証するためには、更新の複雑さもO(log(N))になります。バランスを保つというのは、連鎖したリストのようなツリーを避け、ツリーの両側にデータを分散させるということです。木には分岐と多分岐があります。多分岐木とは、各ノードが複数の子ノードを持ち、子ノード間のサイズが左から右に大きくなることが保証されている木です。二分木は検索に最も効率的ですが、実際にはほとんどのデータベース・ストレージは二分木を使いません。その理由は、インデックスがメモリ上にあるだけでなく、ディスクにも書き込まれるからです。100万個のノードを持ち、高さが20のバランスの取れたバイナリツリーを想像してみてください。*なぜ木の高さが1だとioが必要なのでしょうか？なぜなら、各ioはバイナリツリーに対して1つのノードのデータしか取り出せないからです。2つしか取り出せないのは、ポインタに従ってデータを取り出さなければならないからです。*ioのコストを削減するために木の高さダウンする必要がありますので、データベースは、Nプラグツリーを使用しています。ノードのデータは、このようにioの回数を減らす、N個のポインタが含まれている単一のioで検出されます。
InnoDBの インデックスモデル
InnoDBは、サーチツリーを改良したB+ツリーインデキシングモデルを使用しています。理解しやすくするために、モデルをバイナリツリーに単純化し、ツリーのノードはデータそのものを格納するのではなく、インデックスとして機能するだけです。これに加えて、各リーフノードは、データが小さいものから大きいものへと順番に並べられた連鎖テーブルに張られています。写真のような修正バイナリツリーは、ジャンプテーブルのように見えます。
変更後、区間のデータが必要な場合は、区間の開始値を取り、ツリーの中でそれを見つけるだけです。検索用のツリーで、間隔の開始値を取る必要があるだけで、リーフノードに検索し、チェーンテーブルに沿ってトラバースバック、チェーンテーブルのデータの値が値まで、間隔の終わりよりも大きいノードまで。トラバースされるデータはすべて、区間値と一致するデータです。しかし、データのレベルの数億の数百万でインデックスを構築する場合は、インデックスがメモリに配置されている場合、検索は非常に良いですが、それはまた、非常にメモリを消費するものですので、すべてのメモリにインデックスを作成することはできません、ハードドライブを置くioのパフォーマンスの問題が含まれ、前述のようにツリーの高さを減らすために、M -フォークに分岐、このMの値のどのくらい置くことが適切ですか？関係なく、メモリ上のデータ、またはディスク上のデータの、オペレーティングシステムは、ページ単位で読み取ることです、時間は、データのページを読み取ります。読み込むデータ量が1ページのサイズを超えると、複数のIO操作が発生します。そのため、mサイズを選択するときは、各ノードのサイズが1ページのサイズに等しくなるようにします。1つのノードを読み出すのに必要なディスクIO操作は1回だけです。B+ツリーの場合、m値はページのサイズに基づいて事前に計算されるため、各ノードは最大m個の子を持つことができます。このノードのサイズはページのサイズを超えるため、このようなノードを読み取ると、複数のディスクIO操作が発生します。mを超えるとリスト操作が実行され、核分裂後に親ノードもmを超えます。このカスケード反応はルート・ノードに下から上へと影響します。動画で見ると
B+の木の特徴：
各ノードの子ノードの数はm以上m/2以下であることはできません。
ルート・ノードはm/2以上の子を持つことはできませんが、これは例外です。
m-forkedツリーはインデックスだけを保存し、実際のデータは保存しません。
通常、ルート・ノードはメモリに格納され、他のノードはディスクに格納されます。
MySQLで「N-ツリー」のN値を手動で調整できますか？
(左前原理
B +ツリーインデックス構造は、レコードを検索するには、**"左端の接頭辞"のインデックスを使用することができます。名前の中にテーブルがあるとすると、年齢、ジョイントインデックスを確立するために、インデックスのスキーマは次のとおりです。
名前が "Zhang San "であるすべての人を見つけることが論理的な要件である場合、ID4を素早く見つけ、必要なすべての結果を得るために逆方向へたどることができます。 ファーストネームが "Zhang "であるすべての人を見つけたい場合、SQL文の条件は "where name like 'Zhang%'"となります。この時点で、インデックスを使用して、条件を満たす最初のレコードがID3であることを見つけ、条件が満たされなくなるまで逆行します。 このように、左端の接頭辞さえ満たせば検索を高速化できるのは、インデックスの完全な定義だけではありません。この一番左の接頭辞は、論理和インデックスの一番左のN個のフィールドでも、文字列インデックスの一番左のM個の文字でもかまいません。順序を調整することでインデックスを1つ少なく維持できるのであれば、 多くの場合、この順序を優先して使用する必要があります。
指数下方突き
Cityテーブルのユニオン・インデックスを例にとると、姓がZhangで年齢が10歳の男の子をすべてテーブルから取り出す必要がある場合。SQL文は以下のようになります。
select * from tuser where name like ' %' and age=10 and ismale=1;
MySQL 5.6 では、ID3 から 1 つずつテーブルに戻ることしかできません。主キーインデックスに移動してデータ行を見つけ、フィールドの値を比較することができました。MySQL 5.6で導入されたインデックスプッシュダウン最適化では、インデックスのトラバーサル処理中にインデックスに含まれるフィールドを最初に判断することで、条件に合わないレコードをフィルタリングし、テーブルに戻る回数を減らすことができます。インデックスのプッシュダウンがないケースは
5.6以降、インデックス式プッシュダウン付き
質問です：
CREATE TABLE `test` ( `a` int(11) NOT NULL, `b` int(11) NOT NULL, `c` int(11) NOT NULL, `d` int(11) NOT NULL, PRIMARY KEY (`a`,`b`), KEY `c` (`c`),
KEY `ca` (`c`,`a`),
KEY `cb` (`c`,`b`) ) ENGINE=InnoDB;
主キーにはaとbの2つのフィールドが含まれているので、フィールドcにインデックスを作成するだけで、すでに3つのフィールドが含まれていることになります。
C列の繰り返し率が非常に低い場合は、2つのインデックスを構築することはできません。なぜなら、もし数個のデータしか残っていないフィルタリングの場合、ソートは影響しませんが、C列の繰り返しが比較的高い場合は、ソートを排除するために、ジョイントインデックスを確立する必要があります。大量のデータの場合、ソートは非常に時間のかかる操作ですので、それはまた、ソートを行うには一時テーブルをディスクにする必要がある可能性が非常に高いです。と共同インデックスがない場合は、制限1は、単にクライアントのデータへの復帰は、スキャン行数を制限する役割を果たしていないことを意味し、インデックス上のca列の役割は、左端の接頭辞を満たすために、追加する必要はありません。cは固定値であるため、列が順序付けられます。その後、ここで制限1は非常にデータの1つだけの正確なスキャンの使用を制限するために良いです。だから、時には条件が悪い効率の場合には、この列のインデックスを制限することにより、順序でインデックスを構築する場合にも非常に良いプログラムです、並べ替え、バックテーブルでは、限り、条件として制限を満たすために行をフィルタリングすると、タイムリーにスキャンを停止することができます！
概要
- オーバーライド・インデックス：クエリ条件が一般的なインデックスを使用しており、クエリ結果がジョイント・インデックス・フィールドまたはプライマリ・キーである場合、結果はテーブルに戻ることなく直接返されるため、IOディスクの読み取り/書き込みが削減され、データの正の行の読み取り/書き込みが削減されます。
- 左端の接頭辞：論理和インデックスの左端Nフィールド、または文字列インデックスの左端M文字。
- ジョイント・インデックス：ジョイント・インデックスを作成する順序によると、年齢＝1または年齢＝1と名前＝'張三'はインデックスを使用することができ、単一の名前＝'張三'はインデックスを使用しません！頻繁に検索されるデータを検索するためにインデックスを使用したい場合は、ストレージ容量の問題を考慮し、ビジネス要件に応じてデータの左側にインデックスを作成する必要があります。
- インデックスは、プッシュダウン：'hello％'と年齢> 10のような取得、MySQLのバージョン5.6は、テーブルのクエリに戻って一致するデータになります。バージョン5.6の後、ge < 10のデータをフィルタリングされ、テーブルのクエリに戻って、検索速度を向上させるために、テーブルへの復帰率を減らすために
