将包含大量文件的目录排序到子目录中的方法是什么？

Question

使包含大量文件的目录易于管理的一种方法是将文件排序到以文件名中的渐进字符命名的子目录中。

例如：

-a8debcdcf0d2302ccde5a43bb1fb385e81098342.jpg
- 91ff48de8cfc6468bdc2115cf87cfb6547eee713.jpg
-99d002e2065cdf02bd6d04bf29a8230564719b76.jpg
...

上述文件按类似于以下的方式排序到子目录中：

- A/
  - 8/
    -a8debcdcf0d2302ccde5a43bb1fb385e81098342.jpg
- 9/
  - 1/
    - 91ff48de8cfc6468bdc2115cf87cfb6547eee713.jpg
  - 9/
    -99d002e2065cdf02bd6d04bf29a8230564719b76.jpg

此方法有几种变体，例如使用不同数量的字符来命名子目录或使用哈希或其他算法来确定每个文件的路径。

这种组织文件的方法有正式名称吗？

Answer 1

我一直将其称为哈希分块。

对于这样的结构，有几点需要注意：

• 每个目录都会创建一个 inode。如果你对每个字符进行分块，单个文件可能会导致创建 33 个 inode。这样，在空间用完之前，你就会用完 inode。
• 如果您按组进行分块（例如，前 n 个字符，然后是第二个 n 个字符），则保持集合足够小，您不会强制 inode 扩展，这会减慢查找速度。
• 如果您的哈希值非常随机，那么第 3 阶和进一步的顺序块实际上永远不会有兄弟块，因此您可能能够像... 1234/5678/901234567890 等进行分块并保持您的 inode 较小。

Answer 2

似乎它只是被称为“散列目录结构”，例如http://michaelandrews.typepad.com/the_technical_times/2009/10/creating-a-hashed-directory-structure.html：

如何存储大量文件，同时又能保持较高的访问性能？一种解决方案是文件名哈希处理。

Answer 3

这被称为 B-树（与二叉树无关）。