2

2-3-4 ツリーの 1 つのノードは、8 つのポインターで構築できます。最大 4 つの子ノードへのポインター、検索キーに一致するキー、または 4 つの子ノードのどれを決定するかを決定するキーを含む最大 3 つの実際のレコードへのポインター再帰先、および親ノード ポインター。

今日の一般的なハードウェアには 8 バイトのポインターがあり、64 バイトのノードを提供します。さらに、最新の CPU には 64 バイトのキャッシュ ラインがあります。ノードがキャッシュ ラインと整列している場合、各ノードは 1 つのキャッシュ ライン ヒットのみを必要とします。7 つのポインターのうち最初のポインターを参照した後、残りはすべて L1 キャッシュに格納されます。

赤黒ツリーは実装がはるかに簡単で、小さなコードは高速なコードである必要がありますが、ツリーの降下の各レベルでは L1 キャッシュ ミスのリスクがあります。1023 個のオブジェクトの場合、2-3-4 ツリーでは、キャッシュにロードする最悪のケースで 5 つのノードが必要です。完全にバランスの取れたバイナリ ツリーには 10 が必要ですが、バランスが崩れているため、赤黒ではさらに必要になる場合があります (最悪の場合: 20?)

1 つのデータ構造を単純に叩く小さなテスト ハーネスは、おそらくすべてをキャッシュに保持するため、赤黒ツリーが 2-3-4 と同様のパフォーマンスであると報告される可能性があります。しかし、複雑な実世界のアプリケーションでは、2-3-4 ツリーを使用すると実時間と待ち時間が大幅に短縮される可能性があると感じています。

これに関するコンセンサスや研究はありますか？

4

1 に答える 1

0

あなたの推論は確かに正しいです。コールド ルックアップの場合、ヒットするキャッシュ ラインが少ないという理由だけで、2-3-4 ツリーのパフォーマンスが向上します。

ただし、ツリーのパフォーマンスが重要な場合は、通常、ツリーを頻繁に使用していることを意味します。

ツリーが頻繁に使用されていて、ほとんどすべてがキャッシュにあるわけではない場合、ツリーは大きくなければなりません。大きなツリーが頻繁に使用される場合、通常は上位レベルのノードがキャッシュされます。これは、各レベルが平均して下位レベルの 2 倍の頻度でヒットされるためです。

したがって、重要な場合の実際のパフォーマンスの向上は、ツリーの最も深いいくつかのレベルに限定されます。2-3-4 ツリーでもパフォーマンスを確認できますが、それは暴走ではありません。コードの複雑さが増す価値があると判断するには、特別な理由が必要だと思います (特に検索と反復において)。

于 2019-06-01T12:56:29.777 に答える