大量文件名记录的树形结构存储

共计 4115 个字符，预计需要花费 11 分钟才能阅读完成。

十多年来，NAS 中已经存在的目录和文件达到 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;
    }

字段说明：

value：该节点表示的字符，当 Node 表示根节点时，value 无值。
children：该节点的所有子节点，初始化为长度为 0 的数组。
end：标记节点是否是结束节点。0 不是；1 是。叶子节点肯定是结束节点。默认非结束节点。

    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 的最后一个元素，并返回新创建的节点。

    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);

操作说明：

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 方法的参数进行遍历。

    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 的堆内存有比较高的要求；另外，使用“/”拼接时，查找会比较麻烦。

作者：牛宁昌

来源：宜信技术学院

一、引言

二、涉及的数据结构

2.1 Node 的结构

2.2 Node 的操作

2.3 Tree 的结构

2.4 Tree 的操作

三、树的构建

四、树的查询

五、树的遍历

5.1 Found 的结构

5.2 如何遍历

六、序列化与反序列化

6.1 序列化

6.1.1 节点的 value

6.1.2 节点的 children 数量

6.1.3 节点的 end

6.1.4 树的序列化过程

6.2 反序列化

七、讨论

7.1 关于节省空间

7.2 关于时间

7.3 关于理想化假设

7.4 关于其他压缩方法

Just My Socks（注册教程内含优惠码）