Relaxed Radix Balanced Trees (RRB-trees) は不変ベクトル (Clojure と Scala で使用される) の一般化であり、インデックス作成と更新時間が「実質的に一定」です。RRB ツリーは、効率的なインデックス作成と更新を維持するだけでなく、効率的な連結 (log n) も可能にします。
著者は、私が理解するのが難しい方法でデータ構造を提示しています。各ノードが維持する不変条件が何であるかはよくわかりません。
セクション 2.5 で、アルゴリズムについて説明します。ノードへのインデックス付けには、基数検索後の線形検索の追加ステップのみが必要になることが保証されていると思います。彼らがどのようにして余分なステップの式を導出したのか理解できません。おそらく、それぞれの変数が何を意味するのか (特に「p 個のサブツリー ブランチの合計」) もわからないと思います。
RRB ツリー連結アルゴリズムはどのように機能しますか?
彼らはセクション 2.4 で不変条件について説明しています。「しかし、前述のように、B ツリー ノードは基数検索を容易にしません。代わりに、ノード サイズが と の間の範囲になるようにする初期不変条件を選択しましたm
。m - 1これは、well で始まるバランスの取れたツリーのファミリーを定義します。既知の 2 ～ 3 木、3 ～ 4 木、および (m=32 の場合) 31 ～ 32 木. この不変条件により、バランスが確保され、ほとんどの場合、基数分岐検索が実現されます. 場合によっては、基数検索の後に数ステップの線形検索が必要になります正しい分岐を見つけてください。必要な余分な手順は、レベルが高くなるほど増加します。」
彼らの式を見ると、サブツリーに格納できる値の最大数と最小数を計算しているように見えます。2 つの違いは、ポイントの下にある値の最大数と最小数の間の最大の違いです。これをスロットの下の値の数で割ると、検索しているインデックスが含まれているかどうかを確認するためにどのスロットを調べるかを決定するときに、オフになるスロットの最大数が得られます。