MySQL インデックスの背後にあるデータ構造とアルゴリズムの基礎

インデックスの性質

MySQL のインデックスの公式定義は次のとおりです: インデックスは、MySQL がデータを効率的に取得するのに役立つデータ構造です。文の主幹を抽出することで、インデックスの本質、つまりインデックスがデータ構造であることがわかります。

次の SQL ステートメントのように、データベースクエリはデータベースの最も重要な機能の 1 つであることはわかっています。

my_table から * を選択 WHERE col2 = '77'

テーブル「my_table」から、「col2」が「77」のデータレコードを取得できます。

私たちは皆、できるだけ早くデータをクエリすることを望んでいるので、データベースシステムの設計者はクエリアルゴリズムの観点からそれを最適化します。最も基本的なクエリアルゴリズムは、もちろん線形検索です。これは、「my_table」をトラバースし、「col2」の値を行ごとに照合して、それが「77」であるかどうかを確認します。複雑度が O(n) のこのアルゴリズムは、データ量が多い場合には明らかに不適切です。幸いなことに、コンピューターサイエンスの発展により、バイナリ検索やバイナリツリー検索など、より優れた検索アルゴリズムが数多く提供されています。少し分析してみると、それぞれの検索アルゴリズムは特定のデータ構造にしか適用できないことがわかります。たとえば、バイナリ検索では、取得したデータが順序どおりになっていることが必要で、バイナリツリー検索はバイナリ検索ツリーにしか適用できません。ただし、データ自体の編成構造は、さまざまなデータ構造を完全に満たすことはできません (たとえば、2 つの列を同時に順序どおりに編成することは理論上不可能です)。そのため、データベースシステムは、データに加えて、特定の検索アルゴリズムを満たすデータ構造も保持しています。これらのデータ構造は、何らかの方法でデータを参照 (ポイント) するため、これらのデータ構造に対して高度な検索アルゴリズムを実装できます。このデータ構造はインデックスです。

例を見てみましょう:

図1

図 1 は、可能なインデックス作成アプローチを示しています。左側は 2 つの列と 7 つのレコードを持つデータテーブルです。左端はデータレコードの物理アドレスです (論理的に隣接するレコードが必ずしもディスク上で物理的に隣接するとは限らないことに注意してください)。 Col2 の検索を高速化するために、右に示すようにバイナリ検索ツリーを維持できます。各ノードには、インデックスキー値と、対応するデータレコードの物理アドレスへのポインターが含まれています。このようにして、バイナリ検索を使用して、O(log2n) の複雑さ内で対応するデータを取得できます。

これは本物のインデックスですが、実際のデータベースシステムでは、後述する理由により、バイナリ検索ツリーやその進化形である赤黒ツリーが使用されることはほとんどありません。

B ツリーと B+ ツリー

現在、ほとんどのデータベースシステムとファイルシステムでは、インデックス構造として B-Tree またはその派生形である B+Tree を使用しています。この記事の次のセクションでは、メモリの原理とコンピュータアクセスの原理を組み合わせて、B-Tree と B+Tree がインデックス作成に広く使用されている理由について説明します。このセクションでは、まずデータ構造の観点からのみ説明します。

Bツリー

B-Tree を説明するには、まずデータレコードをタプル [key, data] として定義します。ここで、key はレコードのキー値です。データレコードが異なれば、キーも異なります。データは、キーを除いたデータレコードのデータです。 B-Tree は次の条件を満たすデータ構造です。

d は 1 より大きい正の整数で、B ツリーの次数と呼ばれます。

h は正の整数で、B ツリーの高さと呼ばれます。

各非リーフノードは n-1 個のキーと n 個のポインターで構成されます (d<=n<=2d)。

各リーフノードには、少なくとも 1 つのキーと 2 つのポインターが含まれ、最大で 2d-1 個のキーと 2d ポインターが含まれます。リーフノードのポインターはすべて null です。

すべてのリーフノードは同じ深さを持ち、ツリーの高さ h に等しくなります。

キーとポインタは分離されており、ノードの両端にポインタが存在します。

ノード内のキーは、左から右へ非減少順に並べられます。

すべてのノードはツリー構造を形成します。

各ポインタは null であるか、別のノードを指します。

ポインタがノード node の左端にあり、null でない場合、それが指すノードのすべてのキーは v(key1) より小さくなります。ここで、v(key1) はノードの最初のキーの値です。

ポインタがノード node の右端にあり、null でない場合、それが指すノードのすべてのキーは v(keym) よりも大きくなります。ここで、v(keym) はノードの最後のキーの値です。

ノードへのポインタの左と右の隣接キーがそれぞれ keyi と keyi+1 であり、null でない場合、それが指すノードのすべてのキーは v(keyi+1) より小さく、v(keyi) より大きくなります。

図 2 は、d = 2 の B ツリーの概略図です。

図2

B ツリーの特性により、B ツリーでキーによってデータを取得するアルゴリズムは非常に直感的です。まず、ルートノードからバイナリ検索を実行します。キーが見つかった場合は、対応するノードのデータが返されます。それ以外の場合は、対応する間隔のポインターが指すノードが、ノードが見つかるか、ヌルポインターが見つかるまで再帰的に検索されます。前者は成功した検索であり、後者は失敗した検索です。 B-Tree 上の検索アルゴリズムの疑似コードは次のとおりです。

 BTree_Search(ノード、キー)
 {
 if(node == null )戻り値 ヌル;
 foreach(ノード.キー)
 {
 if( node.key [i] == key )はnode.data[i]を返します。
 if( node.key [i] > key ) return BTree_Search(point[i]->node);
 }
 BTree_Search(point[i+1]->node)を返します。
 }
データ = BTree_Search(ルート、my_key);

B ツリーには一連の興味深い特性があります。たとえば、次数 d の B ツリーが N 個のキーをインデックスする場合、そのツリーの高さ h の上限は logd((N+1)/2) です。キーのノード数を検索する漸近的な複雑さは O(logdN) です。この点から、B-Tree は非常に効率的なインデックスデータ構造であることがわかります。

さらに、新しいデータレコードを挿入したり削除したりすると、B ツリーの特性が破壊されるため、挿入や削除時に B ツリーの特性を維持するために、ツリーを分割、結合、転送するなどの操作を行う必要があります。この記事では、B ツリーのこれらの内容について完全に説明するつもりはありません。B ツリーの数学的特性や挿入および削除アルゴリズムを詳細に説明した資料がすでにたくさんあるためです。興味のある方は、この記事の最後にある参考資料を読んでください。

B+ツリー

B ツリーには多くのバリエーションがありますが、最も一般的なのは B+ ツリーです。たとえば、MySQL では通常、インデックス構造を実装するために B+ ツリーを使用します。

B-Tree と比較すると、B+Tree には次の違いがあります。

ノードあたりのポインターの数は、2d+1 ではなく 2d に制限されます。

内部ノードはデータを保存せず、キーのみを保存します。リーフノードはポインタを保存しません。

図 3 は単純な B+ツリー図です。

図3

すべてのノードが同じドメインを持つわけではないため、B+ ツリーのリーフノードと内部ノードは通常、サイズが異なります。これは B-Tree とは異なります。B-Tree では、異なるノードに格納されるキーとポインターの数が一致しない場合があります。ただし、各ノードのドメインと上限は一致しているため、実装では B-Tree が各ノードに同じ量のスペースを適用することがよくあります。

一般的に言えば、B+Tree は B-Tree よりも外部ストレージインデックス構造の実装に適しています。具体的な理由は、外部ストレージとコンピュータアクセスの原理に関連しており、これについては後述します。

シーケンシャルアクセスポインターを使用した B+ ツリー

データベースシステムやファイルシステムで一般的に使用される B+Tree 構造は、従来の B+Tree に基づいて最適化され、順次アクセスポインターが追加されています。

図4

図 4 に示すように、B+ ツリーの各リーフノードに隣接するリーフノードへのポインタを追加することで、順次アクセスポインタを持つ B+ ツリーが形成されます。この最適化の目的は、区間アクセスのパフォーマンスを向上させることです。たとえば、図 4 では、キーが 18 から 49 までのすべてのデータレコードをクエリする場合、18 を見つけた後は、ノードとポインターをトラバースするだけで、すべてのデータノードに一度にアクセスできるため、区間クエリの効率が大幅に向上します。

このセクションでは、B ツリーと B+ ツリーについて簡単に説明します。次のセクションでは、メモリアクセスの原則を組み合わせて、B+ ツリーが現在データベースシステムにインデックスを実装するための最適なデータ構造である理由を説明します。

#p#

B-Tree (B+Tree) を使用する理由

前述のように、赤黒木などのデータ構造を使用してインデックスを実装することもできますが、ファイルシステムとデータベースシステムでは、インデックス構造として B-/+ ツリーが一般的に使用されます。このセクションでは、インデックスとしての B-/+ ツリーの理論的根拠を、コンピュータ構成の原則に関する関連知識と組み合わせて説明します。

一般的に、インデックス自体も非常に大きく、すべてをメモリに格納することは不可能であるため、インデックスはインデックスファイルの形式でディスク上に保存されることがよくあります。この場合、インデックス検索処理中にディスク I/O 消費が発生します。メモリアクセスと比較すると、I/O アクセスの消費量は数桁大きくなります。したがって、インデックスとしてのデータ構造の品質を評価するための最も重要な指標は、検索処理中のディスク I/O 操作数の漸近的複雑さです。つまり、検索プロセス中のディスク I/O アクセスの数を最小限に抑えるようにインデックスの構造を構成する必要があります。以下では、まずメモリとディスクアクセスの原理を紹介し、次にこれらの原理を組み合わせてインデックスとしての B-/+ ツリーの効率を分析します。

メインメモリアクセスの原理

現在、コンピューターで使用されているメインメモリは、基本的にランダム読み取り書き込みメモリ (RAM) です。現代の RAM の構造とアクセス原理は比較的複雑です。ここでは、この記事では具体的な違いを無視し、非常に単純なアクセスモデルを抽象化して、RAM の動作原理を説明します。

図5

抽象的な観点から見ると、メインメモリは、それぞれが固定サイズのデータを格納する一連のストレージユニットで構成されるマトリックスです。各ストレージユニットには固有のアドレスがあります。現代のメインメモリのアドレス指定ルールは比較的複雑です。ここでは、これを 2 次元アドレスに簡略化します。つまり、ストレージユニットは、行アドレスと列アドレスを通じて一意に特定できます。図 5 は 4 x 4 メインメモリモデルを示しています。

メインメモリのアクセスプロセスは次のとおりです。

システムがメインメモリを読み取る必要がある場合、アドレス信号がアドレスバスに配置され、メインメモリにアップロードされます。メインメモリは、アドレス信号を読み取った後、信号を解析して指定されたストレージユニットを見つけ、このストレージユニットのデータをデータバスに配置して、他のコンポーネントが読み取れるようにします。

メインメモリへの書き込みプロセスも同様です。システムは、ユニットアドレスと書き込むデータをそれぞれアドレスバスとデータバスに配置します。メインメモリは 2 つのバスの内容を読み取り、対応する書き込み操作を実行します。

ここで、メインメモリへのアクセス時間はアクセス回数にのみ比例関係にあることがわかります。これは、機械的な操作がなく、2 回アクセスするデータ間の「距離」が時間に影響を与えないためです。たとえば、最初に A0 にアクセスしてから A1 にアクセスした場合の所要時間は、最初に A0 にアクセスしてから D3 にアクセスした場合の所要時間と同じです。

ディスクアクセスの原理

前述のように、インデックスは通常、ファイルの形式でディスクに保存され、インデックスの取得にはディスク I/O 操作が必要になります。メインメモリとは異なり、ディスク I/O には機械的な動きが伴うため、ディスク I/O にかかる時間は膨大になります。

図６はディスクの全体構造を示す概略図である。

図6

ディスクは同じサイズで同軸の円形プラッタで構成されており、ディスクは回転できます (個々のディスクは同期して回転する必要があります)。ディスクの片側にはヘッドブラケットがあり、ヘッドのグループを固定します。各ヘッドはディスクの内容にアクセスする役割を担います。磁気ヘッドは回転できませんが、ディスクの半径に沿って移動できます (実際には接線方向の移動)。各磁気ヘッドは同時に同軸である必要があります。つまり、真上から見下ろすと、すべての磁気ヘッドが常に重なり合っています (ただし、現在ではこの制限を受けないマルチヘッド独立技術があります)。

図７はディスク構造の概略図である。

図7

ディスクは一連の同心円に分割され、円の中心がディスクの中心になります。各同心円はトラックと呼ばれ、同じ半径のすべてのトラックが円筒を形成します。トラックは放射状の線に沿って小さなセグメントに分割されます。各セグメントはセクターと呼ばれます。各セクターはディスクの最小のストレージ単位です。簡単にするために、ディスクにはプラッタとヘッドが 1 つずつあると仮定します。

ディスクからデータを読み取る必要がある場合、システムはデータの論理アドレスをディスクに送信します。ディスクの制御回路は、アドレス指定ロジックに従って論理アドレスを物理アドレスに変換し、読み取るデータがどのトラックとセクターにあるかを判断します。このセクターのデータを読み取るには、ヘッドをこのセクターの上に配置する必要があります。これを実現するには、ヘッドを移動して対応するトラックに合わせる必要があります。このプロセスはシークと呼ばれ、かかる時間はシーク時間と呼ばれます。次に、ディスクが回転して、ヘッドの下のターゲットセクターを回転させます。このプロセスにかかる時間は回転時間と呼ばれます。

局所性原理とディスクの事前読み取り

ストレージメディアの特性上、ディスクアクセス自体はメインメモリよりはるかに遅くなります。機械的な動作消費に加え、ディスクアクセス速度はメインメモリの数百分の一になることがよくあります。したがって、効率を向上させるには、ディスクI/Oを最小限に抑える必要があります。この目標を達成するために、ディスクは厳密にオンデマンドで読み取られるのではなく、毎回事前に読み取られることがよくあります。必要なのが 1 バイトだけの場合でも、ディスクはこの位置から開始し、一定の長さのデータを順番に逆方向にメモリに読み込みます。この理論的根拠は、コンピュータサイエンスにおける有名な局所性原理です。

あるデータが使用されると、通常は近くのデータもすぐに使用されます。

プログラム実行中に必要なデータは通常集中しています。

ディスクの順次読み取りは非常に効率的であるため (シーク時間は必要なく、回転時間もわずかしか必要ありません)、事前読み取りによって局所性を持つプログラムの I/O 効率を向上させることができます。

事前読み取りの長さは、通常、ページの整数倍になります。ページは、コンピュータ管理メモリの論理ブロックです。ハードウェアとオペレーティングシステムは、多くの場合、メインメモリとディスクストレージ領域を同じサイズの連続ブロックに分割します。各ストレージブロックはページと呼ばれます (多くのオペレーティングシステムでは、ページサイズは通常 4k です)。メインメモリとディスクは、ページ単位でデータを交換します。プログラムが読み取ろうとするデータがメインメモリにない場合、ページフォールト例外が発生します。このとき、システムはディスクに読み取り信号を送信します。ディスクはデータの開始位置を見つけ、1つまたは複数のページを連続的に読み取り、メモリにロードします。その後、例外が返され、プログラムは引き続き実行されます。

B-/+ツリーインデックスのパフォーマンス分析

これで、ようやく B-/+ ツリーインデックスのパフォーマンスを分析できるようになりました。

前述のように、インデックス構造の品質を評価するには、通常、ディスク I/O の数が使用されます。まず、B ツリー分析から始めましょう。B ツリーの定義によれば、検索には最大 h 個のノードにアクセスする必要があります。データベースシステムの設計者は、ディスクの事前読み取り原理を巧みに利用して、ノードのサイズをページと同じサイズに設定し、各ノードを 1 回の I/O だけで完全にロードできるようにしました。この目標を達成するためには、B-Tree の実際の実装で次の技術が必要です。

新しいノードが作成されるたびに、ページのスペースが直接要求されます。これにより、ノードが物理的にページに格納されることが保証されます。さらに、コンピューターのストレージ割り当てはページ単位で行われるため、ノードに必要な I/O は 1 つだけです。

B ツリーでの検索には最大で h-1 回の I/O が必要であり (ルートノードは常にメモリ内に存在します)、漸近的な複雑度は O(h)=O(logdN) です。一般的な実際のアプリケーションでは、出次数 d は非常に大きな数値であり、通常は 100 を超えるため、h は非常に小さくなります (通常は 3 以下)。

まとめると、インデックス構造として B-Tree を使用することは非常に効率的です。

赤黒木構造の場合、h は明らかにはるかに深くなります。論理的に近いノード (親と子) は物理的に離れている場合があり、局所性を活用できないため、赤黒木の漸近的 I/O 複雑度も O(h) となり、その効率は明らかに B ツリーよりもはるかに悪くなります。

前述のように、B+Tree は外部メモリのインデックス作成に適していますが、その理由は内部ノードの出次数 d に関係しています。上記の分析から、d が大きいほどインデックスのパフォーマンスが向上し、出力次数の上限はノード内のキーとデータのサイズに依存することがわかります。

dmax = floor(ページサイズ / (キーサイズ + データサイズ + ポイントサイズ)) (ページサイズ – dmax >= ポイントサイズ)

または

dmax = floor(ページサイズ / (キーサイズ + データサイズ + ポイントサイズ)) - 1 (ページサイズ – dmax < ポイントサイズ)

切り捨てとは切り捨てを意味します。データフィールドは B+ ツリーのノードから削除されるため、出力次数が大きくなり、パフォーマンスが向上します。

この章では、理論的な観点から、インデックスに関連するデータ構造とアルゴリズムの問題について論じます。次の章では、MySQL で B+Tree がインデックスとしてどのように実装されるかについて説明します。同時に、MyISAM と InnDB ストレージエンジンを組み合わせて、非クラスター化インデックスとクラスター化インデックスという 2 つの異なるインデックス実装形式を紹介します。

オリジナルリンク: http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html

【編集者のおすすめ】