Re: [GSoC] Designing a faster index format

From: Thomas Rast <trast@inf.ethz.ch>
Date: Apr 5, 2012, 21:49 UTC
Message-ID: <87r4w1vofu.fsf@thomas.inf.ethz.ch>
In-Reply-To: <D97085E6-2B9F-42C5-A06D-B53422034071@gmail.com>

Thomas Gummerer <italyhockeyfeed@gmail.com> writes:

> -- Proposed solution --
> The proposed solution is to redesign the index to a B-tree based format. This
> allows changes to the index in O(log(n)) time, with n being the number of
> entries in the index.

> -- Solutions that were also considered --
> - Append-only data structure
> - Database format
> - Padded structure

This is quite complete already, which I think is great, but it's still missing one "obvious" approach: a directory-tree based layout that uses "flat" storage. That is, the entries grouped by directory and thus arranged into the "natural" tree, so as to allow parsing only part of it. But not pulling any tricks to make it easy to change; a nontrivial change would mean a rewrite. How good do you think that could be?

-- 
Thomas Rast
trast@{inf,student}.ethz.ch