樹狀結(jié)構(gòu)存儲與讀取之Modified Preorder Tree

jkyin 發(fā)布于2019-08-15 15:52 / 1452人閱讀

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

前言

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

Spring Boot

MyBatis

MySQL CRUD & Procedure

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

我們需要什么操作

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

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

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

public interface TreeService {

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

    /**
     * 獲得所有根節(jié)點
     * @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);
}

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

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

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

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

我們可以通過如下的建表語句在MySQL中新建一個Modified Preorder Tree的節(jié)點的表：

#建表語句
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)。我們將在這個直觀的層次結(jié)構(gòu)的基礎(chǔ)上進(jìn)行存儲和讀取。
當(dāng)然了，與之對應(yīng)的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，非常方便。

一棵樹

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

獲得當(dāng)前節(jié)點為根節(jié)點構(gòu)成的樹

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

    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é)點之下添加一個新的分類。它并不影響原來的其他子節(jié)點。這里我們采用MySQL的過程存儲加上Service層的事務(wù)管理來實現(xiàn)。

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

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

刪除一個分類

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

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

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

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

多棵樹

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

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

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

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

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

獲得所有的根節(jié)點

如果一個節(jié)點不是根節(jié)點，那么一定存在一個節(jié)點，其lft值小于該節(jié)點的lft值，rgt值大于該節(jié)點的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)的樹節(jié)點，因此我們可以復(fù)用之前的構(gòu)造一棵樹的代碼：

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

添加一棵新的樹

添加一棵新的樹意味著需要獲取當(dāng)前l(fā)ft的起始值，并按照中序遍歷遞歸的為每個節(jié)點賦予lft和rgt值。然后將其一次性插入數(shù)據(jù)庫中。這里直接飲用了mybatis代碼。

    
    
    
        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è)置各個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é)

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

參考文章

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

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

云服務(wù)器 GPU云服務(wù)器 java存儲樹狀結(jié)構(gòu) 結(jié)果為樹狀結(jié)構(gòu) 樹狀數(shù)據(jù)結(jié)構(gòu) js數(shù)據(jù)存儲與讀取

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69291.html

發(fā)表評論

登陸后可評論

0條評論

jkyin

男|高級講師

我要關(guān)注我要私信

TA的文章

假如用for循環(huán)判斷一個數(shù)是否為質(zhì)數(shù)

閱讀 892·2021-11-15 11:38
大廠人分享的辦公軟件盤點，哪一款是你常用的？

閱讀 1619·2021-09-24 09:48
Python 和Java 哪個更適合做自動化測試？

閱讀 851·2021-09-24 09:47
SEO優(yōu)化接單項目設(shè)定策略和前景方向探討

閱讀 2281·2021-08-26 14:15
前端必備基礎(chǔ)

閱讀 3510·2019-08-30 11:09
百度網(wǎng)盤文件夾框選功能

閱讀 2616·2019-08-29 16:55
美化文件上傳按鈕自定義input file樣式

閱讀 1592·2019-08-26 14:01
使用 Taro 寫一個你畫我猜的小程序

閱讀 3047·2019-08-23 16:47

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

樹狀結(jié)構(gòu)存儲與讀取之Modified Preorder Tree

相關(guān)文章

localStorage實現(xiàn)本地儲存樹形菜單

樹和樹的算法

樹和樹的算法

發(fā)表評論

0條評論

jkyin

男|高級講師

TA的文章

假如用for循環(huán)判斷一個數(shù)是否為質(zhì)數(shù)

大廠人分享的辦公軟件盤點，哪一款是你常用的？

Python 和Java 哪個更適合做自動化測試？

SEO優(yōu)化接單項目設(shè)定策略和前景方向探討

前端必備基礎(chǔ)

百度網(wǎng)盤文件夾框選功能

美化文件上傳按鈕自定義input file樣式

使用 Taro 寫一個你畫我猜的小程序

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

樹狀結(jié)構(gòu)存儲與讀取之Modified Preorder Tree

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！