一種高效的樹形數(shù)據(jù)存儲(chǔ)方法：分段式數(shù)字存儲(chǔ)

關(guān)鍵詞：樹形結(jié)構(gòu)；數(shù)據(jù)存儲(chǔ)；算法

0 引言

樹形結(jié)構(gòu)數(shù)據(jù)是一種層次化的數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)和邊組成，常用于表示具有層級(jí)關(guān)系的數(shù)據(jù)[1]。樹形結(jié)構(gòu)數(shù)據(jù)應(yīng)用于不同領(lǐng)域。比如：（1） 國家行政區(qū)劃。從省、地、縣、鄉(xiāng)四級(jí)，采用樹形結(jié)構(gòu)進(jìn)行存儲(chǔ)能夠清晰表現(xiàn)出各級(jí)行政區(qū)的關(guān)系；（2） 公司組織架構(gòu)。同樣是存在上下級(jí)關(guān)系，完全符合樹形結(jié)構(gòu)的關(guān)系，采用樹形存儲(chǔ)容易簡化查詢、檢索以及展示的問題；（3） 商品目錄分類。不同商品有不同分類方式，例如在電商網(wǎng)站或貿(mào)易網(wǎng)站中經(jīng)常存在，通過不同類目一級(jí)一級(jí)地進(jìn)行檢索商品。

樹形結(jié)構(gòu)數(shù)據(jù)在不同領(lǐng)域都有重要的應(yīng)用價(jià)值，能夠清晰地表達(dá)層級(jí)關(guān)系，為數(shù)據(jù)的組織和管理提供了便利。隨著信息技術(shù)的發(fā)展，樹形結(jié)構(gòu)數(shù)據(jù)的應(yīng)用范圍還將不斷擴(kuò)大[2]。本文提出一種基于分段式數(shù)字存儲(chǔ)的樹形數(shù)據(jù)存儲(chǔ)方法，旨在提高樹形數(shù)據(jù)的存儲(chǔ)和查詢效率。

1 樹形結(jié)構(gòu)支持的操作方式

樹形結(jié)構(gòu)是常見的非線性數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于各種軟件開發(fā)和數(shù)據(jù)處理中。樹形結(jié)構(gòu)能夠有效地表示具有層次關(guān)系的數(shù)據(jù)，如文件系統(tǒng)、組織架構(gòu)、XML文檔等。樹形結(jié)構(gòu)的存儲(chǔ)方式主要有兩種，一是使用特殊連接字符對(duì)字符串進(jìn)行連接，二是在子節(jié)點(diǎn)的節(jié)點(diǎn)信息中存儲(chǔ)父節(jié)點(diǎn)以及兄弟節(jié)點(diǎn)ID的方式[3]。

第一種方式的操作速度快，但使用存儲(chǔ)空間很多，另外當(dāng)層級(jí)多時(shí)，會(huì)造成節(jié)點(diǎn)ID的字符串很長，在一些小型數(shù)據(jù)庫中可能會(huì)出現(xiàn)超出字段長度的限制[4]。第二種方式把父節(jié)點(diǎn)存在子節(jié)點(diǎn)信息中是參考了程序設(shè)計(jì)中樹對(duì)象定義的方式進(jìn)行存儲(chǔ)。當(dāng)在程序中采用這種存儲(chǔ)方式，因訪問內(nèi)存的速度很快，所以不存在性能問題。但是當(dāng)使用數(shù)據(jù)庫進(jìn)行存儲(chǔ)數(shù)據(jù)，因?yàn)樵L問數(shù)據(jù)消耗時(shí)間較長，當(dāng)樹節(jié)點(diǎn)多的時(shí)候，性能會(huì)成為一個(gè)瓶頸[5]。

采用樹形結(jié)構(gòu)進(jìn)行操作，主要包含以下幾種方式：

（1） 父節(jié)點(diǎn)/子節(jié)點(diǎn)查詢。

（2） 在樹形中插入節(jié)點(diǎn)。

（3） 在樹形中刪除節(jié)點(diǎn)。

（4） 在樹形中移動(dòng)節(jié)點(diǎn)。

（5） 檢索。包含查詢同級(jí)節(jié)點(diǎn)，下級(jí)節(jié)點(diǎn)，上級(jí)節(jié)點(diǎn)以及子節(jié)點(diǎn)在樹中所處的路徑。下文會(huì)就新的存儲(chǔ)方法在以上5種操作的實(shí)現(xiàn)以及性能進(jìn)行分析。

2 常見的存儲(chǔ)方式

樹形結(jié)構(gòu)的數(shù)據(jù)在數(shù)據(jù)表中的存儲(chǔ)，主要是采用特殊字段存儲(chǔ)節(jié)點(diǎn)之間的關(guān)系。我們經(jīng)常采用的存儲(chǔ)方式有以下兩種。以下以組織架構(gòu)圖1為例，介紹兩種常見的樹形結(jié)構(gòu)存儲(chǔ)方式。

2.1 采用分隔符存路徑

每個(gè)節(jié)點(diǎn)數(shù)據(jù)中均增加一個(gè)字符串，其中包含父級(jí)路徑加上子節(jié)點(diǎn)的標(biāo)組成，其中分隔符用不會(huì)出現(xiàn)在樹節(jié)點(diǎn)標(biāo)識(shí)中的特殊字符，例如：._-等字符。例如：公司-研發(fā)部-后端-Java組 用來表示當(dāng)前部門在公司的研發(fā)部下包含了一個(gè)子部門為后端，Java組處于后端子部門的下面。存儲(chǔ)的數(shù)據(jù)庫記錄如表1 所示：

這種方式進(jìn)行存儲(chǔ)在操作時(shí)非常簡單，但是采用字符串進(jìn)行存儲(chǔ)占用的存儲(chǔ)空間比較多，且檢索時(shí)采用的是文本比對(duì)速度比數(shù)字比對(duì)稍慢。

基于目前存儲(chǔ)設(shè)備的價(jià)格大幅下降，占用存儲(chǔ)空間的成本影響也比較小，檢索速度在數(shù)據(jù)庫中一般采用B樹或B+樹和檢索數(shù)字是同一級(jí)別，只是比數(shù)字檢索稍慢一些，所以是一種比較優(yōu)秀的存儲(chǔ)方式。

2.2 存儲(chǔ)引用 （parent_id，left_id，right_id）

在節(jié)點(diǎn)中存儲(chǔ)上級(jí)節(jié)點(diǎn)，左節(jié)點(diǎn)，右節(jié)點(diǎn)的標(biāo)識(shí)，在某些場景下如果不需要排序則不用存儲(chǔ)左右節(jié)點(diǎn)。數(shù)據(jù)如表2所示：

這種存儲(chǔ)方式的優(yōu)點(diǎn)是進(jìn)行插入節(jié)點(diǎn)操作時(shí)速度非?？?，并且占用的存儲(chǔ)空間比較少。但是在刪除節(jié)點(diǎn)，移動(dòng)節(jié)點(diǎn)以及檢索時(shí)，需要進(jìn)行循環(huán)查找到對(duì)應(yīng)的數(shù)據(jù)，多次對(duì)數(shù)據(jù)庫進(jìn)行操作，速度比采用分隔符進(jìn)行存儲(chǔ)要慢比較多。這種方式適用于存儲(chǔ)空間比較小的設(shè)備，例如某些Android外設(shè)、IOT設(shè)備等。

3 使用定長數(shù)字分段存儲(chǔ)

基于以上存儲(chǔ)方式，提出一種新方案用于存儲(chǔ)樹形數(shù)據(jù)結(jié)構(gòu)。首先采用數(shù)字存儲(chǔ)節(jié)點(diǎn)之間的關(guān)系，其次，這數(shù)字要描述了節(jié)點(diǎn)的完整信息。該方法將一個(gè)數(shù)字分為三段，分別表示父節(jié)點(diǎn)ID、節(jié)點(diǎn)ID和子節(jié)點(diǎn)ID。在本文中會(huì)把節(jié)點(diǎn)ID加粗，以用來和父級(jí)ID區(qū)分開。子節(jié)點(diǎn)ID為整個(gè)數(shù)字在節(jié)ID后的數(shù)值，例如：1.1.2.0.0.0.0.0， 父節(jié)點(diǎn)ID為1.1，節(jié)點(diǎn)ID為2，剩余后面為子節(jié)點(diǎn)ID。因?yàn)樽庸?jié)點(diǎn)ID 均為0，也可以簡寫為1.1.2。

基于以上考慮，采用一個(gè)數(shù)字用于存儲(chǔ)樹，每個(gè)字節(jié)（8位二進(jìn)制）作為一級(jí)。一個(gè)32位的整型數(shù)可以用來存儲(chǔ)最多四級(jí)的樹，64位的長整型的數(shù)可以存今朝8級(jí)的樹形結(jié)構(gòu)，考慮到各種情況，我們可以調(diào)整每級(jí)所占的位數(shù)以達(dá)到不同的層級(jí)效果。數(shù)據(jù)存儲(chǔ)方式如表3所示：

如果用IP地址的方式表示，整個(gè)組織結(jié)構(gòu)存儲(chǔ)的IP如圖2所示：

這種方法進(jìn)行節(jié)點(diǎn)插入，可以快速找到父節(jié)點(diǎn)下直接子節(jié)點(diǎn)，在容量沒超過的情況下可以迅速地插入節(jié)點(diǎn)。刪除節(jié)點(diǎn)時(shí)只需要根據(jù)ID進(jìn)行刪除即可，性能上是最優(yōu)的。

3.1 查詢父節(jié)點(diǎn)

父節(jié)點(diǎn)ID即為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)ID部分，直接通過數(shù)學(xué)運(yùn)算即可以取得，不用進(jìn)行數(shù)據(jù)庫查詢。

3.2 查詢子節(jié)點(diǎn)

查詢節(jié)點(diǎn)ID值在當(dāng)前節(jié)點(diǎn)值和下個(gè)節(jié)點(diǎn)值之間即可。例上面例子，需要查詢研發(fā)部下面的所有子節(jié)點(diǎn)，即查詢ID值在1.2.0.0.0.0.0.0和1.3.0.0.0.0.0.0之間的數(shù)值即可。

3.3 刪除節(jié)點(diǎn)以及子節(jié)點(diǎn)

根據(jù)上面的條件可以迅速查詢出所有子節(jié)點(diǎn)以及當(dāng)前節(jié)點(diǎn)，直接使用delete語句即可以一次操作刪除所有子節(jié)點(diǎn)：

3.4 添加節(jié)點(diǎn)

找到主節(jié)點(diǎn)下的直接子節(jié)點(diǎn)的最后一個(gè)，然后在此節(jié)點(diǎn)加1，即為要添加的節(jié)點(diǎn)的值。

如圖，如果要在公司下面添加一個(gè)部門：辦公室。首先找到所有直接子節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)，即研發(fā)部（1.2.0.0.0.0.0.0），下一個(gè)節(jié)點(diǎn)值為1.3.0.0.0.0.0.0這個(gè)值即為新節(jié)點(diǎn)的ID值。

3.5 移動(dòng)節(jié)點(diǎn)

移動(dòng)節(jié)點(diǎn)是把整個(gè)分枝按原來結(jié)構(gòu)全部移動(dòng)到另外一個(gè)節(jié)點(diǎn)下面。如把后端、Java、Python這三個(gè)節(jié)點(diǎn)按原來的關(guān)系移到公司這個(gè)節(jié)點(diǎn)下面。

步驟如下：

（1） 找到公司可用的子節(jié)點(diǎn)ID。根據(jù)圖公司下面直接子節(jié)點(diǎn)的最后一個(gè)為1.2，把節(jié)點(diǎn)ID加1為新的節(jié)點(diǎn)ID：1.3。

（2） 把值從1.2.2.0.0.0.0.0改成1.3。 后端的值變?yōu)?.3.0.0.0.0.0.0， Java 的為1.3.1.0.0.0.0.0， Python 為1.3.2.0.0.0.0.0。

一次數(shù)據(jù)操作即可，不用每個(gè)節(jié)點(diǎn)進(jìn)行修改。

這種樹形的檢索操作是最快的，比前面兩種方式均要快，直接使用了數(shù)字型的唯一索引進(jìn)行檢索。進(jìn)行節(jié)點(diǎn)插入以及移動(dòng)節(jié)點(diǎn)，比采用分隔符的方式要慢些，存儲(chǔ)使用的空間最少。

當(dāng)樹形結(jié)構(gòu)改動(dòng)較少，主要是進(jìn)行查詢時(shí)，這種方式整體性能最好。

4 定長數(shù)字分段存儲(chǔ)的擴(kuò)展

上面的采用數(shù)字進(jìn)行存儲(chǔ)有自己的缺點(diǎn)：

每個(gè)節(jié)點(diǎn)下的子節(jié)點(diǎn)是有限制的，如果使用1個(gè)字節(jié)進(jìn)行存儲(chǔ)，那么只能有254個(gè)子節(jié)點(diǎn)，并且使用64位長整型進(jìn)行存儲(chǔ)時(shí)，最多只能存儲(chǔ)8級(jí)的樹。另外一種情況就是子節(jié)點(diǎn)的數(shù)量過多的時(shí)候無法進(jìn)行存儲(chǔ)。

針對(duì)這種情況，我們可以把這種固定分組的方式改成動(dòng)態(tài)分配的方式。

針對(duì)定長方法的局限性，本文對(duì)其進(jìn)行擴(kuò)展，提出一種動(dòng)態(tài)分配數(shù)據(jù)位的方式。以適應(yīng)更多種情形，根據(jù)節(jié)點(diǎn)數(shù)量使用不同位數(shù)表示節(jié)點(diǎn)值。

假設(shè)節(jié)點(diǎn)數(shù)為n，則用位數(shù)m = ceil（log2 （n + 2）） +1 ，例如有兩個(gè)節(jié)，則使用3位二進(jìn)制位來表示，最后一位為1用來區(qū)分節(jié)點(diǎn)。

例如公司節(jié)點(diǎn)為根節(jié)點(diǎn)，根據(jù)公式算，m = 3，對(duì)應(yīng)的值為 011，最后一位用作標(biāo)識(shí)，這是第一個(gè)節(jié)點(diǎn)。公司下有兩個(gè)部門，依據(jù)公式，m=3，對(duì)應(yīng)的值依次為011，101，則財(cái)務(wù)的ID是011011，研發(fā)部為011101，整個(gè)樹的結(jié)構(gòu)如圖3所示。

動(dòng)態(tài)規(guī)劃的方法和固定使用一個(gè)字節(jié)作為一級(jí)的方式類似，不同處如下：

（1） 使用位（bit）作為最小存儲(chǔ)單元而不是byte，如果一級(jí)節(jié)點(diǎn)少，最少可以使用3位（bit）進(jìn)行存儲(chǔ)，這樣增加了層級(jí)關(guān)系。

（2） 每級(jí)使用的位數(shù)是動(dòng)態(tài)調(diào)整的，如一父節(jié)點(diǎn)下的子節(jié)點(diǎn)多的話，可以規(guī)劃更多的位數(shù)用于存儲(chǔ)。如果節(jié)點(diǎn)達(dá)到65534，則可以用兩個(gè)字節(jié)（即16位）進(jìn)行存儲(chǔ)。如果有更多，還可以規(guī)劃出更多位數(shù)進(jìn)行存儲(chǔ)。

在樹的操作，類似于定長分段存儲(chǔ)的方式，規(guī)劃規(guī)劃法的算法的計(jì)算會(huì)復(fù)雜一些，整體性能會(huì)有一定的下降，但是在檢索的時(shí)候，性能是一致的。

4.1 查找父節(jié)點(diǎn)

因?yàn)楦腹?jié)點(diǎn)肯定比當(dāng)前節(jié)點(diǎn)小，因此我們只需要從ID小于當(dāng)前id值的節(jié)點(diǎn)中進(jìn)行搜索，當(dāng)節(jié)點(diǎn)ID和當(dāng)前值進(jìn)行與操作后值還等于節(jié)點(diǎn)ID，則節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，其中數(shù)值最大的一個(gè)為直接父節(jié)點(diǎn)：

4.2 查詢子節(jié)點(diǎn)

查詢節(jié)點(diǎn)ID值在當(dāng)前節(jié)點(diǎn)值和下個(gè)節(jié)點(diǎn)值之間即可。例上面例子，需要查詢研發(fā)部下面的所有子節(jié)點(diǎn)，即查詢ID值在01110100和01111100之間的數(shù)值即可：

4.3 刪除節(jié)點(diǎn)以及子節(jié)點(diǎn)

同上，直接刪除當(dāng)前節(jié)點(diǎn)值和下個(gè)節(jié)點(diǎn)值之間的節(jié)點(diǎn)即可：

4.4 添加節(jié)點(diǎn)

在動(dòng)態(tài)規(guī)劃時(shí)，如果添加節(jié)點(diǎn)所處的父級(jí)節(jié)點(diǎn)子節(jié)點(diǎn)數(shù)超過限制時(shí)，需要對(duì)所有子節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)調(diào)整。

添加節(jié)點(diǎn)的同定長方式類似，但是當(dāng)節(jié)點(diǎn)數(shù)量滿的時(shí)候需要進(jìn)行動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的長度。如上例，公司下面有兩個(gè)節(jié)點(diǎn)，這是三個(gè)位值進(jìn)行存儲(chǔ)的最大數(shù)量，當(dāng)要往公司節(jié)點(diǎn)下再增加節(jié)點(diǎn)的時(shí)候，需要?jiǎng)討B(tài)調(diào)整所有子節(jié)點(diǎn)。

4.5 移動(dòng)節(jié)點(diǎn)

需要找出所有子節(jié)點(diǎn)，然后把原來節(jié)點(diǎn)的父節(jié)點(diǎn)ID替換成新的父節(jié)點(diǎn)ID即可。

5 總結(jié)

通過以上內(nèi)容，我們可以根據(jù)不同的場景使用不同的樹形實(shí)現(xiàn)方式。使用數(shù)組分段存儲(chǔ)有更好的查詢性能以及需要更少的存儲(chǔ)空間。

本文提出了一種基于分段式數(shù)字存儲(chǔ)的樹形數(shù)據(jù)存儲(chǔ)方法，并通過實(shí)驗(yàn)驗(yàn)證了其有效性。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效提高樹形數(shù)據(jù)的存儲(chǔ)和查詢效率，尤其適用于節(jié)點(diǎn)關(guān)系較為穩(wěn)定的場景。未來工作將進(jìn)一步研究該方法在不同應(yīng)用場景下的性能表現(xiàn)，并探索更加高效的樹形數(shù)據(jù)存儲(chǔ)方案。