Convert the SSN's to 32 bit numbers, so each ssn takes 4 bytes. Pack them in an array (so there's no added overhead per entry). Simple search algorithm would be to start searching in the middle, and dividing each search in half from there.
Search efficiency: log2(n) [10^9 = 2^30]
Storage space per entry: 4 bytes
Worst case n: 10^9
Worst case space = 4 x 10^9 = 4,000,000,000 = 4gigs