In general, HD Wallets use the following logic for how many addresses to query, and when to stop:
- Start with account 0, generate
gap limit number of addresses (usually 20)
- Check for any transactions in those addresses
- If there are no transactions, stop searching for new addresses and accounts
- If there are transactions, generator
gap limit more from the index of the last address with transactions on it. Additionally, also do this process for account 1 (you only check for n+1 accounts if Account n has transactions
The general idea is that no accounts will exist if the previous account is unused, and that no addresses in an account will be used after a single, consecutive block of
gap limit number of unused addresses.
Companies like BitGo who offer HD wallet services to exchanges etc. where you can easily have thousands of unused addresses in a row, and then addresses with transactions, generally ignore the gap limit. They instead maintain a list of all generated addresses and index them as individual addresses, not as an HD wallet.
On the API side of things, wallets generally try to keep a running index. They will maintain a cache of known transactions, and keep appending to it. This way, when you start it up, it only scans for transactions in the new blocks since the last time it scanned. This allows even light clients such as Electrum or Ledger/Trezor wallets to serve thousands of users with just a handful of nodes, since each wallet will not requery for previous transactions it alread knows about.
Naturally, if you import a frequently used HD wallet to a new wallet or delete the cache, the initial sync can take very long. However, subsequent syncs of the wallet will be much faster.
In addition to this, HD wallets will often rely on a full node (such as Bitcoin Core) or a system such as ElectrumX or Insight. All of these are capable of maintaining a full index. Bitcoin Core maintains only a running index across known addresses (which is why you need to rescan when you import an address). ElectrumX and Insight maintain an augmented index which keeps track of all transactions, and can quickly return data for any given address.
HD Wallets do continue to check for transactions across all used addresses. They simply don't rescan the entire chain every time. But for every new block, every tx in that block will be checked for every address in the HD wallet. This check can be done quickly via bloom filters or preindexed data such as from Electrum or Insight, without reaching a bottleneck.