On Tue, Dec 17, 2013 at 09:02:41PM +0100, digitalmars-d-boun...@puremagic.com wrote: > On Tuesday, 17 December 2013 at 19:09:49 UTC, H. S. Teoh wrote: > >What's a good, efficient file structure for storing extremely large > >lookup tables? (Extremely large as in > 10 million entries, with keys > >and values roughly about 100 bytes each.) The structure must support > >efficient adding and lookup of entries, as these two operations will > >be very frequent. > > But 200*10million = 2GB. Can't you use an existing KD-tree and tweak > it to fit memory pages and rely on paging for a start?
Hmm. You're right, I think I underestimated my data size. :P The 10 million figure is based on problems that my current program successfully solved (with an in-memory hashtable). I guess that larger problems must far exceed that number (I ran out of memory so I couldn't check just how big it got before I killed the process). Suffice it to say that this is a combinatorial problem, so the number of entries grow exponentially; anything that can help reduce the storage requirements / I/O latency would be a big help. T -- VI = Visual Irritation