B+treeとHashを比較したデータベースのインデックス作成

データベースが十分に大きい場合、インデックス作成はクエリを効率的に処理するための頼りになる手法であるとよく言われます。この投稿は、データベースインデックスとは何かを要約し、ハッシュとB+Treeを再検討するためのものです。

インデックスは、特定の種類の取得操作を最適化するためにレコードを編成するデータ構造です。テーブルのフィールドにインデックスを作成してから、search-keyの検索条件を満たすすべてのレコードを取得できます。 分野。インデックスがないと、クエリはテーブルのコンテンツ全体を線形にスキャンして、1つまたは少数のレコードのみをフェッチすることになります。

この投稿では、2つの一般的なインデックス作成手法のパフォーマンスとユースケースを要約します。ハッシュインデックス およびB+ツリー

ハッシュインデックス

この手法は、メインメモリにインデックスを作成するために広く使用されています。 本質的に高速検索だからです。平均的なO（1）操作の複雑さとO（n）ストレージの複雑さがあります。
多くの本では、人々はbucketという用語を使用します 1つ以上のレコードを保管するストレージの単位を示します
ハッシュに関しては、次の2つの点について話し合う必要があります。

• ハッシュ関数：検索キー（入力として）をバケット内のそのキーを表す整数にマップします。
• ハッシュスキーム：ハッシュ後のキーの衝突に対処する方法。

一部の人々は尋ねます：なぜ衝突？完璧なハッシュ関数は存在しますか？実際、キーが無限集合であるとしましょう。衝突がなければ、キーを32ビット整数のセットにマップすることは不可能です。計算と衝突率の間にはトレードオフがあるはずです。

言及する価値のあるハッシュスキームがいくつかあります。線形プロービング、連鎖ハッシュ、拡張可能ハッシュです。ルックアップ/挿入/削除アルゴリズムはハッシュスキームによって異なります。たとえば、連鎖ハッシュは、同じバケットに同じハッシュ値を持つ要素を配置することでキーの衝突を処理します。

長所

• ハッシュインデックスは、等式または主キーの検索に適しています。クエリは、ハッシュインデックスを利用して、償却されたO（1）ルックアップコストを取得できます。例：SELECT name, id FROM student WHERE id = '1315';

短所

ハッシュテーブルにはいくつかの制限があります：

• 範囲クエリは効率的ではありません。ハッシュテーブルは一様分布に基づいています。つまり、インデックスエントリを配置する場所を制御することはできません。
• スケーラビリティが低い：衝突が多い場合、ルックアップ操作のパフォーマンスが低下する可能性があり、ハッシュテーブルのサイズを変更してから、既存のインデックスエントリを再ハッシュする必要があります。

B+ツリー

これは、データをソートされた順序で保持し、通常はバイナリ検索を使用して各ノード内で高速検索を可能にする自己バランス型ツリーデータ構造です。
B + Treeは、ほとんどすべてのリレーショナルデータベースシステムでの標準的なインデックス実装です。

B + Treeは、基本的に次の構造を持つM-way検索ツリーです。

• 完全なバランス：葉のノードは常に同じ高さです。
• ルート以外のすべての内部ノードが少なくとも半分いっぱいになっています（M / 2 −1<=キーの数<=M− 1）。
• k個のキーを持つすべての内部ノードにはk+1個のnull以外の子があります。

ツリーのすべてのノードには、ソートされたキーと値のペアの配列があります。キーと値のペアは、ルートノードと内部ノードの（検索キー値、ポインター）から構築されます。リーフノードの値は2つの可能性があります：

• 実際の記録
• 実際のレコードへのポインタ

値を検索するv

• ルートノードから開始
• ノードはリーフノードではありませんが、次のようにします。
  • Ki> =v
  である最小のKiを見つけます
  • Ki ==vの場合：現在のノードをPi+1が指すノードに設定します
  • それ以外の場合は、現在のノードをPiが指すノードに設定します

重複キー

一般に、検索キーは複製できます。これを解決するために、ほとんどのデータベース実装は複合検索キーを考え出します。たとえば、student_nameにインデックスを作成したいとします。 その場合、複合検索キーは（student_name、Ap）になります。ここで、Apはテーブルの主キーです。

長所

B +treeが提供する2つの主要な機能があります：

• I/O操作の最小化
  • 高さの減少：B + Treeの分岐係数は非常に大きく（50〜2000の値がよく使用されます）、ツリーが太く短くなります。次の図は、高さが2のB +ツリーを示しています。ノードが広がっていることがわかるように、リーフまでトラバースするのに必要なノードは少なくなります。単一の値を検索するコストは、ツリーの高さ+1テーブルへのランダムアクセスの場合です。
• スケーラビリティ：
  • すべてのケース、特にO（log（n））に対して予測可能なパフォーマンスがあります。データベースの場合、通常、最良または平均的なケースのパフォーマンスを向上させるよりも重要です。
  • ツリーは、その実装によって常にバランスが保たれます。 n個のキーを持つB+ツリーの深さは常にO（log（n））です。したがって、データベースが大きくなってもパフォーマンスが低下することはありません。ページのサイズが4KBの場合、分岐係数が500の4レベルツリーは最大256TBを格納できます。

• B + Treeは、範囲クエリに最適です。たとえば、"SELECT * FROM student WHERE age > 20 AND age < 22"

結論

ハッシュインデックスは完全一致クエリの点で優れていますが、B + Treeは、全体的なパフォーマンスと高いスケーラビリティの一貫性により、RDBMSで最も広く使用されているインデックス構造です。

最近、ログ構造のマージツリー（LSMツリー）は、そのデータ構造によってストレージスペースの使用効率が向上する可能性があるため、B+ツリーの候補として大きな関心を集めています。さらに調査し、近いうちに投稿します。