Per the question, the operation has two parts:
- Determining if a record for a value exists.
- Returning the record if the value exists.
Part 1: Existence
Per the question:
- There are 100 billion possible values
- 1 billion of those values actually exist.
Since these are integers and computers typically come in 32 bit and 64 bit flavors, they must be 64 bit integers to allow 100 billion possible values. Therefore a strategy that stores all the actual values uses approximately 8GB of space (one billion * 8 bytes).
However, existence (or presence in the database) is binary and can be represented by a single bit. An alternative approach is a bitmap of all possible values. 100 billion bits is approximately 12GB. This will fit in memory of a modestly specified computer with room to spare.
The Bitmap Datastructure
It is possible, but neither necessary or sufficient, to think of a 100 billion bit bitmap as a database with 100 billion rows. The utility of this abstraction is that all the gory database details of managing heap files, disk paging and caching strategies can be applied if one chooses. Or to put it another way, you can have databases all the way down.
Persisting the bitmap to disk and loading it into memory is also amenable to all the standard database mechanisms of working with blocks. But potentially easier because the bitmap is always sorted on key values and is fixed size so the block in which a "record" will be found can be calculated directly. For example with a 1MB page size, the bitmap exists across 12k pages. The location of an ID's status can be page ID modulo 12k
and location ID modulo 1MB
or more generically ID modulo numberOfPages : ID modulo blockSize
.
Efficiency
If it's data and not just random numbers, efficiency is a function of implementation details. And determining what's efficient is a matter of measuring and determining what is inefficient in actual use. In other words, database tuning.
For some implementations, 12GB for a bitmap might be nothing more than throwing up another machine to a cluster. For other implementations, 12GB might be a non-starter for financial or bureaucratic reasons. That's just the nature of engineering as opposed to mathematics. But, at 12GB the operation can be done in memory and that means I/O can be avoided and I/O operations are the traditional measure of efficiency for databases...with the caveat that relative performance of in memory operations is just as dependent on caching and paging as on disk operations. The latencies are simply different magnitudes.
Underspecification
There's no way to know whether or not a bitmap is an appropriate engineering approach because engineering is the process of dealing with all the messy details and expectations of actual systems. The question does not describe these details and expectations.
Part 2: Record Retrieval
Performance is a matter of tuning the database for the actual workload. Standard methods will go a long way.