Since you are in a Gnutella Forum I will try to explain how searching works in the Gnutella Network:

The basic idea is to send one query to all the peers connected directly to you. These peers pass on the query and check if they can reply positive to the query (if they have the file).

As you can see this is exponential, thats one reason why massive querieng is bad for the Network speed.

When Ultrapeers were introduced, the ultrapeers kept a list of all files the leaves had and responsed for them to save bandwidth for the leaves.

Damn my English sucks and I'm having an exam tomorrow. Fsck.