摘要：本文將通過實現先序樹存儲。我們將在這個直觀的層次結構的基礎上進行存儲和讀取。缺點在于如果樹的大小超過了，那么需要對整棵樹進行重新轉儲。

一直以來存儲樹狀結構都采用經典的結構的組合，即每一個節點持有其父節點的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究竟是什么樣的一個數據結構。在有了一個基礎的認識之后我們將進一步利用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，非常方便。

我們先從存取一棵樹入手，來看看究竟如何實現節點的增刪改查，以及插入一整棵樹。下面我將分別列出相應操作的SQL語句以及對應的JAVA代碼。

Service中的接口為Category getTree(int rootId)
我們將用一條語句獲取該節點所有的子節點（包括該節點本身），再在service層進行重組構成一棵樹。相對于之前通過遞歸訪問數據庫，這樣的方式明顯效率更高。

    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的過程存儲加上Service層的事務管理來實現。

#插入節點-只能作為當前節點的一個新節點
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查看。
Service層代碼：

    @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);
    }

然而，我們的數據庫往往并不會只有一個分類，分類之下往往會有多個獨立的根節點，比如之前的電器類，還有家具類，書籍類。我們如何在Modified Preorder Tree結構下的分類管理中管理多棵樹呢？
一般來說有兩種思路：

默認所有的樹都有一個隱藏的根節點，在此根節點的基礎上，每個我們所知道的真實根節點為其直接子節點。缺點在于一棵樹結構的變動將必然會影響所有節點

為每棵樹冗余一定的空間，假設為1024，那么每棵樹的根節點的lft值為1024的倍數。每次插入一棵新的樹，我們將從下一個最小的1024的倍數作為lft值構建整棵樹。缺點在于如果樹的大小超過了1024，那么需要對整棵樹進行重新轉儲。而且如果樹的大小不均勻，那么將會產生很多的空余值沒有被使用。

每個節點冗余一個字段，引入根節點的ID，這樣的話所有的lft都可以從0開始寫起并且樹與樹之前不會相互干擾。缺點：冗余字段，插入樹是需要先獲取根節點的ID，再傳遞給所有的子節點

這里我采用了第一種實現，后面會陸續更新第二和第三種。
可以看到，之前的實現在該場景下全部可以完美適用。

如果一個節點不是根節點，那么一定存在一個節點，其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)

當然了，service層要求傳遞完整結構的樹節點，因此我們可以復用之前的構造一棵樹的代碼：

    @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 Mysql
Hierarchical data database
樹狀結構的數據表如何存儲

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~