Keep your keys sorted, and use an M-tree to retrieve any key.
An M-tree has M entry per node, instead of 2 for binaries.
It will help tremendously for performance.
Use a cache line size as the basis of your node size, hence 64 Bytes.
You can store 16 32bits values in this size.
Since you have 1000 values, 3 levels will be enough to retrieve the right key (as opposed to 10 levels for a binary tree).
Another idea would be to hash your keys into a small hash-table, such as 12-bits one (4K entries), and solve the potential collisions with a simple chain. You are very likely to get most of your keys in a single search.