[解決済み] B-Treeとハッシュテーブルの比較

質問

MySQL では、インデックスタイプは b-tree であり、b-tree の要素へのアクセスは対数償却時間である。 O(log(n)) .

一方、ハッシュテーブルの要素にアクセスするのは O(1) .

データベース内のデータにアクセスするために、B-treeの代わりにハッシュテーブルを使用しないのはなぜですか？

どのように解決するのですか？

ハッシュテーブルでは、主キーによってのみ要素にアクセスすることができます。 これは、ツリーアルゴリズムを用いるよりも高速です ( O(1) の代わりに log(n) ) を選択することはできませんが、範囲指定 ( の間にあるもの全て x と y ). ツリーアルゴリズムでは、これを Log(n) 一方、ハッシュインデックスでは、フルテーブルスキャンになる可能性があるため O(n) . また、ハッシュインデックスの定数オーバーヘッドは通常より大きくなります ( はシータ表記では要因になりませんが、それでも存在します。 ). また、ツリー アルゴリズムは通常、メンテナンスが容易で、データと共に成長し、スケールアップすることができます。

ハッシュインデックスはあらかじめ定義されたハッシュサイズで動作するため、最終的にはオブジェクトが格納されるいくつかのバケットを持つことになります。これらのオブジェクトは、このパーティション内で本当に正しいものを見つけるために、再度ループされます。

そのため、サイズが小さいと小さな要素に対して多くのオーバーヘッドが発生し、サイズが大きいとさらなるスキャンが発生します。

現在のハッシュテーブルのアルゴリズムは通常スケールしますが、スケーリングが非効率になることがあります。

確かにスケーラブルなハッシュアルゴリズムは存在します。それがどのように機能するかは聞かないでください - 私にとっても謎です。AFAIKは、再ハッシュが容易でないスケーラブルなレプリケーションから発展したものです。

と呼ばれるものです。 RUSH - R エンプリケーション U 下 S キャラクタブル H のようなアルゴリズムがあり、これをRUSHアルゴリズムと呼んでいます。

しかし、インデックスがハッシュサイズと比較して許容できる大きさを超え、インデックス全体を再構築する必要がある場合があります。通常、これは問題ではありませんが、巨大な巨大なデータベースでは、これは何日もかかることがあります。

木アルゴリズムのトレードオフは小さく、ほとんどすべてのユースケースに適しているため、デフォルトで使用されています。

しかし、もしあなたが非常に正確なユースケースを持っていて、何が、そして何が必要とされるのかだけを正確に知っているならば、ハッシュインデックスを利用することができます。