c++ - QFile 寻道性能

Question

使用常规文件（不是特殊的 Linux I/O 设备文件）时， QFile似乎是随机访问，这意味着查找操作具有恒定时间复杂度 O(1)。

但是，我无法证实这一点。通常，当跳转到文件中的特定位置（用于写入或读取）时，是否std::fstream提供QFile恒定时间运行时间复杂度？

Answer 1

简短的回答是“是的，出于实际目的”。长答案是……这很复杂。

在文件流上查找最终会在底层文件描述符上调用 lseek()，其性能取决于内核。

运行时间取决于您使用的文件系统以及文件的大小。随着文件变大，随机搜索需要追逐更多级别的“间接”索引块。但即使对于高达 2^64 字节的文件，级别的数量也很少。

所以理论上，seek 大概是 O(log n); 但实际上，对于现代文件系统来说，它基本上是不变的。