2 seeks. Address space doesn't matter, you have one seek to read the directory (I'm assuming 100% cold cache), and one seek to get to the page in question.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
I was actually thinking of a >2GB DB file on a 32 bit server. But leaving that aside, it sounds like you're assuming a perfect hash function with no collisions. If you have collisions, you have to deal with the possibility of a hash bucket overflowing and requiring an additional seek.
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.
Comments
2 seeks. Address space doesn't matter, you have one seek to read the directory (I'm assuming 100% cold cache), and one seek to get to the page in question.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
I was actually thinking of a >2GB DB file on a 32 bit server. But leaving that aside, it sounds like you're assuming a perfect hash function with no collisions. If you have collisions, you have to deal with the possibility of a hash bucket overflowing and requiring an additional seek.
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.
It is 2 seeks, at most, for 100% of lookups.