If your hierarchy already uses one natural key, then navigation would obviously work really well. However, if you have other natural keys then it is still appropriate in ModeShape 3.x to use a query to find nodes based upon one of those natural keys. ModeShape 3.x still uses a Lucene index under the hood, so it still should be quite fast.
We are introducing explicitly defined indexes in ModeShape 4.0 to allow using other kinds of indexing technology (such as ElasticSearch, Solr, etc.), and to reduce the amount of work (and thus reduce the time) required to update the indexes. It's not clear whether or how this approach will change the query execution times. It's possible that queries could be faster because we'll be able to use a variety of perhaps more appropriate indexing technologies under the hood. But even if an explicitly-defined index uses Lucene, the query engine is different than in 3.x and it's too difficult to say one way or the other.