There are various methods employed by AV vendors to make the database size smaller. One is compression techniques, wherein the vendor will compress the database and make them available for download to users.
Second is generalization, a technique used in machine learning. They use pattern-matching or regular expressions for this. Suppose a vendor has 4 signatures of the following format:
Instead of having separate definitions for each of the above, these 4 definitions can be generalized to:
? being a wild-card character, which represents any one character. This technique significantly reduces the size of the database.
Here lies one caveat, though. Suppose the AV product finds
aaaax in some legitimate software. Naturally, it is also flagged as a malicious program(in reality, though, it is not). This gives rise to false-positives. In such cases, the AV vendor will give an exception to
aaaax in their next update of database, so that it does not get red-flagged in future.
There might be other techniques as well, which might be proprietary, but the above 2 techniques are generally widely-used ones.
As requested in comments, here are the links for the generalization techniques:
Intego Search for Generic Detection
Pattern Matching in GPUs