Traversing a tree in multiple threads

Hello everyone, I want to share with the public some amount of information that it seemed to me difficult to find on the Internet.

What is a tree, look Wikipedia .


Fig.1 Example of a tree.

So, why would you ever need to bypass the tree in several streams? In my case, it was the need to search for files on disk. It is clear that physically the disk works in one stream, but nevertheless, multi-threaded file search can give acceleration in the case when a single stream searches for a file in a multi-level hierarchy, and the file you are looking for lies in the next folder with one level. Also, evidence of the relevance of multi-threaded search is its implementation in many successful commercial products. I do not exclude that other variants of the algorithm are possible, write in the comments.
')
To begin, I propose to consider the animation:



What's going on here? The whole essence of the algorithm is that:

1. The first stream bypasses the tree from the root to the depth along the “far left” path, i.e. always when moving inward turns to the left or in other words always selects the last child node.
2. In parallel, the first thread collects all the missing child nodes and sends them to the queue (or to the stack) where another thread takes them, the queue or stack must implement a multi-thread approach, and the algorithm repeats, replacing the root with the node just taken.
   
   In fact, the whole algorithm looks like this (one color - one stream):
   

In fact, the whole algorithm looks like this (one color - one stream):

Java software implementation

I give an example of code that might be useful to someone, I searched for it for a long time, but I did not find it:

import java.io.File; import java.util.concurrent.BlockingQueue; import java.util.concurrent.Executor; import java.util.concurrent.Executors; import java.util.concurrent.LinkedBlockingDeque; public class MultiThreadTreeWalker extends Thread { private static BlockingQueue<File> nodesToReview = new LinkedBlockingDeque<>(); private File f; public MultiThreadTreeWalker(File f) { this.f = f; } public MultiThreadTreeWalker() { } public static void main(String[] args) { Executor ex = Executors.newFixedThreadPool(2); MultiThreadTreeWalker mw = new MultiThreadTreeWalker(new File("C:\\")); mw.run(); for (int i = 0;i<2;i++) { ex.execute(new MultiThreadTreeWalker()); } } @Override public void run() { if (f != null) { //    reviewFileSystem(f); } else { try { while (true) { f = nodesToReview.take(); reviewFileSystem(f); } } catch (InterruptedException e) { e.printStackTrace(); } } } void reviewFileSystem(File f) { if (f == null) { return; } if (f.isFile()) { //  (+ ) System.out.println(" " + f.getName() + "   " + Thread.currentThread()); return; } File[] files = f.listFiles(); if (files.length != 0) { for (int i = 0; i < files.length - 1; i++) { nodesToReview.add(files[i]); //     } //       File last = files[files.length - 1]; reviewFileSystem(last); } } } 

Conclusion

As you can see, multithreading in Java can be implemented quite simply by means of BlockingQueue, a data structure that provides access of several streams to stored data.

In general, this is all, if in brief, write comments about what else there are ways or methods to bypass the tree, I would like to hear the opinion of the guru in this matter. Write questions, wishes.

Link to github . There is also a JavaFX search engine nearby, if someone wants to test, then I’ll only be happy.