バイナリ検索がデータベースインデックス作成でどのように使用されるのですか

Question

バイナリ検索の仕組みはわかっていますが、バイナリ検索の実用的な使い方を知りたかったのです... インターネットで検索したところ、主な用途はデータベースのインデックス作成でしたバイナリ検索がデータベースの索引付けにどのように役立つか理解できませんでした。

Answer 1

ソートされたリストがある場合は、バイナリ検索を使用して効率的にリストを検索できます。データベースインデックスは、ソートされたデータのデータ構造です。

Answer 2

Binary searchを使用すると、キーがすでにソートされていることを前提に、そのキーでレコードをすばやく検索できます。これは、キーの数が多い場合に特に当てはまります。 32のキーの読み取りは、20億のソートされたキーのコレクション内の単一の一意のキーを見つけるには十分です。

バイナリ検索は、各検索の試行で検索するレコードの数が半減するため、この方法で動作します。言い換えれば、データベースは、通常、b-treesまたはred-black treesのような他のbinary treeのようなデータ構造を使用してインデックスを実行します。バイナリツリーを使用すると、検索する前にキーのリストをソートする必要がなくなります。

Answer 3

私が解決策を探している間、非常に便利なリンクとあなたの質問に対する答えが見つかりました。

Using Binary trees in Table Database indexes。

Answer 4

バイナリ検索では、各ステップの次の位置（中点）が計算されます。

DBのバイナリツリー事前計算各ステップ上の中点、単一の項目に達するまで。すべての中間点をツリーに配置します。クエリを実行すると、DBMSはツリーをルックアップします。