摘要：本文將通過(guò)實(shí)現(xiàn)先序樹(shù)存儲(chǔ)。我們將在這個(gè)直觀的層次結(jié)構(gòu)的基礎(chǔ)上進(jìn)行存儲(chǔ)和讀取。缺點(diǎn)在于如果樹(shù)的大小超過(guò)了，那么需要對(duì)整棵樹(shù)進(jìn)行重新轉(zhuǎn)儲(chǔ)。

一直以來(lái)存儲(chǔ)樹(shù)狀結(jié)構(gòu)都采用經(jīng)典的結(jié)構(gòu)的組合，即每一個(gè)節(jié)點(diǎn)持有其父節(jié)點(diǎn)的ID，并由此構(gòu)成完整的樹(shù)狀結(jié)構(gòu)。但是這樣的結(jié)構(gòu)在遇到大量的查詢(xún)時(shí)會(huì)成為嚴(yán)重的性能瓶頸，因?yàn)樗婕傲藢?duì)數(shù)據(jù)庫(kù)的遞歸查詢(xún)。因此我查找了一下網(wǎng)上的各種層次結(jié)構(gòu)的存儲(chǔ)方式并決定對(duì)其分別實(shí)現(xiàn)。本文將通過(guò)MySQL+MyBatis+SpringBoot實(shí)現(xiàn)先序樹(shù)存儲(chǔ)。
閱讀本文之前需要了解：

Spring Boot

MyBatis

MySQL CRUD & Procedure

本文的源碼可以在GitHUB上查看。歡迎大家給出意見(jiàn)。

在進(jìn)入正文之前，我們需要從底層的具體實(shí)現(xiàn)抽離開(kāi)來(lái)，從業(yè)務(wù)的角度來(lái)分析我們究竟需要對(duì)一棵樹(shù)進(jìn)行什么樣的操作。這里我們將以分類(lèi)管理作為具體場(chǎng)景。寫(xiě)過(guò)庫(kù)存管理系統(tǒng)的盆友們都知道，我們需要用某種方式對(duì)各種商品的分類(lèi)按照層次結(jié)構(gòu)進(jìn)行存儲(chǔ)。比如我們有電子產(chǎn)品大類(lèi)，底下還包括數(shù)碼產(chǎn)品，家電等等各種小類(lèi)，而在各個(gè)小類(lèi)之下我們也還有多種更加具體的分類(lèi)。這些分類(lèi)在用戶界面往往以直觀的樹(shù)狀結(jié)構(gòu)展示如下：

-電子產(chǎn)品
  - 數(shù)碼產(chǎn)品
    - 手機(jī)類(lèi)
    - 相機(jī)類(lèi)
    - 電腦類(lèi)
  - 家電

因此在業(yè)務(wù)層的角度來(lái)說(shuō)我們需要以下操作：

public interface TreeService {

    /**
     * 獲得rootId節(jié)點(diǎn)下的所有子節(jié)點(diǎn)
     * @param rootId
     * @return
     */
    Category getTree(int rootId);

    /**
     * 獲得所有根節(jié)點(diǎn)
     * @return
     */
    List getRoots();


    /**
     * 添加一個(gè)分類(lèi)
     * @param nodeName
     * @param parentId
     * @return
     */
    int addCategory(String nodeName, int parentId);

    /**
     * 刪除一個(gè)分類(lèi)
     * @param id
     * @return
     */
    void deleteCategory(int id);

    /**
     * 添加一個(gè)分類(lèi)列表作為一個(gè)全新的分類(lèi)
     * @param category
     * @return
     */
    int addCategoryList(Category category);
}

而業(yè)務(wù)層所看到的每一個(gè)分類(lèi)的節(jié)點(diǎn)如下：

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

這篇文章當(dāng)時(shí)給了我非常大的幫助，在閱讀本文之前強(qiáng)烈建議先閱讀這篇文章，來(lái)了解一下Modified Preorder Tree究竟是什么樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)。在有了一個(gè)基礎(chǔ)的認(rèn)識(shí)之后我們將進(jìn)一步利用SQL和Spring的事務(wù)來(lái)完成各項(xiàng)操作，從而實(shí)現(xiàn)之前列出的各項(xiàng)操作。

接下來(lái)了解一下Modified Proorder Tree的數(shù)據(jù)結(jié)構(gòu)。

我們可以通過(guò)如下的建表語(yǔ)句在MySQL中新建一個(gè)Modified Preorder Tree的節(jié)點(diǎn)的表：

#建表語(yǔ)句
CREATE TABLE nested_category (
  category_id INT AUTO_INCREMENT PRIMARY KEY,
  name VARCHAR(20) NOT NULL,
  lft INT NOT NULL,
  rgt INT NOT NULL
);

并且先默認(rèn)的插入一些數(shù)據(jù)：

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

這里的數(shù)據(jù)就是之前那張圖的層次結(jié)構(gòu)。我們將在這個(gè)直觀的層次結(jié)構(gòu)的基礎(chǔ)上進(jìn)行存儲(chǔ)和讀取。
當(dāng)然了，與之對(duì)應(yīng)的JAVA中的類(lèi)為：

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

本項(xiàng)目中很多地方的采用了lombok開(kāi)源插件來(lái)簡(jiǎn)化getters和setters的書(shū)寫(xiě)。可以稍微了解一下lombok，非常方便。

我們先從存取一棵樹(shù)入手，來(lái)看看究竟如何實(shí)現(xiàn)節(jié)點(diǎn)的增刪改查，以及插入一整棵樹(shù)。下面我將分別列出相應(yīng)操作的SQL語(yǔ)句以及對(duì)應(yīng)的JAVA代碼。

Service中的接口為Category getTree(int rootId)
我們將用一條語(yǔ)句獲取該節(jié)點(diǎn)所有的子節(jié)點(diǎn)（包括該節(jié)點(diǎn)本身），再在service層進(jìn)行重組構(gòu)成一棵樹(shù)。相對(duì)于之前通過(guò)遞歸訪問(wèn)數(shù)據(jù)庫(kù)，這樣的方式明顯效率更高。

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

這里的添加操作是指在父節(jié)點(diǎn)之下添加一個(gè)新的分類(lèi)。它并不影響原來(lái)的其他子節(jié)點(diǎn)。這里我們采用MySQL的過(guò)程存儲(chǔ)加上Service層的事務(wù)管理來(lái)實(shí)現(xiàn)。

#插入節(jié)點(diǎn)-只能作為當(dāng)前節(jié)點(diǎn)的一個(gè)新節(jié)點(diǎn)
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直接調(diào)用存儲(chǔ)過(guò)程并獲得返回結(jié)果，但是這里并不是本文的重點(diǎn)，所以不多贅述，可以直接前往Github查看。
Service層代碼：

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

刪除一個(gè)分類(lèi)意味著我們需要所有在該分類(lèi)lft和rgt值之內(nèi)的節(jié)點(diǎn)全部刪除，同時(shí)需要更新其所有的父節(jié)點(diǎn)。

#刪除節(jié)點(diǎn)
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);

這里同樣需要過(guò)程管理加上事務(wù)的支持：

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

然而，我們的數(shù)據(jù)庫(kù)往往并不會(huì)只有一個(gè)分類(lèi)，分類(lèi)之下往往會(huì)有多個(gè)獨(dú)立的根節(jié)點(diǎn)，比如之前的電器類(lèi)，還有家具類(lèi)，書(shū)籍類(lèi)。我們?nèi)绾卧贛odified Preorder Tree結(jié)構(gòu)下的分類(lèi)管理中管理多棵樹(shù)呢？
一般來(lái)說(shuō)有兩種思路：

默認(rèn)所有的樹(shù)都有一個(gè)隱藏的根節(jié)點(diǎn)，在此根節(jié)點(diǎn)的基礎(chǔ)上，每個(gè)我們所知道的真實(shí)根節(jié)點(diǎn)為其直接子節(jié)點(diǎn)。缺點(diǎn)在于一棵樹(shù)結(jié)構(gòu)的變動(dòng)將必然會(huì)影響所有節(jié)點(diǎn)

為每棵樹(shù)冗余一定的空間，假設(shè)為1024，那么每棵樹(shù)的根節(jié)點(diǎn)的lft值為1024的倍數(shù)。每次插入一棵新的樹(shù)，我們將從下一個(gè)最小的1024的倍數(shù)作為lft值構(gòu)建整棵樹(shù)。缺點(diǎn)在于如果樹(shù)的大小超過(guò)了1024，那么需要對(duì)整棵樹(shù)進(jìn)行重新轉(zhuǎn)儲(chǔ)。而且如果樹(shù)的大小不均勻，那么將會(huì)產(chǎn)生很多的空余值沒(méi)有被使用。

每個(gè)節(jié)點(diǎn)冗余一個(gè)字段，引入根節(jié)點(diǎn)的ID，這樣的話所有的lft都可以從0開(kāi)始寫(xiě)起并且樹(shù)與樹(shù)之前不會(huì)相互干擾。缺點(diǎn)：冗余字段，插入樹(shù)是需要先獲取根節(jié)點(diǎn)的ID，再傳遞給所有的子節(jié)點(diǎn)

這里我采用了第一種實(shí)現(xiàn)，后面會(huì)陸續(xù)更新第二和第三種。
可以看到，之前的實(shí)現(xiàn)在該場(chǎng)景下全部可以完美適用。

如果一個(gè)節(jié)點(diǎn)不是根節(jié)點(diǎn)，那么一定存在一個(gè)節(jié)點(diǎn)，其lft值小于該節(jié)點(diǎn)的lft值，rgt值大于該節(jié)點(diǎn)的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)

當(dāng)然了，service層要求傳遞完整結(jié)構(gòu)的樹(shù)節(jié)點(diǎn)，因此我們可以復(fù)用之前的構(gòu)造一棵樹(shù)的代碼：

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

添加一棵新的樹(shù)意味著需要獲取當(dāng)前l(fā)ft的起始值，并按照中序遍歷遞歸的為每個(gè)節(jié)點(diǎn)賦予lft和rgt值。然后將其一次性插入數(shù)據(jù)庫(kù)中。這里直接飲用了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并設(shè)置各個(gè)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;
    }

非結(jié)構(gòu)的層次存儲(chǔ)往往對(duì)讀取友好而對(duì)更新不友好，所以我們往往需要根據(jù)具體的業(yè)務(wù)場(chǎng)景來(lái)決定如何來(lái)實(shí)現(xiàn)層次結(jié)構(gòu)的存儲(chǔ)和讀取。

Managing Hierarchical Data in Mysql
Hierarchical data database
樹(shù)狀結(jié)構(gòu)的數(shù)據(jù)表如何存儲(chǔ)

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~