New toy for bzr developers: B+Tree index sketch

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert Collins wrote:
| On Tue, 2008-07-01 at 14:29 -0500, John Arbash Meinel wrote:
|
|
|
|> Attached is a patch which moves the page size into a constant, to make
|> it easier to modify if we want to test for optimal page sizes on large
|> projects. Specifically, you had a place where you did 4096 - 100 = 3996
|> and then hard-coded that, which caused weird problems when I replaced
|> all occurances of 4096 :).
|
| Thanks. This is good; I have been wondering about putting this in the
| header to make it completely tunable; at the cost of needing an extra
| read if the first read doesn't contain the root node.
|
| -Rob

I wanted to ask a bit about how these are written out.

It seems like you write all the leaf nodes, and then work out what the
next level nodes are, write them, if that spills, work out the next, etc.

Which means that you write leafs => internal 1 => internal 2.

But isn't the final structure "internal 2 | internal 1 | leaf" ? At
least, I would assume that gives better forward reads.

So is it just that you stage into a temp file, and then copy the values
over when finished? Certainly you won't know how many internals you need
until you are done, because you don't know how much you can fit into a node.

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkhqpI0ACgkQJdeBCYSNAAOFOACffPLdOW+eQf9HkyMT+h6oNQ5f
wpwAnjUzj9bejGnzHIbfASFPX85ztOOg
=RKVg
-----END PGP SIGNATURE-----