如何使用数据库存储文件目录结构？

发表于 2024-07-19 分类于 tech ， DBMS 本文字数： 1.6k 阅读时长 ≈ 6 分钟

序言

如果要用数据库保存文件目录的结构，应该使用哪种数据库？ —— 要么 NoSQL，要么 RDBMS。选取 NoSQL，应该选择支持树形结构的；选取 RDBMS，重点在于表的设计和查询操作。

这个问题的关键在于：我们要对数据库中的目录结构做何种操作？ 显然，这些操作本质上是对文件系统上文件的操作。

操作1：单个文件/目录的增删改查，即拷贝、删除、剪切某个文件/目录；
操作2：递归遍历某个目录；

只有考虑了这两点，才能设计出高效的方案。本文给出了 NoSQL 和 RDBMS 的方案，重点在于后者。另外，本文还探讨了使用 JSON 的方案。

NoSQL

选项如下：

使用 HDFS 这种文件系统作为数据库；
使用图数据库，比如 Neo4j；

没有必要为了存储目录结构而引入新的组件。

RDBMS

以下的 Item 表都代表目录项，即目录树中的节点。

树形表示

1、保存父节点指针：

CREATE TABLE Item (
  id INT AUTO_INCREMENT PRIMARY KEY, 
  name VARCHAR(255) NOT NULL COMMENT '文件名', 
  type TINYINT NOT NULL COMMENT '0 表示文件，1 表示目录', 
  parent_id INT NOT NULL DEFAULT -1 COMMENT '父节点 id'
);

2、保存子节点指针列表（如何处理 children 字段也是个麻烦事）：

CREATE TABLE Item (
  id INT AUTO_INCREMENT PRIMARY KEY, 
  name VARCHAR(255) NOT NULL COMMENT '文件名',
  type TINYINT NOT NULL COMMENT '0 表示文件，1 表示目录', 
  children VARCHAR(1023) NOT NULL DEFAULT "" COMMENT '逗号分隔的子节点 id'
);

这两种表示法本质上都是有向图的邻接表。无论是操作 1 还是操作 2 ，都要遍历一张表多次，效率极低。

使用文件路径作为索引

由于文件路径可以唯一定位一个文件，那么文件路径也可以作为唯一索引。

这种方法被称为 Materialized Paths。

CREATE TABLE Item (
  id INT AUTO_INCREMENT PRIMARY KEY, 
  name VARCHAR(255) NOT NULL COMMENT '文件名', 
  type TINYINT NOT NULL COMMENT '0 表示文件，1 表示目录', 
  path VARCHAR(1023) NOT NULL COMMENT '文件路径'
);
CREATE INDEX path_idx ON Item(path);

实际使用时，没必要令 path 为唯一索引，因为：（1）唯一索引效率太低；（2）path 太长，不适合作为主键。因此，path 作为一个普通索引即可。

对于操作 1：

增删查改文件，触发索引，时间复杂度为 $O(\log n)$：

1	SELECT * FROM Item WHERE path = '路径';

新增、查询目录，时间复杂度为 $O(\log n)$，与操作文件相同。
修改目录，即改名操作，时间复杂度为 $O(n)$，因为需要修改所有子目录项的路径。
删除目录，时间复杂度为 $O(n)$，因为需要删除所有子目录项。

对于操作 2：只需要遍历一次索引表，而且由于最左前缀原则，不需要全表遍历，效率很高。

综上，使用文件路径作为索引的方式效率很高。

Nested Sets

这种数据结构适合静态数据 —— 只是为了高效查询设计的，不适合修改。

CREATE TABLE Item (
  id INT AUTO_INCREMENT PRIMARY KEY, 
  name VARCHAR(255) NOT NULL COMMENT '文件名', 
  type TINYINT NOT NULL COMMENT '0 表示文件，1 表示目录', 
  lft INT NOT NULL, 
  rgt INT NOT NULL
);

Nested Sets 有如下特点：

每一个节点有 lft 和 rgt 属性，记录区间左端点和右端点。比如 id 为 1 的节点的区间是 (1, 22)；
每一个节点的所有子节点的区间，都是它的区间的子区间。因此，一个区间对应一棵子树。比如 id 为 1 的节点的所有子节点的区间，一定是 (1, 22) 的子区间；
同层节点的区间不相交。比如第二层的区间为 (2, 9)、 (10, 15)、 (16, 21)；

这种设计的优点在于操作 2 是高效的，考虑递归遍历 id 为 1 的子树：

1	SELECT * FROM Item WHERE lft > 1 AND rgt < 22;

对于静态结构，所有节点的 lft 和 rgt 都是事先计算好的，直接批量插入数据库即可。但是要执行操作 1，即动态地修改有关节点的 lft 和 rgt ，其代价可想而知。

JSON

目录是一种结构化对象，并且是递归定义的。JSON 同理。因此，可以用 JSON 表示目录。

JSON 本质上是字符串，因此用任何数据库都可以存储，直接存在文件中亦可。

在这种情形下，对于目录结构的两种操作和文件系统的操作一致，因此操作的时间复杂度不高。而且操作都是在内存中进行的，故性能不错。

这种情况的缺点在于，当目录树很大时，（1）字符串和对象的转换时间增加；（2）内存占用增加；（3）客户端和服务器、服务器和数据库之间的网络开销过大。

第三点原因是 C/S 架构中 JSON 方案主要的弊端，因为它不如 RDBMS 方案：

如果目录树很小，那么使用 RDBMS 和 JSON 都可以；
如果目录树很大，且查询多、修改少，那么 RDBMS 更好；
如果目录树很大，且修改频繁，尽管 JSON 在内存中操作速度更快，但网络通信频繁，且每个网络包都很大，导致带宽占用大，总体效果不一定优于 RDBMS。

但是，如果是一个程序的本地数据库，JSON 无疑是最好的选择。

总结

如何用 RDBMS 存储树形数据（比如文件目录）这一问题，实际上在 2005 到 2010 间就讨论过了，并且得出了完善的结论。从今天的角度看，NoSQL 的兴起似乎掩盖了本文探讨的问题的本质，让我对于该问题的探索走了弯路。

同时，数据库也是一个组件。正如我们不会为了存储目录结构而引入一个新的 NoSQL 数据库，如果只是要存储目录结构，我们甚至没必要引入数据库，直接使用 JSON 文件即可。

序言