Re: cdb Fast Lookup
Russ Allbery <[email protected]> Fri, 23 Aug 2002 16:17:18 -0700
| Newsgroups | gmane.comp.djb.cdb |
|---|---|
| Organization | The Eyrie |
| Message-ID | <[email protected]> |
Gustavo Vieira Gonçalves Coelho Rios <[email protected]> writes: > 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? > How may DJB have used a perfect hash function? How may one garantee such > a feat ? It's not particularly difficult to generate a perfect hash function when you know the entire key space in advance, which cdb_make does. -- Russ Allbery ([email protected]) <http://www.eyrie.org/~eagle/>