As we know, address reusability compromises both privacy and security.
My question is how Bitcoin wallets avoid address reusability?
Is wallet generates an address from index 1 and scan blockchain whether an address is used or not, until wallet finds an unspent address?
In case of HD wallets, whenever the user requests to generate a new address to receive address. Wallet generates an address from the very first index and checks whether the index is used or not until it reaches address that has not been used.
Is the wallet keeps state of unused address?
If the wallet is stateless, then determining unused address by generating the address from very first and looking up blockchain for the unused address is expensive?
I tried to find documentation of wallets such as Ledger, Airbitz, but i did not found it.
Edit: Note that I have knowledge of how seed, private and public keys are generated, as it is explained in detail BIP 32.
My question here is When a user requests to generate a new address how does wallet find that the address is previously unused?
If wallet generates an address from the very first index, scans blockchain whether the address is previously spent or not? until it finds the index new address to receive payment.