バイナリマテリアライズドパスを使用してツリーをソートする問題を解決する

1つのプロジェクトにツリーのようなコメントを実装する問題に直面して、この記事ではソリューションを投稿します。

タスクの説明

• MySQLリレーショナルデータベースに階層データ（ツリーコメント）を保存する
• ノード/ブランチの簡単な追加
• 1つのクエリでツリー全体を選択し、ブランチを正しい順序でソートします

原則として、タスクは古典的なものであり、最初は隣接リストとマテリアライズドパスを組み合わせて解決しました。 つまり、列がテーブルに追加されます

id INT(11) parentid INT(11) mpath VARCHAR(255)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

mpathには、ツリー内のブランチのフルパスが格納されていました。たとえば、 / 1/3/4/5/8/9には、コメントIDが「/」記号でリストされていました。



このアプローチを使用すると、ほぼすべてのレベルのネストの新しいコメントを簡単に追加できます。 同時に、クエリによって選択が行われました。

 SELECT * FROM messages WHERE postid=$postid ORDER BY mpath ASC
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この問題は、コメントの数の増加とともに発生しました。 たとえば、次のパスを持つツリーがあります。

 1 1.2 1.2.10 1.2.3 1.2.7 4 4.8 4.8.9 5 5.6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、数字はIDを示し、順序はORDER BY mpath ASC



を使用した場合の順序です。

コメント1.2.10は1.2.3などに適用されますが、後で追加されました（IDによる判断）。

問題解決

問題の解決策の一部は、 http ： //habrahabr.ru/post/125729/で説明されています。 アイデアは、パスで10進数のIDではなく、パスの長さの制限を少なくするために別の番号システムにエンコードすることです。 同時に、フィールドはソートにのみ使用されるため、ドットまたはその他の文字の形式の区切り記号は必要ありません。



ASCIIで印刷する正確な文字数であるベース95を使用しました。

  !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パスの各値に固定長を使用する場合、次の上限しきい値IDを取得します。

1-95 ^ 1-1 = 94

2-95 ^ 2-1 = 9,024

3-95 ^ 3-1 = 857 374

4-95 ^ 4-1 = 81 450 624

5-95 ^ 5-1 = 7 737 809 374



コメントの最大数を気にしないには、5文字で十分です。

ネストの最大レベル。VARCHAR255/5 = 51の場合



理論的には、BASE95ではなくBASE256（非印刷可能文字とともに）を使用できますが、すべてバイナリをBLOBに保存できますが、ここではソート時のパフォーマンスについてはわかりません（確認する必要があります）。 次に、3文字を使用して、16,777,215個のバリアントと4〜4,294,967,295個をエンコードできます。

コードでの見え方

この理論全体の実装例を紹介します。

 // $mpath -   materialized path   "/" //    : $db->Execute(" UPDATE messages SET mpath=?, bpath=?, depth=? WHERE id=? ", array( $mpath, bpath($mpath), $depth, $messid )); // . . . //      define('BASE95', ' !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~'); // . . . //  bpath function bpath($mpath, $sep = '/', $max_len = 5) { $bpath = ''; $chunks = explode($sep, trim($mpath, $sep)); $zero = substr(BASE95, 0, 1); foreach($chunks as $chunk) $bpath .= str_pad(dec2base($chunk, 95, BASE95), $max_len, $zero, STR_PAD_LEFT); return $bpath; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらに選択：

 SELECT * FROM messages WHERE postid=$postid ORDER BY bpath ASC
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

dec2base関数はここから取得されます 。



私の意見では、そのような解決策は非常に簡単です。 武器庫にも美しい解決策がある場合は、コメントで共有してください。