大量文件名記錄的樹形結構存儲

十多年來，NAS中已經存在的目錄和文件達到10億之多，在設計和開發備份系統的過程中碰到了很多挑戰，本文將分享大量文件名記錄的樹形結構存儲實踐。

一、引言

既然是定期備份，肯定會有1次以上的備份。對于一個特定目錄，每次備份時都要與上次備份時進行比較，以期找出哪些文件被刪除了，又新增了哪些文件，這就需要每次備份時把該目錄下的所有文件名進行保存。我們首先想到的是把所有文件名用特定字符進行拼接后保存。由于我們使用了MySQL保存這些信息，當目錄下文件很多時，這種拼接的方式很可能超出MySQL的Blob長度限制。根據經驗，當一個目錄有大量文件時，這些文件的名稱往往是程序生成的，有一定規律的，而且開頭一般是重復的，于是我們想到了使用一種樹形結構來進行存儲。

例如，一個有abc、abc1、ad、cde 4個文件的目錄對應的樹如圖1所示。

圖1 樹形結構示例

圖1中，R表示根節點，青色節點我們稱為結束節點，從R到每個結束節點的路徑都表示一個文件名?？梢栽跇渲胁檎沂欠窈心硞€文件名、遍歷樹中所有的文件名、對樹序列化進行保存、由序列化結果反序列化重新生成樹。

二、涉及的數據結構

注意：我們使用java編寫，文中涉及語言特性相關的知識點都是指java。

2.1 Node的結構

包括根節點在內的每個節點都使用Node類來表示。代碼如下：

    class Node {
        private char value;
        private Node[]children = new Node[0];
        private byte end = 0;
    }

字段說明：

• value：該節點表示的字符，當Node表示根節點時，value無值。
• children：該節點的所有子節點，初始化為長度為0的數組。
• end：標記節點是否是結束節點。0不是；1是。葉子節點肯定是結束節點。默認非結束節點。

2.2 Node的操作

    public Node(char v);
    public Node findChild(char v);
    public Node addChild(char v);

操作說明：

• Node：構造方法。將參數v賦值給this.value。
• findChild：查找children中是否含有value為v的子節點。有則返回子節點，沒有則返回null。
• addChild：首先查找children中是否已經含有value為v的子節點，如果有則直接將查到的子節點返回；否則創建value為v的節點，將children的長度延長1，將新創建的節點作為children的最后一個元素，并返回新創建的節點。

2.3 Tree的結構

    class Tree {
        public Node root = new Node();
    }

字段說明：Tree只含有root Node。如前所述，root的value無值，end為0。初始時的children長度為0。

2.4 Tree的操作

    public void addName(String name) ;
    public boolean contain(String name);
    public Found next(Found found);
    public void writeTo(OutputStream out);
    public static Tree readFrom(InputStream in);

操作說明：

• addName：向樹中增加一個新的文件名，即參數name。以root為起點，name中的每個字符作參數調用addChild，返回值又作為新的起點，直到name中的全部字符添加完畢，對最后一次調用addChild的返回值標記為結束節點。
• contain：查詢樹中是否含有一個文件名。
• next：對樹中包含的所有文件名進行遍歷，為了使遍歷能夠順利進行，我們引入了新的類Found，細節會在后文詳述。
• writeTo：將樹寫入一個輸出流以進行持久化。
• readFrom：此方法是靜態方法。從一個輸入流來重新構建樹。

三、樹的構建

在新建的Tree上調用addName方法，將所有文件名添加到樹中，樹構建完成。仍然以含有abc、abc1、ad、cde 四個文件的目錄為例，對樹的構建進行圖示。

圖2 樹的構建過程

圖2中，橙色節點表示需要在該節點上調用addChild方法增加子節點，同時addChild的返回值作為新的橙色節點。直到沒有子節點需要增加時，把最后的橙色節點標記為結束節點。

四、樹的查詢

查找樹中是否含有一個某個文件名，對應Tree的contain方法。在圖2中的結果上分別查找ef、ab和abc三個文件來演示查找的過程。如圖3所示。

圖3 樹的查詢示意圖

圖3中，橙色節點表示需要在該節點上調用findChild方法查找子節點。

五、樹的遍歷

此處的遍歷不同于一般樹的遍歷。一般遍歷是遍歷樹中的節點，而此處的遍歷是遍歷根節點到所有結束節點的路徑。

我們采用從左到右、由淺及深的順序進行遍歷。我們引入了Found類，并作為next方法的參數進行遍歷。

5.1 Found的結構

    class Found {    
        private String name;
        private int[] idx ;
    }

為了更加容易的說明問題，在圖1基礎上進行了小小的改造，每個節點的右下角增加了下標，如圖4。

圖4 帶下標的Tree

對于abc這個文件名，Found中的name值為“abc”，idx為{0，0，0}。

對于abc1這個文件名，Found中的name值為“abc1”，idx為{0，0，0，0}。

對于ad這個文件名，Found中的name值為“ad”，idx為{0，1}。

對于cde這個文件名，Found中的name值為“cde”，idx為{1，0，0}。

5.2 如何遍歷

對于圖4而言，第一次調用next方法應傳入null，則返回第一個結果，即abc代表的Found；繼續以這個Found作為參數進行第二次next的調用，則返回第二個結果，即abc1代表的Found；再繼續以這個Found作為參數進行第三次next的調用，則返回第三個結果，即ad所代表的Found；再繼續以這個Found作為參數進行第四次next的調用，則返回第四個結果，即cde所代表的Found；再繼續以這個Found作為參數進行第五次調用，則返回null，遍歷結束。

六、序列化與反序列化

6.1 序列化

首先應該明確每個節點序列化后應該包含3個信息：節點的value、節點的children數量和節點是否為結束節點。

6.1.1 節點的value

雖然之前所舉的例子中節點的value都是英文字符，但實際上文件名中可能含有漢字或者其他語言的字符。為了方便處理，我們沒有使用變長編碼。而是直接使用unicode碼。字節序采用大端編碼。

6.1.2 節點的children數量

由于節點的value使用了unicode碼，所以children的數量不會多于unicode能表示的字符的數量，即65536。children數量使用2個字節。字節序同樣采用大端編碼。

6.1.3 節點的end

0或1可以使用1位（1bit）來表示，但java中最小單位是字節。如果采用1個字節來表示end，有些浪費空間，其實任何一個節點children數量達到65536/2的可能性都是極小的，因此我們考慮借用children數量的最高位來表示end。

綜上所述，一個節點序列化后占用4個字節，以圖4中的根節點、value為b的節點和value為e的節點為例：

表1 Node序列化示例

6.1.4 樹的序列化過程

對樹進行廣度遍歷，在遍歷過程中需要借助隊列，以圖4的序列化為例進行說明：

圖5 對圖4的序列化過程

6.2 反序列化

反序列化是序列化的逆過程，由于篇幅原因不再進行闡述。值得一提的是，反序列化過程同樣需要隊列的協助。

七、討論

7.1 關于節省空間

為方便討論，假設目錄下的文件名是10個阿拉伯數字的全排列，當位數為1時，目錄下含有10個文件，即0、1、2……8、9，當位數為2時，目錄下含有100個文件，即00、01、02……97、98、99，以此類推。

比較2種方法，一種使用“/”分隔，另一種是本文介紹的方法。

表2 2種方法的存儲空間比較（單位：字節）

由表2可見，當位數為4時，使用Tree的方式開始節省空間，位數越多節省的比例越高，這正是我們所需要的。

表中，使用“/”分隔時，字節數占用是按照utf8編碼計算的。如果直接使用unicode進行存儲，占用空間會加倍，那么會在位數為2時就開始節省空間。同樣使用“/”分隔，看起來utf8比使用unicode會更省空間，但實際上，文件名中有時候會含有漢字，漢字的utf8編碼占用3個字節。

7.2 關于時間

在樹的構建、序列化反序列化過程中，引入了額外的運算，根據我們的實踐，user CPU并沒有明顯變化。

7.3 關于理想化假設

最初我們就是使用了“/”分隔的方法對文件名進行存儲，并且數據庫的相應字段類型是Blob（Blob的最大值是65K）。在測試階段就發現，超出65K是一件很平常的事情。在不可能預先統計最大目錄里所有文件名拼接后的大小的情況下，我們采取了2種手段，一是使用LongBlob類型，另一種就是盡量減小拼接結果的大小，即本文介紹的方法。

即使使用樹形結構來存儲文件名，也不能夠保證最終結果不超出4G(LongBlob類型的最大值)，至少在我們實踐的過程并未出現問題，如果真出現這種情況，只能做特殊處理了。

7.4 關于其他壓縮方法

把文件名使用“/”拼接后，使用gzip等壓縮算法對拼接結果進行壓縮后再存儲，在節省存儲空間方面會取得更好的效果。但是在壓縮之前，拼接結果存在于內存，這樣對JVM的堆內存有比較高的要求；另外，使用“/”拼接時，查找會比較麻煩。

作者：牛寧昌

來源：宜信技術學院