入れ子の間隔とYii2での実装

こんにちは、Habr！

ほとんどの開発者は、ネストセットとは何か、その長所と短所を知っています。 今日、私はこの手法の修正の実装を公開したいと思います。これは、元のアルゴリズムの欠点を部分的に解決しますが、欠点もあります。



元のネストされたセットの長所と短所は何ですか：

+簡単なリクエストで親と子をすばやく選択;

+簡単なリクエストで隣接ノードをすばやく選択。

+簡単なリクエストで空のノードをすばやく選択。

+式に従って、ノード内のすべての子の数を即座に受け取ります。

+ 1つのサイクルで再帰的にツリーを構築しない可能性。

-挿入と更新が非常に遅い。



挿入/更新が遅い理由は何ですか？ ノードの境界の値は継続的に移動するため、特にツリーの先頭に挿入する場合は、後続のすべてのノードの境界を再計算する必要があります。 テーブルが十分に大きい場合、このプロセスは数十秒またはさらに長くドラッグできます。 アニメーションについて：

入れ子の間隔

ネストされたセットの視覚的表現を含む写真を検討するときに思いついた最初の考えは、「ルートノードを実数のフィールド上のセグメントとして想像すると、境界線を移動できません」です。 つまり、ルートノードの境界の値が0.0および1.0であると想像した場合、他のノードを移動せずに任意の場所にノードを追加できます。ターゲットノード間で実数を取る必要があります。 しかし、コンピューターの実数には限界があることを完全に知っているため、整数を優先してこの考えをすぐに放棄しました。



整数の場合、本質は同じです。ルートノードの境界をゼロからINT_MAXにするだけです。 次に、新しいノードを挿入するときに、ターゲットノード間に空いている2つの値を取得し、他に何も触れないでください。 明らかに、すべての境界値を最も近い自由な値に移動して、挿入用のスペースを「クリア」する必要があります。 しかし、このような「穴」を見つけるのはコストのかかる作業であるため、この場合の結果は、従来のネストされたセットよりもさらに遅くなる可能性があります。









少しグーグルで、私は自転車を発明していなかったことに気付きました。この考えは長い間Nested Itervalsと呼ばれていました。 しかし、ほとんどのリソースでは、この手法は「一方は治り、もう一方は不自由になった」という否定的な方法で検討されていたため、私は気づいていません。 そして、これは根拠のないことではありませんが、私にとって非常に興味深いものになりました。このアルゴリズムがどのように優れているか、どのアルゴリズムが悪いか、どれくらいあるかをテストしたかったのです。

実装

ネストされた間隔のアイデアを実装するYii2の動作の記述を開始しました。 挿入メソッドを作成するときに最初の問題が発生しましたinsertBefore()



およびinsertAfter()



隣接ノードまたは親の境界線を取得し、 insertBefore()



およびinsertAfter()



で最初/最後のノードの境界線を取得する方法 ネストされたセットで明らかな場合は、現在のノードの境界に+ + 1 / -1であるため、データベースへの追加のクエリは一切ありません。 しかし、サンプルが高速であることは良いことです。



新しいノードを挿入するのに十分なスペースがない場合、割り当てられていないスペースの検索の実装にかなりの時間が費やされました。 しかしその結果、ベースの半分ではなく、現在のセグメントから最も近い「穴」に小さな部分の境界を移動する機会を得ました。



既存のブランチを新しい場所に移動するときに、次の大きな疑問が生じました。 この操作が同じツリー内で発生した場合、2つのブロックを交換するだけで、すべてをすばやく実行できます。







しかし、別のツリーから移動すると、多くの移動ノードが存在する可能性があり、通常のアルゴリズムを使用してそれらを挿入するのに時間がかかりすぎるため、問題の解決が困難であることが判明しました。 最初は、一般的にこの機会を放棄し、実装の複雑さに起因することを望みました。 しかし、少し後に、私はoptimize()



メソッドの必要性に気付きました。このメソッドは、既存のノードの境界をある範囲に均等に分散します。 その後、移動するノードの「ウィンドウ」を準備してソースツリーを最適化することにより、別のツリーのノードを移動するというアイデアが生まれました。 これはすべて非常にゆっくり動作します（現時点では、この方法はMySQLに対してのみ最適化されています）が、他のツリーから移動する操作はほとんど必要なく、同じツリー内での移動がより頻繁に必要であることに注意してください。



しかし、サンプルの実装は非常に簡単でした-親と子を取得する主な方法は、従来のネストされたセットと同じです。 前/次のネイバーのサンプルではもう少し複雑です。2つのクエリが必要です。親を取得し、制限のある範囲で直接検索します。 ただし、空のgetLeaves()



ノードを取得すると本当に悪い状態になりました。これは、パフォーマンスに影響する可能性がある左結合で行う必要があるためです。

挿入の最適化

パフォーマンステストの最初のシリーズを実行した後、結果は控えめに言っても印象的ではありませんでした。 問題は、最初にセグメントを3つの部分に分割することで、挿入されたノードの境界の選択を最初に実現したことです。 このため、新しいノードのギャップは急速に減少していました。 32ビットPHPの範囲は[ appendTo()



]（大きい数値の操作は浮動小数点に変換される）であるため、 appendTo()



を介してルートに合計19ノードを挿入すると、20番目のノードにスペースが残りません（2147483647/3 ^ 19 =〜1.9）、空いている場所を見つけて移動するには、遅い操作を実行する必要があります。 そのため、もちろん機能しません。 スペースの割り当てに何らかの最適化が必要です。 これには、動作のオプションがすでに5つあります。

• 最初の主要なamountOptimize
  
  
  
  このパラメーターは、挿入可能なセグメントの分割を計画するノードの数を決定します。 つまり、値が20の場合、20個の子ノードを挿入できます。これらの子ノードは、親の範囲を均等に占有し、それがどのように進むかを示します。
  
  配列を値として使用できます。値はレベルごとに異なります。
  
  
• noPrepend
  
  
  
  、 noAppend
  
  
  
  、 noInsert
  
  
  
  これらのパラメーターは、境界間のスペースの予約、および最初のノードの位置を最適化するのに役立ちます。 appendTo()
  
  
  
  操作（たとえば、コメント）のみをappendTo()
  
  
  
  場合は、 noPrepend = true
  
  
  
  およびnoInsert = true
  
  
  
  設定することができます。これにより、新しいノードのスペースをクリアする困難なケースの可能性を大幅に削減できます。 これらのパラメータの効果は、写真でより明確に示されています。
  
  

  amountOptimize = 3
  amountOptimize = 3 noPrepend = true
  amountOptimize = 3 noAppend = true
  amountOptimize = 3 noInsert = true
  amountOptimize = 3 noInsert = true noPrepend = true
  amountOptimize = 3 noInsert = true noAppend = true

  
  
  noPrepend = true
  
  
  
  をnoPrepend = true
  
  
  
  した場合、これはprependTo()
  
  
  
  を挿入できないことを意味するものではないことに注意してprependTo()
  
  
  
  。これらの操作の多くはゆっくり実行される可能性が非常に高いです。
  
  
• そして、最後のreserveFactor
  
  
  
  パラメーターは、境界線間のギャップのサイズを決定します。 ユニティの場合、ギャップのサイズは挿入されたノードのサイズと等しくなります。 Behaviorの使用シナリオで多数のinsertBefore()
  
  
  
  およびinsertAfter()
  
  
  
  操作が想定されている場合、このパラメーターを増やす必要があります。

これらすべての操作の後、テストははるかに「おいしい」ものになりました。

64ビット

BIGINT列を使用してright



属性を保存left



、64ビットPHPを使用する場合、より広い範囲の形式で自由な最適化を使用できます。 range = [0、9223372036854775807]パラメーターを設定するだけです。 これにより、新しいノード用のスペースが不足するまれなケースが発生します。

性能試験

比較のための参照として、最も人気のある動作が採用されました。これは、尊敬されるAlexander Kochetov（Creocoder） creocoder / yii2-nested-setsからNested Setsを実装しています 。 また、ソート機能を保持しながら、結果を隣接リストと比較することも興味深いものでした。 私はこれに適したライブラリを見つけられなかったので、それを取り、自分で書きました （そして、JOINサポートがありますが、これは今ではありません）。



最初の2つのテストは非常に総合的なものです。実際には誰もがツリーを満たすことはほとんどありませんが、最初の段階でこの手順が必要でした。 彼らは単に一定数の子供でレベルを一貫して満たします。



テスト3〜5は、大きなテーブルのさまざまな場所に20個のノードを挿入することを模倣します。



次のテストでは、ツリーの先頭から20個のノードが削除されます。



テスト7は、コメントにBehaviorを使用することを模倣しているため、非常に明らかになっています。 サイクルでは、ランダムに選択されたノードにレベル制限付きで1000個のノードが追加されます。 テスト8も同様ですが、さらに厳しい条件があります。追加だけでなく、他の操作も許可されます。



ツリー内のノードを移動するための次の2つのテスト：



Behaviorを書いた後、動作の代わりにTraitを使用する利点を知りたいと思いました。 そこで、静的属性を使ってTraitに移植しました。 Traitを使用したバリアントでも、さらなるサンプリングテストが実行されました。 しかし、不純物を穏やかに使用した結果は、特にそれらが原因でコードがどれだけmoreくなるかを考えると、印象的ではありませんでした。

すべての要素の簡単な選択Model::find()->all()



：



子孫のサンプリング：



先祖のサンプル：



隣接ノードおよび空ノードの選択：

結論

入れ子の間隔-生きる権利があります。 利点と欠点の両方があります。

+クイック挿入（最適化パラメーターの適切な選択の対象）;

+子孫を持つノードの迅速な削除。

+祖先と子孫のサンプルのネストセットと同じ速度。

+また、1サイクルで非再帰的にツリーを構築する可能性が残っています。

-近隣ノードの受信が遅い。

-空のノードの受信が遅い。

-ノード内の子孫の数を即座に計算する方法はありません。

Yii2の実装

これらの方法は、Creocoderの動作で提案されている方法とはわずかに異なることに注意してください。 最初に、メソッドの名前をgetParents() getDescendants()



に変更しました。これにより、リレーションと同様に、関連するノードへのアクセスを実装できます。これにより、データベースに2次クエリを作成できません。

 $node = Node::findOne(['name' => 'test']); $children = $node->children; // relation $children = $node->getChildren()->all(); // query
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらに、保存するYiiパラメーター（$ runValidation、$ attributeNames）をプッシュせず、代わりにアクションの指示としてメソッドを実装し->asArray()->



）：

 $node = new Node(); $node->makeRoot()->save(false); $node->insertAfter($node2)->save();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

GitHubでのネストされた間隔の実装 。

GitHubでの隣接リストの実装 。