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

十多年來,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序列化示例

  value的unicode children數量 end children數量/(end<<15) 最終結果
根節點 0x0000 2 0 0x0002 0x00020000
b節點 0x0062 1 0 0x0001 0x00010062
e節點 0x0065 0 1 0x8000 0x80000065

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種方法的存儲空間比較(單位:字節)

位數 方法 1 2 3 4 5 6
“/”分隔 19 299 3999 49999 599999 6999999
Tree 44 444 4444 44444 444444 4444444

由表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的堆內存有比較高的要求;另外,使用“/”拼接時,查找會比較麻煩。

作者:牛寧昌

來源:宜信技術學院

【精選推薦文章】

如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!!

想要讓你的商品在網路上成為最夯、最多人討論的話題?

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

想知道最厲害的台北網頁設計公司推薦台中網頁設計公司推薦專業設計師"嚨底家"!!