Different approaches take different levels of time investment on your part; here are some options your focus is on the data-structure for the index, whereas I'

Different approaches take different levels of time investment on your part; here are some options your focus is on the data-structure for the index, whereas I'm thinking that unless the data itself that the index points to is also in RAM, its going to be hard to get msecs results anyway. 1) if you are repeatedly accessing the same subset of your data, rather than making continuous random reads across the whole data set, then caching that set can help: 1a) if you have some file or DB on each of your machines, then the kernel will automatically cache regularly read bits and it'll all end up quite fast. You could use any database of your choice for this, with 'sharding'. 1b) you could run memcached and the DBs on each of your machines; to be honest, letting the OS do the caching is likely a better idea. 2) if you want to continuously go all over the data set, then you are going to be IO bound. 2a) therefore, if you can compress your data set - find a space-efficient storage for it so it fits into 250GB of RAM instead of 5TB of disk, then you can avoid the disk and it'll fly. You could consider storing deltas and then arithmetic or huffman coding behind some low order predictor; ask on this compression forum http://encode.ru/ http://encode.ru/ and you'll have to tell them much more about your data and perhaps describe a few lines of it. Compression can be on small blocks of data, so you only have to decompress a small amount to get the random value you want 2b) or you might find that you only need to generate some statistics from the data once, and then work with the derived data - presumably small enough to fit in your RAM - from then on 3) you could buy bigger machines, or bigger amounts of RAM