data-structures - m-wayツリーの実用化

Question

データ構造の研究を再開しました。私はこれの実用的な使用法をほとんど見つけませんでした。それらの1つは、ディスク上のファイルシステムに関するものでした。誰かがm-wayツリーの実際の使用例をもっと教えてもらえますか？

Answer 1

M-wayの木はたくさんのアリーナに現れます。ここに小さなサンプルがあります：

1. Bツリー：これらは、巨大な分岐係数を持つ二分探索木のような探索木です。これらは、各ノードが1回のパスでハードディスクから読み取ることができるメモリのすぐ内側に収まるように設計されています。これらはすべて、通常のBSTと同じasymPtotic保証を備えていますが、特定の要素を見つけるために検索されるノードの数を最小限に抑えるように設計されています。その結果、多くの巨大なデータベースシステムは、Bツリーまたは他の関連する構造を使用して大きなテーブルをディスクに格納します。これにより、高価なディスク読み取りの数が最小限に抑えられ、全体的な効率が大幅に向上します。
2. 八分木。八分木とその2次元のいとこ四分木は、3次元空間に点を格納するためのデータ構造です。これらは、高速の衝突検出とリアルタイムのレンダリング計算のためにビデオゲームで広く使用されており、そうでない場合はさらに悪いことになります。
3. 木をリンク/カットします。これらの特殊なツリーは、ネットワークフローの問題で使用され、マッチングを効率的に計算したり、オペレーションズリサーチに非常に適用できる従来のアプローチよりもはるかに高速に最大フローを見つけたりします。
4. 素集合の森。これらのマルチウェイツリーは、最小スパニングツリーアルゴリズムで使用され、接続性を目がくらむほど高速に計算し、実行時間を理論上の限界付近に最適化します。
5. 試行します。これらのツリーは、文字列データをエンコードするために使用され、文字列のセットの非常に高速な検索、保存、および保守を可能にします。また、一部の正規表現マーチャーでも使用されます。
6. Van EmdeBoasTrees-巨大な分岐係数を持つ木の森に裏打ちされた整数の優先キューの超高速実装。
7. 接尾辞木。テキスト処理の世界のこれらの宝石は、高速の文字列検索を可能にします。また、通常、分岐係数は2よりはるかに大きくなります。
8. PQツリー。順列をエンコードするためのこれらのツリーは、回路レイアウトとグラフ描画に適用される線形時間平面性テストを可能にします。

ふぅ！それはたくさんの木です。お役に立てれば！

Answer 2

m-wayとは、一般化されたツリーを意味しますか？もしそうなら、ほとんどすべての「単一の親」階層。