Re: cdb Fast Lookup

Steve Dekorte <[email protected]> writes:
> On Friday, August 23, 2002, at 05:00  PM, Russ Allbery wrote:

>> How many keys are in the typical cdb database?  Do you really think
>> that number is large compared to the numbers represented by a 32-bit
>> integer, for instance?

> 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.

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.

The actual hash function is only a small part of the problem.

-- 
Russ Allbery ([email protected])             <http://www.eyrie.org/~eagle/>