Re: GSoC - Designing a faster index format

From: Jeff King <peff@peff.net>
Date: Mar 29, 2012, 09:45 UTC
Message-ID: <20120329094554.GA11603@sigill.intra.peff.net>
In-Reply-To: <CACsJy8BfCpH3jtfaOyyAgjH3P5fv4FYjboqjoFYF2GiG44TmoA@mail.gmail.com>

On Tue, Mar 27, 2012 at 01:33:33PM +0700, Nguyen Thai Ngoc Duy wrote:

Show 10 quoted lines

> On Tue, Mar 27, 2012 at 10:34 AM, David Barr <davidbarr@google.com> wrote:
> > Another implementation in this general class is TinyCDB[1].
> > It is <1600 lines of plain C. Too few to be complete?
> > It is a derivative of DJB's CDB[2].
> >
> > [1] http://www.corpit.ru/mjt/tinycdb.html
> 
> "CDB is a constant database, that is, it cannot be updated at a
> runtime, only rebuilt.". It does not sound promising to me. I have not
> read the description carefully though.

No, you are right. I did some work with cdb many years ago. It optimizes for lookup by spending time building an optimal hash table at generation time. There is no way to add or modify an entry short of rewriting the complete contents of the database, which is exactly what we are trying to get away from with the current index format.

-Peff