Bヒープ

Bヒープは、サブツリーを単一ページに格納するように実装されたバイナリヒープです。これにより、従来の実装と比較して、仮想メモリを使用する場合、大きなヒープではアクセスされるページ数が最大10分の1に削減されます。 [1]従来の配列内の位置への要素のマッピングでは、ほぼすべてのレベルが異なるページに格納されます。

仮想記憶やキャッシュを使用するコンピュータで効率的なヒープのバリエーションとしては、キャッシュ忘却アルゴリズム、kヒープ[2]、ファン・エムデ・ボアズ・レイアウト[3]などがあります。

モチベーション

伝統的に、バイナリ ツリーは規則に従って連続するメモリ内に配置されますn -> {2n, 2n+1}。つまり、ノードが位置 にある場合n、その左右の子は配列内の位置 と にあると見なされます2n。2n+1ルートの位置は 1 です。バイナリ ツリーに対する一般的な操作は垂直方向のトラバーサルです。これは、検索したノードに到達するために、ツリーのレベルを下っていきます。ただし、最近のコンピュータではメモリが仮想メモリ内のページに編成される方法が原因で、バイナリ ツリーをレイアウトするこのスキームは非常に非効率的になる可能性があります。その理由は、ツリーのより深くまでトラバースする場合、次のノードまでの距離が指数関数的に増加するため、取得される次のノードはすべて別のメモリ ページ上にある可能性が高くなるためです。これにより、非常にコストのかかるページ ミスの数が増えます。B ヒープは、メモリ内の子ノードを別の方法でレイアウトし、可能な限りサブツリーを 1 ページ内に配置することでこの問題を解決します。したがって、垂直方向のトラバーサルが進むにつれて、連続して取得されたノードのいくつかが同じページに配置され、ページミスの数が少なくなります。

実装

詳細には、bヒープは以下のように実装できます。Poul-Henning Kamp [4]は、ノードのレイアウトについて2つの選択肢を提示しています。1つはページごとに2つの位置を無駄にするものの、ツリーの厳密なバイナリ構造は維持されるもので、もう1つはページの利用可能なスペース全体を使用するものの、新しいページに入る際にツリーが1レベル拡張されない（そのレベルのノードには子が1つだけ存在する）ものです。いずれにせよ、重要な点は、あるページを離れる際に、両方の子ノードが常に共通の別のページにあることです。これは、垂直方向のトラバーサルにおいて、アルゴリズムは通常、処理方法を判断するために両方の子ノードを親ノードと比較するためです。このため、各ページには2つの並列サブツリーが点在していると言えます。ページ自体はm進木と見なすことができ、各ページの要素の半分は（ページ内で）葉となるため、「ページのツリー」の分割係数は となりますpagesize/2。

親関数

従来の配列のようなレイアウトとは対照的に、Bヒープにおける親関数はより複雑です。これは、ノードの親のインデックスを、ページ内の位置に応じて異なる方法で計算する必要があるためです。ページ内の位置が0から​​ までラベル付けされていると仮定するとpagesize、親関数は次のようになります。

ノード 0 と 1 については、これらはすべての可能なスペースを活用するバリアントでのみ使用されます。この場合、両方のノードの親インデックスは同じで、別のページにあり、そのページ内の特定のオフセットは現在のページ番号のみによって決まります。具体的には、親のページ番号を計算するには、現在のノードのページ番号を「ページ ツリー」の分割係数 で割るだけですpagesize/2。ページ内の正しいオフセットを取得するには、親ページ内のリーフ ノードの 1 つである必要があることを考慮して、オフセット から開始しますpagesize/2。次に、現在のページ番号と親のページ番号の差から 1 を減算します。これは、親ページの後の最初のページがインデックス ( pagesize/2) に親ノードを持つためです。

ノード2と3については、モードによって親が異なります。省スペースモードでは、親はそれぞれノード0と1であるため、2を減算するだけで済みます。一方、厳密な二分木モードでは、これらのノードは0と1ではなくページのルートであるため、共通の親は上記と同じ方法で計算されます。

他のすべてのノードについては、親は同じページ内にあるため、ページ番号を変更せずに、ページ内のオフセットを 2 で割るだけで十分です。

参照

参考文献

  1. ^ Kamp, Poul-Henning (2020年7月26日). 「You're Doing It Wrong.」ACM Queue .
  2. ^ Naor, Dalit; Martel, Charles U.; Matloff, Norman S. (1991). 「仮想メモリ環境における優先キュー構造の性能」. Comput. J. 34 (5): 428– 437. doi :10.1093/comjnl/34.5.428.
  3. ^ van Emde Boas, P. ; Kaas, R.; Zijlstra, E. (1976). 「効率的な優先キューの設計と実装」.数理システム理論. 10 : 99–127 . doi :10.1007/BF01683268. S2CID  8105468.
  4. ^ Kamp, Poul-Henning. 「You're Doing It Wrong」. phk.freebsd.dk . 2019年6月8日閲覧。
  • 実装は https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c および http://phk.freebsd.dk/B-Heap/binheap.c にあります。
  • B ヒープをサポートする汎用ヒープ実装。
  • van Emde Boas レイアウトの詳細については、Benjamin Sach の「Descent into Cache-Oblivion」または「Cache-oblivious data structures」を参照してください。
「https://en.wikipedia.org/w/index.php?title=B-heap&oldid=1272231103」から取得