Single big BST vs multiple smaller BSTs? Which is faster for search?
Searching among $N$ in a BST takes (roughly) $\log_2 N$ comparisons. So searching in $10^9 \approx 2^{30}$ takes around 30 comparisons. Searching in $10^6 \approx 2^{20}$ takes 20 comparisons. The cost of farming out the work to 1000 processors, collecting the results and figuring out the answer is surely costlier than 10 comparisons.