Decentralized search is a complex problem and there exist different approaches to it with different degree of centralization and resource requirements.
DC++ is a bit more decentralized than BitTorrent. There still are central servers ("hubs"), but they don't even host any metadata. Search works by the hub broadcasting all search queries to all online peers and them replying with results if they have any. The file transfers themselves are p2p.
I have an idea that's kind of more decentralized. Initially envisioned as a missing global search feature for the fediverse, but can be adapter for anything that has a similar network structure. A server has a number of peers already established because of the ActivityPub federation. Each server would send to its peers some kind of bloom filter that determines the tags or keywords that this server has results for. Then, when searching, your server would find the peers who are likely to have what you want, and only send your search query to them. If there aren't any, then it would send your query to the peers that have most users (with some random bias for load balancing purposes) because they're likely to have more connectivity, and they would point you where to look based on their own peers and their bloom filters. There would also need to be some kind of reputation system (centralized server lists? p2p exchange of scores/reports?) so that servers that return spam or intentionally wrong results would get punished.
This could probably be made to work in a fully-decentralized p2p network, but I imagine it would be too easy to abuse. Getting a new domain costs money, yet getting a new IP or public key is free and easy.