目錄

一、出現的問題

部門樹接口超時

二、問題分析

源代碼分析

三、解決方案

具體實現思路

四、優化的效果

---

一、出現的問題

部門樹接口超時

無論是在A項目還是在B項目中，都存在類似的頁面，其實就是一個部門列表或者叫組織列表。

從頁面的展示形式上來看它是一個樹狀結構。因此在最早的接口設計上也是通過一個接口返回該租戶的部門頁面進行顯示。

接口的返回形式如上。其實也很簡單。就是一個通過一個嵌套的對象實現了樹

但是在我們私有化的過程中有一些大型的集團客戶，他們整個集團的部門數量上萬個甚至可能出現 10w 多個部門。因此出現了接口超時20s 都沒有結果的情況出現了。

數據權限查詢子部門超時

其實，不光有這個場景，在我們的數據權限設計上有一個，這個意思呢就是。如果用戶的數據權限為本級及子級的，那這個用戶就能查看用戶所屬部門和該部門子部門下產生的數據。按照目前的實現方式，那我們就要知道這個用戶的部門和子部門。

那這個查詢子部門的過程也會同樣出現超時的情況。

二、問題分析

源代碼分析

走讀原先的部門樹接口邏輯發現，是通過遞歸查詢的方式實現。

在數據表的設計上，是通過一個 parent_id 字段關聯的是父部門的 id。因此可以通過該字段查詢到這個部門的子部門的列表。然后通過遞歸不斷地遍歷就能查詢出所有的部門并且組裝成樹。

偽代碼邏輯其實就是

// 遞歸查詢函數，參數為要查找的父部門id
List<Department> findDepartmentsByParentId(int parentId) {
????List<Department> departmentList = queryFromMysql(parentId);
??// 用于存放查詢結果的列表
????List<Department> result = new List<Department>(); ?
????for (Department department : departmentList) {
????????if (department.parentId == parentId) {
????????????result.add(department);
????????????// 遞歸調用，查找當前部門下的子部門，并將結果合并
????????????List<Department> subDepartments = findDepartmentsByParentId(department.id);
????????????result.addAll(subDepartments);
????????}
????}

????return result;

?可能出現問題的原因

1. 子部門數量太多。導致queryFromMysql 這個方法執行的次數多
2. 部門層級深。導致queryFromMysql 這個方法執行的次數多

核心原因其實還是每一次查詢子部門都需要通過queryFromMysql這個方法執行一次，類似如下的

select * from department where tenant_id=xxx and parent_id=xxx;

不難發現，問題的根本原因就是 sql 查詢執行次數太多了。那么現在問題的核心就是減少 sql 查詢的次數。就能解決問題。

當然這里沒有考慮改交互的方式，比如一次只查詢一級，慢慢展開呢，其實一樣，數據權限的子部門那里保持原樣還是會超時。

另外，細心的同學可能發現這個代碼有問題呀，為什么要從 root 一層一層地查下去，直接用租戶 id 查詢出所有的部門數據然后再組裝成樹不是會解決嗎。確實可以解決部門樹的查詢，但是數據權限的子部門那里保持原樣還是會超時。

因此要解決的問題核心還是傳入任何一個部門 id 能夠快速查詢出子部門列表。

三、解決方案

1. 加緩存，可能存的數據比較多吧，每一個部門 id 都需要存一份子部門的數據。初始化構建緩存的時候查詢依舊慢，這里不討論了。因為核心問題是解決查詢數據庫慢的問題
2. 減少查詢數據庫的次數，從而減少響應時間

具體實現思路

回顧標題，要用數據結構去優化查詢，那可能就是在原先表的基礎增加一些輔助字段來提高查詢的效率。加索引肯定沒啥大作用了，因為這里的查詢慢是因為次數多而不是因為單詞查詢數據量大導致。當然索引該加還是得加。

?

我們可以添加為每個節點添加兩個值，代表數據的范圍（leftValut, rightValue）

需要滿足以下要求：

1. 1. 每個節點的 leftValut < rightValue
   2. 子節點的 leftValut > 父節點的 leftValue
   3. 子節點的 rightValue < 父節點的 rightValue

我們按照，這個規則給上面的結構賦值下：

再觀察下，怎么去查子部門呢？

比如 ?2-1（2,9） 的 子部門為 ?3-1（3,6） 和 ?3-2（7,8）以及 3-1 的子部門 4-1（4,5）。 可以看出 3,4,5,6,7,8 都在 2,9 之間。

因此可以用，2< leftValue/rightValue <9 ?查詢到 3-1,3-2,4-1 .而這幾個正好是 2-1 的子部門。

根據我們賦值的限制條件不難看出一個部門的所有子部門的 leftValue 和 rightValue 是在父部門的范圍內的。所以我們在查詢一個部門的所有子部門時，就可以用如下的偽代碼去查詢

//1. 查詢該部門的 leftValue 和 rightValue
Dept dept = queryDeptFromMysql(parentId);
int leftValue = dept.getLeftValue();
int rightValue = dept.getRightValue();

//2. 通過leftValue 和 rightValue 查詢子部門
List<Dept> childDepts = queryChildDeptsFromMysql(leftValue,rightValue)

//sql 的話就是這樣
// select * from dept where tenant_id=xxx and left_value > #{leftValue} and left_value < #{rightValue}
??
//3. 根據實際情況返回列表，或者組裝成樹

在我們有這兩個左右值的情況下，一條 sql 就能查詢出所有符合條件的結果。那么現在的問題來到了如何去為每個部門節點進行賦值。

如何對部門進行賦值

可以分為以下幾種情況討論：（這里只考慮增加修改的情況都是單部門）

???????初始化 ??初始化是最簡單的，我們只需要以根節點（leftValue 值為 1）為開始深度優先遍歷， 每次+1 即可。

這里的初始值設置為 1 即可。很簡單

???????新增部門

?

可以看出變化的部分是

1. 1. 新增了一個部門 4-2 他的值分別是 4-1 的 （rightValue +1,rightValue+2) 即 6,7
   2. 因為 3-1 增加了子部門所以他的值范圍必定發生變化，變化的增長值就是 2 （ 也是增加的節點個數*2）因為部門 4-2 已經是 6,7 了 所以 3-1 部門會發生變化為 3,8
   3. 同理后續右邊（比發生變化的值大的）節點的值都會發生對應的變化

其實不難看出，每個值大于等于 4-1 的rightValue +1，（即新增加的4-2的 leftValue） 的值都增加了 2 ，無論他是leftValue還是rightValue。

那么新增加一個子節點可以這樣去更新。當然你還要把新加的部門加進去

  UPDATE deptSET left_value = IF(left_value > #{leftValue}, left_value + #{changeValue}, left_value),right_value = IF(right_value > #{leftValue}, right_value +  #{changeValue}, right_value)where tenant_id= #{tenantId};

?

changeValue 是什么呢。其實就是變化的節點的個數*2，而這里就是 2，因為只新增了一個子節點 4-2

那如果，新增加的部門不是一個，而是多個呢？

其實這種情況在我們這種頁面上不會出現。因為添加部門的時候只會添加一個。

那刪除和修改就是一個道理了~

就不多演示了

???????感興趣的可以評論區討論~

四、優化的效果

部門樹（約有 1.8w 個部門）的接口返回了如此巨大數據的情況的下只用了 400ms。其中還對部門重新進行了排序，并且帶有其他邏輯。效果堪稱顯著。