2 ms·
> Binary search will require about 20 to 30 reads, This does not pass a sanity check. If one switches to linear scan at 4KiB = 2^12 bytes, then 30 (balanced, b
by puffoflogic 4y ago
> Binary search will require about 20 to 30 reads,
This does not pass a sanity check. If one switches to linear scan at 4KiB = 2^12 bytes, then 30 (balanced, but approximately correct for unbalanced) binary search steps would search a 4TiB file. I don't know how big the hash file is but it isn't this big. Not even 4GiB big.
The maximum number of steps is lg(file size)-12, maybe plus 2 or so to account for the unbalanced search. (NB the unbalanced search approximates the balanced only because the hashes are approximately uniform; the relation doesn't hold in general.)
- danbruc 4y agoThe version 8 file contains 847,223,402 hashes which gives 29.7 bits, that is where I got the 30 reads from. And I assumed the most naïve approach, always just seeking and reading a single hash, but admittedly this would almost certainly not read the final page over and over again. And then I just subtracted 10 taking into account that you would read the final page only once, with 10 being a rough approximation of 12. How many bytes you actually read per read could be affected by all kind of things - sector size, cluster size, page size, read ahead, ... - so 10 bit was good enough for me. But you are right, the number of reads would almost certainly be in the vicinity of 20, not 30.