Google search does a lot more complex processing (crawling, historical weighting) and it does it on unstructured pages. Discoveravility in a microblogging system doesn't have to be a lot more than indexing/collation of structured posts, and end-user clients can be designed to participate in that. "Retweets"/"boosts" are already a form of that.
Sure, but fediverse numbers are pitiful at this point. Reality is that 99.9% of users don't care about decentralization, so it ends up being a "this has to work as well as a centralized system" does.