ツリー構造記憶と読み出しのModified Preorder Tree

前言
従来、ストレージツリー構造は、古典的な構造の組合せ、すなわち、各ノードが親ノードのIDを有し、これによって完全なツリー構造を構成してきた.しかし、このような構造は、データベースの再帰的なクエリーに関連するため、多くのクエリーに遭遇すると深刻なパフォーマンスのボトルネックになります.そこで、ネット上の様々な階層の格納方法を探して、それぞれ実現することにしました.この文書では、MySQL+MyBatis+SpringBootを使用してプリアンブルツリーストレージを実装します.この文書を読む前に、次のことを理解する必要があります.

Spring Boot

MyBatis

MySQL CRUD & Procedure

本明細書のソースコードはGitHUBで参照できます.皆さんのご意見を歓迎します.
どのような操作が必要ですか?
本文に入る前に、私たちは底層の具体的な実現から引き離す必要があります.ビジネスの角度から、私たちが木に対してどのような操作を行う必要があるのかを分析する必要があります.ここでは、分類管理を具体的なシーンとして使用します.在庫管理システムを書いた盆友たちは、さまざまな商品の分類を階層的に保存する必要があることを知っています.例えば、私たちは電子製品の大類を持っていて、その下にはデジタル製品、家電などの各種の小類も含まれていますが、各小類の下にはもっと具体的な分類があります.これらの分類は、ユーザインタフェースにおいて、直感的なツリー構造で以下のように示されることが多い.

-    
  -     
    -    
    -    
    -    
  -   

ビジネス・レベルでは、次の操作が必要です.

public interface TreeService {

    /**
     *   rootId         
     * @param rootId
     * @return
     */
    Category getTree(int rootId);

    /**
     *        
     * @return
     */
    List getRoots();


    /**
     *       
     * @param nodeName
     * @param parentId
     * @return
     */
    int addCategory(String nodeName, int parentId);

    /**
     *       
     * @param id
     * @return
     */
    void deleteCategory(int id);

    /**
     *                  
     * @param category
     * @return
     */
    int addCategoryList(Category category);
}

ビジネス・レベルで表示される各分類のノードは、次のとおりです.

public class Category {
    
    private int id;
    private String name;
    private List subCategories;

    public Category(int id, String name){
        this(name);
        this.id = id;
    }

    public Category(String name){
        this.name = name;
        subCategories = new ArrayList();
    }
    public void addSubCategory(Category subCategory){
        subCategories.add(subCategory);
    }

    public boolean isLeaf(){
        return subCategories==null || subCategories.size() == 0;
    }
}

Modified Preorder Treeとは
この文章は当時私に非常に大きな助けを与えてくれたので、本文を読む前にこの文章を強くお勧めして、Modified Preorder Treeがどのようなデータ構造なのかを理解してみましょう.基本的な認識が得られた後、SQLとSpringのトランザクションをさらに利用して各操作を完了し、上位の各操作を実現します.
次に、Modified Proorder Treeのデータ構造について説明します.
次の表作成文を使用して、MySQLでModified Preorder Treeのノードの表を新規作成できます.

#    
CREATE TABLE nested_category (
  category_id INT AUTO_INCREMENT PRIMARY KEY,
  name VARCHAR(20) NOT NULL,
  lft INT NOT NULL,
  rgt INT NOT NULL
);

データをデフォルトで挿入します.

INSERT INTO nested_category VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
  (4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
  (9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);

ここでのデータは、前の図の階層です.この直感的な階層に基づいて、ストレージと読み取りを行います.もちろん、それに対応するJAVAのクラスは:

import lombok.Data;
@Data
public class CategoryNode {

    private int id;
    private String name;
    private int lft;
    private int rgt;

    public boolean isLeaf(){
        return lft + 1 == rgt;
    }
}

本プロジェクトではlombokオープンソースプラグインを多く採用し、gettersとsettersの書き込みを簡素化しています.lombokを少し知ることができて、とても便利です.
1本の木.
まず、1本の木にアクセスして、ノードの削除をどのように実現するか、木全体を挿入するかを見てみましょう.次に、対応する操作のSQL文と対応するJAVAコードをそれぞれリストします.
現在のノードがルートノードで構成されているツリーを取得
ServiceのインタフェースはCategory getTree(int rootId)です.ノード自体を含むすべてのサブノードを1つの文で取得し、サービス層を再編成してツリーを構成します.これは、データベースに再帰的にアクセスするよりも明らかに効率的です.

    SELECT c1.* FROM nested_category c1, nested_category c2
        WHERE c1.lft >= c2.lft
              AND c2.rgt >= c1.rgt
              AND c2.category_id = #{id}
        ORDER BY c1.lft ASC

論理レベルでの再編成:

    public Category getTree(int rootId) {
        List categoryNodes = mapper.getSubCategoryNodesIncludingSelf(rootId);
        if (categoryNodes==null || categoryNodes.size() ==0) return null;
        CategoryNode root = categoryNodes.remove(0);
        return getTree(root, categoryNodes);
    }

    private Category getTree(CategoryNode parentCategory, List nodes){
        Category category = new Category(parentCategory.getId(), parentCategory.getName());
        if (!parentCategory.isLeaf()){
            while (nodes.size() > 0){
                CategoryNode tmpNode = nodes.get(0);
                if (tmpNode.getLft() > parentCategory.getRgt()) break;
                nodes.remove(0);
                category.addSubCategory(getTree(tmpNode, nodes));
            }
        }
        return category;
    }

分類を追加
ここでの追加操作は、親ノードの下に新しい分類を追加することです.元の他のサブノードには影響しません.ここではMySQLのプロセスストレージにサービス層のトランザクション管理を加えて実現します.

#    -              
CREATE PROCEDURE addCategory(
  IN categoryName VARCHAR(255),
  IN parentId INT,
  OUT categoryID INT
)
BEGIN
  SELECT @right := rgt FROM nested_category c WHERE c.category_id = parentId;
  UPDATE nested_category SET rgt = rgt + 2 WHERE rgt >= @right;
  UPDATE nested_category SET lft = lft + 2 WHERE lft >= @right;
  INSERT INTO nested_category(name, lft, rgt) VALUES(categoryName, @right, @right+1);
  SELECT LAST_INSERT_ID() INTO categoryID;
END;

CALL addCategory('GAME',1, @categoryId);
SELECT @categoryId;

ここではMyBatisを使用してストレージ・プロシージャを直接呼び出し、戻り結果を得ることができますが、ここでは本稿の重点ではありませんので、説明は省略し、Githubに直接行って確認することができます.サービス層コード:

    @Transactional
    @Override
    public int addCategory(String nodeName, int parentId) {
        return mapper.addCategoryTo(nodeName, parentId);
    }

分類を削除
分類を削除すると、分類lftとrgtの値内のすべてのノードをすべて削除する必要があり、すべての親ノードを更新する必要があります.

#    
CREATE PROCEDURE delCategory(
  IN categoryID INT
)
BEGIN
  SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
  FROM nested_category
  WHERE category_id = categoryID;

  DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

  UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
  UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
END;

CALL delCategory(1);

プロセス管理とトランザクションのサポートも必要です.

    @Override
    @Transactional
    public void deleteCategory(int id) {
        mapper.deleteCategory(id);
    }

複数の木
しかし、私たちのデータベースには分類が1つしかないことがよくありません.分類の下には、以前の電気製品類、家具類、書籍類など、複数の独立したルートノードがあります.Modified Preorder Tree構造での分類管理では、どのようにして複数のツリーを管理しますか?一般的には2つの考え方があります.

デフォルトでは、すべてのツリーに非表示のルートノードがあります.このルートノードに基づいて、私たちが知っている実際のルートノードは、その直接サブノードです.欠点は、1本のツリー構造の変動が必然的にすべてのノード

に影響を及ぼすことである.

は、ツリーごとに一定の空間を冗長化し、1024と仮定すると、ツリーごとのルートノードのlft値は1024の倍数となる.新しいツリーを挿入するたびに、次の最小1024の倍数からlft値としてツリー全体を構築します.欠点は、木の大きさが1024を超えると、木全体を再貯蔵する必要があることである.また,木の大きさが不均一であると,多くの空き値が使用されない.

各ノードは1つのフィールドを冗長化し、ルートノードのIDを導入する.これにより、すべてのlftが0から書き始めることができ、ツリーとツリーの前に干渉しない.欠点:冗長フィールド、挿入ツリーはルートノードのIDを取得してから、すべてのサブノード

に渡す必要があります.
ここでは1つ目の実装を採用し、後で2つ目と3つ目を続々と更新します.これまでのインプリメンテーションは、このシーンですべて完璧に適用できることがわかります.
すべてのルートノードを取得
ノードがルートノードでない場合、lft値がノードのlft値より小さく、rgt値がノードのrgt値より大きいノードが必ず存在する.

    SELECT * FROM nested_category c1
        WHERE c1.category_id
        NOT IN (
        SELECT DISTINCT c2.category_id
        FROM nested_category c2,
        nested_category c3
        WHERE c2.lft > c3.lft AND c3.rgt > c2.rgt)

もちろん、サービスレイヤでは、完全な構造のツリーノードを渡す必要があります.そのため、前のツリーを構築するコードを多重化することができます.

    @Override
    public List getRoots() {
        List roots = mapper.getRoots();
        List result = new ArrayList();
        for (CategoryNode n : roots){
            Category root = this.getTree(n.getId());
            result.add(root);
        }
        return result;
    }

新しい木を追加
新しいツリーを追加すると、現在のlftの開始値を取得し、各ノードにlft値とrgt値を中順に繰り返す必要があることを意味します.次に、データベースに一度に挿入します.ここではmybatisコードを直接飲みました.

    
        SELECT MAX(rgt) FROM nested_category;
    
    
    
        INSERT INTO nested_category(name, lft, rgt) VALUES
        
            #{element.name}, #{element.lft}, #{element.rgt}
        
    

    /**
     *           
     * @param category
     * @return
     */
    @Override
    public int addCategoryList(Category category) {
        int lftValue = mapper.getMaxRightValue() + 1;
        List nodes = new ArrayList();
        CategoryNode root = labelCategory(category, lftValue, nodes);
        mapper.addCategories(nodes);
        return root.getId();
    }

    /**
     *   lftValue     node    
     * @param category
     * @param lftValue
     * @return rgtValue
     */
    private CategoryNode labelCategory(Category category, int lftValue, List nodes){
        CategoryNode categoryNode = new CategoryNode();
        nodes.add(categoryNode);
        categoryNode.setName(category.getName());
        categoryNode.setLft(lftValue);
        int rgtValue = lftValue + 1;
        if (category.isLeaf()){
            categoryNode.setRgt(rgtValue);
        }else{
            for (Category subCategory : category.getSubCategories()){
                rgtValue = labelCategory(subCategory, rgtValue, nodes).getRgt() + 1;
            }
            categoryNode.setRgt(rgtValue);
        }
        return categoryNode;
    }

まとめ
非構造の階層ストレージは、読み取りに友好的であり、更新に友好的ではないことが多いため、特定のビジネスシーンに基づいて階層のストレージと読み取りをどのように実現するかを決定する必要があります.
参考記事
Managing Hierarchical Data in MysqlHierarchical data databaseツリー構造のデータテーブルの格納方法
より多くの開発技術、面接チュートリアル、インターネット会社のプッシュを知りたいなら、私の微信の公衆番号に注目してください.不定期で福祉が支給されますよ~