1
$\begingroup$

So after learning about DFS and BFS yesterday in my class I was curious as to how is scanning on various file system being done. I spent quite a bit of time trying to look for some references on the web, but so far I have failed in doing so. I'm assuming that either DFS or BFS are behind the core "scanning" in some file systems.

There's also Dijkstra's algorithm but as I'm not even sure if file system is a weighted or unweighted tree (ie. number of files being the weight or file size) it's hard to say if it's useful or not because I believe that BFS would be better than Dijkstra if it's unweighted tree.

I hope that someone could clear this up as there just isn't anything specific about it on the web.

$\endgroup$
  • $\begingroup$ Wait a while. You will learn about dictionary datastructures, and they can be used to create indices which enable fast search. Simple tree traversal doesn't cut it. $\endgroup$ – Raphael May 25 '16 at 9:29
5
$\begingroup$

For most file systems, a directory lists its entries in a certain order, so reading ("scanning") an individual directory will return its entries in that order.

But when it comes to scanning whole directory structures, there is no such thing as "core scanning": there isn't a common implementation for that.

I think depth-first is more popular; e.g. GNU find only supports depth-first scanning. This may be due to depth-first scanning consuming less memory on average; it can't be due to breath-first search being harder to implement, as it's just a matter of treating your list of files to visit as a queue rather than a stack.

$\endgroup$
  • $\begingroup$ Don't filesystems have indices/tables to speed up searches? $\endgroup$ – Raphael May 25 '16 at 9:30
  • $\begingroup$ Raphael: Rarely. On Unix/Linux, fast searching (locate) is traditionally provided by a separate database built by a nightly filesystem scan with find. $\endgroup$ – reinierpost May 25 '16 at 10:24
  • $\begingroup$ 1) But surely find does not do a linear scan on the the actual data on the disk? I guess table of contents or inodes are what I had in mind. 2) According to WIkipedia, ext4 uses Htree indices. $\endgroup$ – Raphael May 25 '16 at 11:50
  • $\begingroup$ Thanks for the answers. I'd also like to know if there are any books or theses about that or similar topic. I will have to make a short presentation soon about something that is connected with graphs (Dijkstra's usage in GPS etc.) and I thought that I could do something with directory scanning and DFS/BFS. $\endgroup$ – brajevicm May 25 '16 at 13:25
  • $\begingroup$ Raphael: find reads directories, which are files that contain a mapping from filenames to pointers to files (inodes). So it reads a pointer structure consisting of files of a special type. $\endgroup$ – reinierpost May 25 '16 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.