2 ms·
ext4 uses btrees for the directory index, so accessing files by name is just as fast as manually splitting it into a prefix-based directory tree. Searching by
by the8472 9y ago
ext4 uses btrees for the directory index, so accessing files by name is just as fast as manually splitting it into a prefix-based directory tree.
Searching by filename on the other hand can be much faster with a prefix tree because directories only allow linear scans, not range-based ones.
- ngrilly 9y agoI'm missing something. What difference do you see between "accessing files by name" and "searching by filename"?
- the8472 9y agof = open("/path/to/file"); // do something with file vs. d = opendir("path/to") while((dent = readdir(d)) != NULL) { if(!dent.name.startsWith("file")) continue; // do something with first matched entry } The former is O(log n) on ext4, O(n) on older filesystems that use flat lists. The latter is always O(n)
- ngrilly 9y agoUnderstood. Thanks ;-)