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 13:17 +1000, Robert Collins wrote:
|> I have been tinkering with a B+Tree approach to the disk indices. I
|> prefer this over a hash based index because of the ability to do
|> in-order traversal when desired.
|>
|> In short, I think we can save substantial size with the currently
|> developed B+Tree and it allows addressing some of the memory problems
|> Andrew has spent some time debugging.
|

...

|
| I think the btree random access is so much slower because it is totally
| unoptimised. One thing is that is always bisecting to find the page of a
| key. If we had a plain dict of keys to probe in first, we could avoid
| that extra work. We could further eliminate the leaf nodes from the page
| cache (so getting more hits on locator nodes), but that would then
| require an IO on every key miss; so I'd prefer to not do that. Another
| possibility would be to put the keys from a leaf node into a plain dict,
| and have a callback on leaf node removal from the _node_cache to remove
| those keys from the dict.


I think it would be very reasonable to change the code so that internal
nodes are cached separately from leaf nodes. There is generally 1-2
orders of magnitude difference in the number of nodes.

Especially once I get the multi-way bisecting done, we also will only
hit each row 1 time. Which means that all of those nodes get a single
reference, and then we are down to the next level. And the leaf nodes
*also* get a single reference (and they were accessed last). So we are
quite likely to kill internal nodes when we really want them, in favor
of leaf nodes that we won't request again.

I *might* work on this after I get the bisecting done, but we'll see.

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

iEYEARECAAYFAkhq+GkACgkQJdeBCYSNAAPbNACgo7Zp/57JopED5UC/k1qFcUHV
qWgAnjMB2sro4q978VKSxrtfSlmz+Z2N
=E1EM
-----END PGP SIGNATURE-----