QFile 搜索性能

Question

看起来QFile在处理常规文件（不是特殊的 Linux I/O 设备文件）时是随机访问的，这意味着查找操作的时间复杂度为 O(1)。

但是，我无法确认这一点。在一般情况下，当跳跃到一个文件中的特定位置（写或读），确实std::fstream和QFile提供固定时间的运行时间复杂性？

Answer 1

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

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

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

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