On Tuesday 10 February 2009 07:16:00 you wrote:
quoted text
> On Tue, Feb 10, 2009 at 01:58:41AM -0600, Boyd Stephen Smith Jr. wrote:
> > On Monday 09 February 2009 15:12:06 Johannes Schindelin wrote:
> > > So I think it would be a sane plan to do the following when a commit
> > > note is requested:
> >
> > So, something like a Trie data structure?  I think that is a great way =
to
quoted text
> > store fixed-length strings from a limited alphabet with arbitrary data
> > attached.
>
> I don't think a Trie quite makes sense here. We still have to look
> linearly through each git tree (an artifact of the tree implementation).

Perhaps it's not a traditional trie structure but that was the closest anal=
ogy=20
I could come up with.  I was actually thinking of something between a trie =
and=20
a b-tree, I think.  (It has been a long time since data structures class...)

The issue, as I understand it, it that we don't have gargantuan tree object=
s. =20
Reading and writing are slow and they'd also take up way to much memory if =
you=20
are only trying to find a few commits.

So, we figure out a maximum tree size that is reasonable, figure out a fan-=
out=20
that prevents the tree from growing above that size, but *dynamically* appl=
y=20
that fan-out.  I.e. if the fanout is 2 characters, and we've added notes fo=
r=20
both ff82730c and ff23abc0, then our tree would have ff/ -> some_tree_sha, =
but=20
if we had only a note for the one one our tree would have ff82730c... ->=20
some_note_sha.  Unlike .git/objects, we should probably also do dynamic fan=
out=20
in subtrees.

Yes, this would require a custom merge strategy for notes to flatten -> mer=
ge=20
=2D> canonicalize.

quoted text
> Or did you mean something else entirely?

Yeah, that.

While I'm throwing out crazy ideas, why not makes a notes tree look just li=
ke=20
=2Egit/objects, including info and pack directories?
=2D-=20
Boyd Stephen Smith Jr.                   ,=3D ,-_-. =3D.
bss@iguanasuicide.net                   ((_/)o o(\_))
ICQ: 514984 YM/AIM: DaTwinkDaddy         `-'(. .)`-'
http://iguanasuicide.net/                    \_/