Clever Geek Handbook

.Net条件でネストされたセットを増やす





こんにちは、私の名前はアントンです。私は開発者です。私が出産した息子、建てられた家は買いました、それは木を育てるために残っています。私はあまり農学者ではないので、木をコーディングしなければなりませんでした。私たちのプロジェクトは、.Net Core上のいくつかのマイクロサービスで構成されており、階層関係を形成するエンティティはPostgreSQLデータベースに保存されます。そのようなデータを保存するためにどの構造を選択するのが良いか、なぜ正確にネストされたセットであるか、どのレーキを踏むことができるか、そして後でそれをどのように使用するかを説明します。



ネストされたセットとは



庭で木がどのように成長するかは誰もが知っています。ネストされたセットの場合、木は次のように成長します。ノードごとに、LeftとRightの2つのフィールドが格納され、それらは整数です。ここでの論理は、左が右よりも小さいことであり、ノードに子がある場合、子ノードのすべての左と右の値は、親の対応する値の間にある必要があります。





彼らが私たちと一緒に成長する方法



階層を保存するための個別のマイクロサービスを用意しています。Frontedは、詳細ビューで要素のサブツリーだけでなく完全なツリーも描画する必要があることがよくありますが、要素の挿入と移動は比較的まれです。このような場合、ネストされたセットは最適です。次のようなテーブルに保存されます。





Idは、対応するエンティティのIDであり、これを使用して、適切なマイクロサービスから完全な情報を取得できます。TreeIdは、ルート要素の識別子です。プロジェクトの樹木はほとんどが小さいですが、たくさんあります。EntityFrameworkはデータベースからの読み取りに使用され、クラスはテーブル構造に1対1で対応します。



読み方



このストレージ方法を使用すると、サブツリーの要素を取得するのは簡単です。左が親の左より大きく、右がそれぞれ小さいすべてのノードを要求します。また、TreeId列によって、すべてのノードが同じツリーに属していることを確認します。これは最も頻繁に必要な操作であり、迅速に実行されます。たとえば、次のようになります。 



dataContext.Nodes.Where(_ => 
                        _.Left > node.Left && 
                        _.Right < node.Right && 
                        _.TreeId == node.TreeId);


もう1つの頻繁に実行される操作は、オブジェクトのすべての親ノードを見つけることです。ここでも、難しいことではありません。Leftが親要素のLeftよりも小さく、Rightがそれぞれ大きいツリーノードを要求します。たとえば、次のようになります。 



dataContext.Nodes.Where(_ => 
                        _.Left < node.Left && 
                        _.Right > node.Right && 
                        _.TreeId == node.TreeId);


新しい枝を育てる方法



難しい部分に移りましょう-移植、つまり ノードを追加するか、あるサブツリーから別のサブツリーに移動します。転送する方法を考えてみましょう。この操作には、基本的に、子要素を追加するために必要なすべてのものが含まれます。



挿入を成功させるために最初に行うことは、挿入または更新操作を1つだけ許可することです。これを行うには、ブロッキングを使用します。ノードは1つのツリー内でしかナビゲートできないため、テーブル全体をロックすることは意味がありません。したがって、このツリーのみをロックするだけで十分です。これを行うには、次のSQLクエリを実行します。 



select * from "Nodes" where "TreeId" = <TreeId> for update;


これにより、ツリーの要素をすぐに読み取ることができますが、そのような操作がすでに開始されているツリーでノードを追加または変更する必要がある場合は、前の操作が完了するのを待つ必要があります。



次のステップは、移植のための場所を準備することです-左と右の間にギャップを作成します。必要なスペースの量を計算してみましょう。これは、移動するサブツリーのルート要素の右と左の差です。この違いを、新しい親になるノードのすべての子に追加しましょう。ここで例外をキャッチできます。その理由は次のとおりです。テーブルでの検索と読み取りを高速化するために、LeftフィールドとRightフィールドに2つのB-Treeインデックスが追加されました。これらのフィールドの値を同時に変更すると、EntityFrameworkは循環依存エラーを生成する可能性があります。 2つのインデックスを1行で同時に再計算できます。エラーのタイプはInvalidOperationExceptionで、次のメッセージが表示されます。



保存するデータで循環依存関係が検出されたため、変更を保存できません： 'ノード[変更済み] <-インデックス{'右 '、'ツリーID '}ノード[変更済み] <-インデックス{'左 '、'ツリーID '}ノード[変更済み] '。


回避するために、2つの別々のループを作成します。1つは左に、もう1つは右に変更します。もちろん、それぞれの後に変更を保存します。 




            var nodesToMove = await dataContext.Nodes 
                .Where(n => 
                    n.Right >= parentNodeRight && 
                    n.TreeId == parentNode.TreeId) 
                .OrderByDescending(n => n.Right) 
                .ToListAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Left += distance; 
            } 
 
            await dataContext.SaveChangesAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Right += distance; 
            } 
 
            await dataContext.SaveChangesAsync();


さらに、移植自体-転送距離は、新しい親の左側とサブツリーのルートの左側の差に等しくなります。移動するサブツリー内のすべてのノードの左右にこの値を追加します。 




            var nodes = await dataContext.Nodes 
                .Where(n => 
                    n.Left >= node.Left && 
                    n.Right <= node.Right && 
                    n.TreeId == node.TreeId) 
                .ToListAsync(); 
 
            foreach (var n in nodes) 
            { 
                n.Left += distance; 
                n.Right += distance;


そして最後にすべきことは、サブツリーが移動されたギャップを埋めることです。このサブツリーの右側にあるすべてのノードをリクエストしましょう。これらは、右側がサブツリーのルートの左側以上の要素になり、それらを空きスペースに移動します。これを行うには、これらすべてのノードの左と右から、ルートの右と左の差を差し引きます。ここでも、2つの別々のループを実行する必要があります。 




            var nodesToMove = await dataContext.Nodes 
              .Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId) 
              .ToListAsync(); 
            nodesToMove = nodesToMove 
                .Where(n => n.Right >= gap.Right) 
                .OrderBy(n => n.Right) 
                .ToList(); 
 
            foreach (var n in nodesToMove) 
            { 
                if (n.Left >= gap.Right) 
                { 
                    n.Left -= distance; 
                } 
            } 
 
            await dataContext.SaveChangesAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Right -= distance; 
            } 
 
            await dataContext.SaveChangesAsync();


結論



何が成長したか見てみましょう。子供と親をすばやく読むことができる木を手に入れました。プロジェクトで頻繁にデータを読み取り、サブツリーを取得する必要がある場合は、ネストされたセットが最適です。挿入および更新操作で問題が発生する可能性があるという事実に備える必要がありますが、それらは完全に解決可能です。頻繁に追加および転送する必要がある場合は、他のアルゴリズムの使用を検討するか、いくつかのハイブリッドオプションを検討することをお勧めします。たとえば、ネストされたセットと隣接リストを交差させます。これを行うには、各ノードで、左と右に加えて、親要素識別子への直接リンクを追加する必要があります。これにより、階層をすばやくナビゲートして親ノードと子ノードを見つけることができ、さらに、アルゴリズムの信頼性が向上します。


More articles:


All Articles