189 8069 5689
十多年来，NAS中已经存在的目录和文件达到10亿之多，在设计和开发备份系统的过程中碰到了很多挑战，本文将分享大量文件名记录的树形结构存储实践。
创新互联公司长期为近1000家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为合肥企业提供专业的成都网站设计、成都网站制作、外贸网站建设，合肥网站改版等技术服务。拥有十载丰富建站经验和众多成功案例,为您定制开发。
既然是定期备份，肯定会有1次以上的备份。对于一个特定目录，每次备份时都要与上次备份时进行比较，以期找出哪些文件被删除了，又新增了哪些文件，这就需要每次备份时把该目录下的所有文件名进行保存。我们首先想到的是把所有文件名用特定字符进行拼接后保存。由于我们使用了MySQL保存这些信息，当目录下文件很多时，这种拼接的方式很可能超出MySQL的Blob长度限制。根据经验，当一个目录有大量文件时，这些文件的名称往往是程序生成的，有一定规律的，而且开头一般是重复的，于是我们想到了使用一种树形结构来进行存储。
例如，一个有abc、abc1、ad、cde 4个文件的目录对应的树如图1所示。
图1 树形结构示例
图1中，R表示根节点，青色节点我们称为结束节点，从R到每个结束节点的路径都表示一个文件名。可以在树中查找是否含有某个文件名、遍历树中所有的文件名、对树序列化进行保存、由序列化结果反序列化重新生成树。
注意：我们使用java编写，文中涉及语言特性相关的知识点都是指java。
包括根节点在内的每个节点都使用Node类来表示。代码如下：
class Node {
private char value;
private Node[]children = new Node[0];
private byte end = 0;
}字段说明：
public Node(char v);
public Node findChild(char v);
public Node addChild(char v);操作说明：
class Tree {
public Node root = new Node();
}字段说明：Tree只含有root Node。如前所述，root的value无值，end为0。初始时的children长度为0。
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);操作说明：
在新建的Tree上调用addName方法，将所有文件名添加到树中，树构建完成。仍然以含有abc、abc1、ad、cde 四个文件的目录为例，对树的构建进行图示。
图2 树的构建过程
图2中，橙色节点表示需要在该节点上调用addChild方法增加子节点，同时addChild的返回值作为新的橙色节点。直到没有子节点需要增加时，把最后的橙色节点标记为结束节点。
查找树中是否含有一个某个文件名，对应Tree的contain方法。在图2中的结果上分别查找ef、ab和abc三个文件来演示查找的过程。如图3所示。
图3 树的查询示意图
图3中，橙色节点表示需要在该节点上调用findChild方法查找子节点。
此处的遍历不同于一般树的遍历。一般遍历是遍历树中的节点，而此处的遍历是遍历根节点到所有结束节点的路径。
我们采用从左到右、由浅及深的顺序进行遍历。我们引入了Found类，并作为next方法的参数进行遍历。
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}。
对于图4而言，第一次调用next方法应传入null，则返回第一个结果，即abc代表的Found；继续以这个Found作为参数进行第二次next的调用，则返回第二个结果，即abc1代表的Found；再继续以这个Found作为参数进行第三次next的调用，则返回第三个结果，即ad所代表的Found；再继续以这个Found作为参数进行第四次next的调用，则返回第四个结果，即cde所代表的Found；再继续以这个Found作为参数进行第五次调用，则返回null，遍历结束。
首先应该明确每个节点序列化后应该包含3个信息：节点的value、节点的children数量和节点是否为结束节点。
虽然之前所举的例子中节点的value都是英文字符，但实际上文件名中可能含有汉字或者其他语言的字符。为了方便处理，我们没有使用变长编码。而是直接使用unicode码。字节序采用大端编码。
由于节点的value使用了unicode码，所以children的数量不会多于unicode能表示的字符的数量，即65536。children数量使用2个字节。字节序同样采用大端编码。
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 |
对树进行广度遍历，在遍历过程中需要借助队列，以图4的序列化为例进行说明：
图5 对图4的序列化过程
反序列化是序列化的逆过程，由于篇幅原因不再进行阐述。值得一提的是，反序列化过程同样需要队列的协助。
为方便讨论，假设目录下的文件名是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个字节。
在树的构建、序列化反序列化过程中，引入了额外的运算，根据我们的实践，user CPU并没有明显变化。
最初我们就是使用了“/”分隔的方法对文件名进行存储，并且数据库的相应字段类型是Blob（Blob的最大值是65K）。在测试阶段就发现，超出65K是一件很平常的事情。在不可能预先统计最大目录里所有文件名拼接后的大小的情况下，我们采取了2种手段，一是使用LongBlob类型，另一种就是尽量减小拼接结果的大小，即本文介绍的方法。
即使使用树形结构来存储文件名，也不能够保证最终结果不超出4G(LongBlob类型的最大值)，至少在我们实践的过程并未出现问题，如果真出现这种情况，只能做特殊处理了。
把文件名使用“/”拼接后，使用gzip等压缩算法对拼接结果进行压缩后再存储，在节省存储空间方面会取得更好的效果。但是在压缩之前，拼接结果存在于内存，这样对JVM的堆内存有比较高的要求；另外，使用“/”拼接时，查找会比较麻烦。
作者：牛宁昌
来源：宜信技术学院