btreeインデックスの原理は何ですか

Btree インデックスの原理は、バイナリ ツリーの結果としてツリーの高さが非常に高くなるということです。論理的に非常に近いノードは物理的に非常に離れているため、局所性を利用できません。IO の数が多く、検索効率は低く、Btree はバランスの取れた「m ウェイ」検索ツリーであり、複数のブランチ ノードを使用してデータのクエリ時に発生するノードの数を減らすことができます。

#Bツリー インデックスの原則

バイナリ ツリーでは、ツリーの高さが非常に高く、ノードが論理的に近くなります。非常に遠く離れているため、局所性を利用できず、IO 時間が長く、検索効率が低いです。

Btree はバランスのとれた m-way 検索ツリーであり、複数のブランチ ノード (サブツリー ノード) を使用してクエリを削減できます。データが経験したノードの数を減らし、アクセス時間を節約します。 m は B-Tree の次数と呼ばれます。

B ツリーは 2-3 検索ツリーの拡張と見なすことができます。つまり、各ノードが M-1 個の子ノードを持つことができます。

特徴

• ルート ノードがあり、ルート ノードにレコードが 1 つと子が 2 つだけあるか、ルート ノードが空です。

• 各ノード レコードのキーとポインターは互いに離れており、ポインターは子ノードを指します。

• d は幅を表しますツリーの葉ノードを除き、その他の各ノードには [d/2,d-1] 個のレコードがあり、これらのレコード内のキーはサイズ順に左から右に配置され、[d/2 1,d] 個あります。 Children;

• ノードでは、n 番目のサブツリー内のすべてのキーが、このノードの n 番目のキーより小さく、n-1 番目のキーより大きいです;

• すべてのリーフ ノードは同じレベル、つまり同じ深さである必要があります。

##B ツリーの特性により、アルゴリズムB-Tree のキーによるデータの取得は非常に直感的です: まず、ルート ノードから二分探索が実行され、見つかった場合は、対応するノードのデータが返され、そうでない場合は、対応する区間のポインタが指すノードが返されます。ノードが見つかるか null ポインタが見つかるまで再帰的に検索され、前者の検索は成功し、後者の検索は失敗します。
推奨: 「

mysql チュートリアル

」

以上がbtreeインデックスの原理は何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。