Two (possibly off base, but given your description . . .) ideas that come to mind:

• use a Bloom Filter (edit: probably not relevant)
• use DB_File and let it build a btree (backed on disk) for you rather than you manually (basically) doing similar

Edit: tweaked; upon rereading I don't get that your dataset's necessarily sparse (in that you need to quickly check for membership or not) so the bloom suggestion's off base probably.