This really depends on the nature of the tree itself.
The cache is in memory, so it's not going to be slow to search through.
If you can narrow the query down i.e. get content by type, that are children/descendants of a specific node, then you may be able to speed that up - IME this is usually more than fast enough as it's unusual to need to look for random doctypes that could be anywhere in the tree.
If your tree is huge, and you need to search all of it, then making a db/examine call first might be faster but the only way to know is to test it against your actual content.