Re: Git's database structure

> On 9/4/07, Andreas Ericsson <ae@op5.se> wrote:
>> Jon Smirl wrote:
>>> Let's back up a little bit from "Caclulating tree node".  What are the
>>> elements of git's data structures?
>>>
>>> Right now we have an index structure (tree nodes) integrated in to a
>>> base table. Integrating indexing into the data is not normally done in
>>> a database. Doing a normalization analysis like this may expose flaws
>>> in the way the data is structured. Of course we may also decide to
>>> leave everything the way it is.
>>>
>>> What about the special status of a rename? In the current model we
>>> effectively have three tables.
>>>
>>> commit - a set of all SHAs in the commit, previous commit, comment, author, etc
>>> blob - a file, permissions, etc.
>>> file names - name, SHA
>> commit - SHA1 of its parent(s) and its root-tree, along with
>>          author info and a free-form field
>> blob - content addressable by *multiple trees*
>> file names - List of path-names inside a tree object.
>>
>>
>> To draw some sort of relationship model here, you'd have
>>
>> commit 1<->M roottree
>> tree M<->M tree
>> tree M<->M blob
> 
> By introducing tree nodes you have blended a specific indexing scheme
> into the data. There are many other ways the path names could be
> indexed hash tables, binary trees, etc.
> 
> This problem exists in files systems. Since the path names have been
> encoded into the directory structures there is no way to query
> something like "all files created yesterday" from a file system
> 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.
>