Re: cdb Fast Lookup
Bruce Guenter <[email protected]> Mon, 26 Aug 2002 17:46:29 -0600
| Newsgroups | gmane.comp.djb.cdb |
|---|---|
| Message-ID | <[email protected]> |
On Fri, Aug 23, 2002 at 07:12:52PM -0300, Gustavo Vieira Gonçalves Coelho Rios wrote: > DJB says about cdb: > > Fast Lookup: A successful lookup in a large database normally takes > just two disk accesses. An unsuccessful lookup takes only one. > > How may one make such a claim? Simple. In the *normal* case, a CDB lookup will use one disk access to read the hash table, examine a few slots (half the slots are empty to ensure the search terminates quickly), and then start reading the data. The data will *normally* be small, requiring a single read. > How may DJB have used a perfect hash function? The hash function used by CDB, while not a "perfect" hash, does very well at avoiding collisions with most keys. > How may one garantee such a feat ? The above statement is not a guarantee. -- Bruce Guenter <[email protected]> http://em.ca/~bruceg/ http://untroubled.org/ OpenPGP key: 699980E8 / D0B7 C8DD 365D A395 29DA 2E2A E96F B2DC 6999 80E8
signature.asc
(application/pgp-signature, 232 B)
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE9ar3V6W+y3GmZgOgRAl4bAJ99uIDq3oQCrMM9zl0hJIsUH8L69QCeLX5y MPv03LQDfIAzdaWx5zp3AXA= =1Dr3 -----END PGP SIGNATURE-----