Re: Git's database structure

From: David Tweed <david.tweed@gmail.com>
Date: Sep 4, 2007, 20:17 UTC
Message-ID: <e1dab3980709041317v35c1dab7wd5e6ac4f7292d522@mail.gmail.com>
In-Reply-To: <9e4733910709040919u3d252b91s2785ed4d20086c88@mail.gmail.com>

On 9/4/07, Jon Smirl <jonsmirl@gmail.com> wrote:

> without building another mapping table or a brute force search. I keep
> using Google as an example, Google is indexing hierarchical URLs but
> they do not use a hierarchical index to do it.

It might help the discussion if you could point to a reference, preferably one that discusses the trade-offs in the design, with more concrete details about what google or other search engines actually do. It would be particularly useful if it addressed issues of

1. the type of queries the representation is optimised for.
2. consistency requirements. (Can a search engine use different data
structures if they improve average performance at the cost of
occasional inconsistency/lossage?)

Finally, this design space is not totally unexplored, for example,

http://plan9.bell-labs.com/sys/doc/venti/venti.html

AFAICS they only use SHA-1 for blocks within files (although this might be misreading the paper) so presumably they'd have knowledge about the trade-offs.

-- 
cheers, dave tweed__________________________
david.tweed@gmail.com
Rm 124, School of Systems Engineering, University of Reading.
"we had no idea that when we added templates we were adding a Turing-
complete compile-time language." -- C++ standardisation committee