algorithm - 在文件系统中存储字符串+描述

Question

我有超过 1 亿个字符串要存储在文件系统中。与字符串 (~255Chars utf8) 一起，将有两个日期和一些定义其属性的整数值。

我可以将它们放在一个 CSV 文件中，但它会很大。我可以将几个较小的 CSV 文件放在子目录中以使其更快，或者我可以简单地为每个字符串创建一个文件并将它们存储在目录树中。

我如何知道哪种解决方案更快、更容易维护/开发？我什至不知道我的琴弦有多稀疏；也许我有 5000 万个以相同的字符开头，从而使树不那么平衡。

现在我想我可以用前 5 个字符创建一个目录结构，然后将 csv 文件放在每个目录中。例如。字符串 "I don't know what I'm doing"-> "Idontknowwhatimdoing"进入

/i/d/o/n/t/list.csv

有更好的主意吗？我不能使用 Db。我正在使用 java 来存储并使用 php 来读取文件系统，如果这有什么不同的话。

Answer 1

• 带有索引的数据库会更理想。
• 以下是固定记录大小的警告。

如果您的字符串是 ASCII，您只需要一个字节来定义每个字符(与 UTF8 相比，其中某些字符可能编码为 4 个字节)，那么您可以只使用每个记录的固定大小的平面文件。如果您的字符串确实需要 UTF8，则选择固定大小编码而不是可变大小编码，或者只找到最大的字符串并将其用作固定大小。

256 字节(字符串)+ 8 字节(日期)+ 8 字节(日期)+ 8 字节(整数)+ 8 字节(整数)= 每条记录 288 字节

1 亿(条目)* 288 字节(记录大小)= 28.8 GB

访问这样一个巨大的文件意味着您必须使用内存映射文件，其中操作系统只负责将您当前正在访问的文件部分放入内存。

如果您的字符串未排序，您将不得不这样做，一些合并排序变体可能会很有用，您可以对 1 亿个字符串(可能是 100 万个分区)的 block 进行完全排序，然后将这 100 个排序的分区合并在一起得到最终的排序列表。

如何搜索字符串将是一个二进制搜索 log N，对于 1 亿条记录，这将是 ~27 次 IO 读取。