Re: cdb Fast Lookup

On Friday, August 23, 2002, at 06:32  PM, Russ Allbery wrote:
> Steve Dekorte <[email protected]> writes:
>> No, but I don't think cdb uses 2^32 byte large db file. Remember, your
>> hash of a key is going to map to a position in a file where we should 
>> be
>> able to find the corresponding record.
>
> That's usually a bad design unless speed really matters way more than 
> file
> size (and even then, the locality would be horrible).  You instead only
> use a portion of your hash to map into a table of offsets.

Right.

> Dan's promising one disk read, but one disk read pulls in a whole block 
> of
> data, which can store a lot of 32-bit offsets in a hash table that uses
> linear probing.

If you're mapping to a set of records to then probe it's not a perfect 
hash in the normal sense. But in the context of a file based lookup I 
can see how you might consider in-memory operations relative non-ops so 
that use of the term "perfect hash" might make sense.

Cheers,
Steve