^{ノーチラスの舵をとるニモ船長}

インデックスは、リレーショナルデータベースで最も強力なツールの1つです。 いくつかの値をすばやく見つける必要がある場合、データベースを結合する場合、SQLステートメントの作業を高速化する必要がある場合などに使用します。 しかし、インデックスとは何ですか？ また、データベース検索の高速化にどのように役立ちますか？ これらの質問に答えるために、PostgreSQLのソースコードを調査し、単純な文字列値のインデックスの検索方法を追跡しました。 複雑なアルゴリズムと効率的なデータ構造を見つけることが期待されていました。 そして見つけた。

ここでは、インデックスがどのように配置され、どのように機能するかについて説明します。 ただし、コンピューターサイエンスに基づいているとは思っていませんでした。 インデックスの内外を理解することは、Postgresがどのように機能するかだけでなく、なぜそのように機能するかを説明するコード内のコメントによっても助けられました。

配列検索

Postgresのシーケンス検索アルゴリズムには奇妙な点があります。何らかの理由で、テーブル内のすべての値を調べます。 前回の投稿では、次の簡単なSQLステートメントを使用して、「Captain Nemo」の値を検索しました。



Postgresはリクエストをスパース、分析、および計画しました。 次に、 ExecSeqScan （SEQSCANシーケンス検索を実装する組み込みC言語関数）がすぐに目的の値を見つけました。



しかし、その後、説明されていない理由で、Postgresはデータベース全体をスキャンし続け、各値を検索と比較しましたが、すでに見つかっています！



テーブルに何百万もの値が含まれている場合、検索には非常に長い時間がかかります。 もちろん、これは、ソートを削除し、最初に見つかった一致で停止するようにクエリを書き換えることで回避できます。 しかし、問題はより深く、Postgres自体の検索エンジンの非効率性にあります。 シーケンス検索を使用してテーブル内の各値を比較するのは遅く、非効率的であり、レコードが配置される順序に依存します。 別の方法が必要です！

解決策は簡単です。インデックスを作成する必要があります。

インデックス作成

これを行うには簡単です。コマンドを実行するだけです：


Ruby開発者は、同じCREATE INDEXコマンドを実行するActiveRecordでadd_index移行を使用することを好みます。 通常、selectを再起動すると、Postgresはプランニングツリーを作成します。 ただし、この場合は少し異なります。



下部では、SEQSCANの代わりにINDEXSCANを使用していることに注意してください。 INDEXSCANは、SEQSCANとは異なり、データベース全体をスキャンしません。 代わりに、作成したばかりのインデックスを使用して、必要なレコードをすばやく効率的に検索します。

インデックスを作成すると、パフォーマンスの問題は解決しますが、次のような多くの質問に対する答えは得られません。

• Postgresのインデックスとは正確には何ですか？
• 正確にはどのように見えますか、その構造は何ですか？
• インデックスはどのように検索を高速化しますか？

Cのソースを見て、これらの質問に答えましょう。

Postgresのインデックスとは

CREATE INDEXコマンドのドキュメントから始めましょう：



インデックスの作成に使用できるすべてのパラメーターがここに表示されます。 USINGメソッドパラメータに注意してください。これは、必要なインデックスの種類を示します。 同じページには、メソッド、USINGキーワード引数に関する情報が記載されています。



Postgresには4種類のインデックスがあります。 これらは、さまざまなタイプのデータに、または状況に応じて使用できます。 USINGパラメータを定義しなかったため、index_users_on_nameはデフォルトで「btree」（Bツリー）の形式のインデックスです。

Bツリーとは何ですか。それに関する情報はどこで入手できますか？ これを行うには、対応するPostgresソースファイルを調べます。



READMEの説明は次のとおりです。



ところで、README自体は12ページのドキュメントです。 つまり、Cコードの有用なコメントだけでなく、データベースサーバーの理論と特定の実装に関するすべての必要な情報も利用できます。 多くの場合、オープンソースプロジェクトのコードの読み取りと解析は困難な作業ですが、Postgresでは困難です。 開発者は、彼らの発案の設計を理解するプロセスを促進しようとしました。

最初の文には、Bツリーが何であるか（したがって、Postgresでのインデックスの仕組み）を説明する科学出版物へのリンクがあることに注意してください。とヤオ。

Bツリーとは何ですか？

この記事では、作者が1981年にBツリーアルゴリズムに加えた改善について説明しています。 これについては後ほど説明します。 アルゴリズム自体は1972年に開発されました。これは単純なBツリーの例です。



名前は英語の略です。 「バランスの取れた木」。 このアルゴリズムにより、検索操作を高速化できます。 たとえば、値53を見つける必要があります。値40を含むルートノードから始めましょう。



目的の値と比較されます。 53> 40なので、ツリーの右のブランチに従います。 また、たとえば値29を探している場合、29 <40であるため、左の分岐に沿って進みます。右の分岐に続いて、2つの値を含む子ノードに到達します。



今回は、53を値47および62と比較します。47<53 <62。ノード内の値がソートされていることに注意してください。 目的の値は1より小さく、他の値よりも大きいため、中央の分岐をたどって、3つの値を含む子ノードに入ります。



ソートされた値のリスト（51 <53 <56）と比較し、4つのブランチのうち2番目のブランチに沿って進み、最終的に目的の値を持つ子ノードに到達します。



このアルゴリズムが検索を高速化するため：

1. 各ノード内の値（キー）がソートされます。
2. アルゴリズムのバランスが取れています。キーはノード全体に均等に分散され、遷移の数が最小限に抑えられます。 各ブランチは、他のすべての子ノードとほぼ同じ数のキーを含む子ノードにつながります。

Postgresでのインデックスの外観

リーマンとヤオは30年以上前に図を描いたが、現代のPostgresとは何の関係があるのか​​？ 作成したindex_users_on_nameは、この図に非常に似ていることがわかります。 CREATE INDEXコマンドが実行されると、Postgresはユーザーテーブルのすべての値をBツリーツリーのキーとして保存します。 これは、インデックスノードの外観です。



インデックスの各エントリは、IndexTupleDataと呼ばれるCの構造で構成され、値とビットマップも含みます。 後者はスペースを節約するために使用され、キーのインデックスの属性がNULLであるかどうかに関する情報が書き込まれます。 値自体は、インデックス内のビットマップに従います。

IndexTupleData構造は次のようになります。



t_tid ：これは、データベース内の他のインデックスまたはレコードへのポインターです。 これは、Cからの物理メモリへのポインタではないことに注意してください。Postgresがメモリの一致するページを検索するためのデータが含まれています。

t_info ：これには、インデックスアイテムに関する情報が含まれます。 たとえば、何個の値が格納されているか、それらがNULLであるかなど。

理解を深めるために、 index_users_on_nameのいくつかのエントリを検討してください 。



ここでは、値の代わりに、データベースからいくつかの名前が挿入されます。 最上位ツリーノードには、キー「Dr. Edna Kunde”と” Julius Powlowski”、そして最下位ノードは” Julius Powlowski”と” Juston Quitzon”です。 リーマンおよびヤオ図とは異なり、Postgresは各子ノードで親キーを繰り返します。 たとえば、「Julius Powlowski」は最上位ツリーと子ノードのキーです。 t_tidポインターは、上位ノードのJuliusを下位ノードの同じ名前に参照します。 キー値をBツリーノードに保存する方法を詳しく調べたい場合は、itup.hファイルを参照してください。

値を含むBツリーノードを検索する

元のSELECTステートメントに戻ります。

Postgresはindex_users_on_nameで「Captain Nemo」をどのくらい正確に検索しますか？ 検索を比較するよりも高速にインデックスを使用するのはなぜですか？ インデックスに保存されている名前のいくつかを見てみましょう。



これは、index_users_on_nameのルートノードです。 名前が全体に合うようにツリーを展開しました。 4つの名前と1つのNULL値があります。 インデックス自体が作成されるとすぐに、Postgresはこのルートノードを自動的に作成しました。 インデックスの先頭を示すNULLを除き、他の4つの名前はアルファベット順になっていることに注意してください。

覚えているように、Bツリーはバランスの取れたツリーです。 したがって、この例では、ツリーには5つの子ノードがあります。

• 「Dr. エドナ・クンデ”
• 「Dr. エドナ・クンデ”と”ジュリアス・ポウロウスキー”
• 「Julius Powlowski」と「Monte Nicolas」の間の名前
  ...など

「Captain Nemo」を探しているため、Postgresは右の最初のブランチに沿って進みます（アルファベット順のソートでは、望ましい値は「Dr. Edna Kunde」になります）。



図からわかるように、Postgresは目的の値を持つノードを見つけます。 テストのために、テーブルに1000個の名前を追加しました。 この右の結び目には240個が含まれていました。 したがって、残りの760個の値が船外に残されたため、ツリーは検索プロセスを大幅に加速しました。

Bツリーで目的のノードを見つけるためのアルゴリズムについて詳しく知りたい場合は、_bt_search関数のコメントを参照してください。

ノード内の値を検索します

そのため、Postgresは240個の名前を含むノードに移動しましたが、その中で値「Captain Nemo」を見つける必要がありました。



このために、シーケンス検索ではなく、バイナリ検索アルゴリズムが使用されます。 最初に、システムはリストの中央（位置50％）にあるキーを比較します。



希望の値は「Breana Witting」の後にアルファベット順に続くため、Postgresは75％（リストの4分の3）にあるキーにジャンプします。



今回、私たちの価値はもっと高くなければなりません。 その後、Postgresはある値を高くジャンプします。 私の場合、目的の値が最終的に見つかるまで、システムはノード内のキーのリストを8回ジャンプする必要がありました。



_bt_binsrch関数のコメントで、ノード内の値の検索アルゴリズムについて詳しく読むことができます。

その他の興味深いこと

ご希望の場合、Bツリーに関する理論の一部は、科学論文「 Bツリーでの同時操作の効率的なロック」から収集できます。

Bツリーにキーを追加します 。 ツリーに新しいキーを追加する手順は、非常に興味深いアルゴリズムに従って実行されます。 通常、キーは、受け入れられたソートに従ってノードに書き込まれます。 しかし、ノードに空きスペースがなくなったらどうしますか？ この場合、Postgresはノードを2つの小さなノードに分割し、そのうちの1つにキーを挿入します。 また、「スプリットポイント」からのキーと新しい子ノードへのポインターを親ノードに追加します。 もちろん、このキーを挿入するために親ノードも分割する必要があります;その結果、1つのキーをツリーに追加する手順は複雑な再帰操作に変わります。

Bツリーからキーを削除します 。 また、非常に奇妙な手順。 Postgresノードからキーを削除する場合、可能であれば、子ノードを結合します。 再帰的な操作も可能です。

Bリンクツリーツリー 実際、リーマンとヤオの研究は、単一のツリーが複数のスレッドで使用されている場合に、並列性とブロッキングに関連して考案された革新を説明しています。 Postgresコードとそのアルゴリズムは、複数のクライアントが同時にアクセス（または変更）できるため、マルチスレッドをサポートする必要があります。 各ノードから次の子ノード（「右矢印」）にポインターを追加すると、一方のスレッドがツリーを検索でき、もう一方のスレッドはインデックス全体をブロックせずにノードを共有できます。

探検することを恐れないでください

おそらく、あなたはPostgresの使い方に関するすべてを知っていますが、それが内部にどのように配置されているか、「内部」にあるものを知っていますか？ コンピューターサイエンスの研究は、現在のプロジェクトに取り組んでいるだけでなく、単なる娯楽ではなく、開発者の開発プロセスの一部です。 年々、当社のソフトウェアツールはより複雑で、多面的で、より優れたものになり、サイトやアプリケーションを簡単に作成できるようになりました。 しかし、このすべての基礎がコンピューターサイエンスの科学であることを忘れてはなりません。 Postgresのオープンソース開発者コミュニティ全体と同様に、LehmanやYaoなどの前任者の肩に立っています。 したがって、日常的に使用するツールを盲目的に信頼せず、デバイスを調べてください。 これは、あなたがより高い専門的レベルを達成するのを助けます。あなたは、あなたが以前は気づかなかった情報と解決策を自分で見つけることができます。