New toy for bzr developers: B+Tree index sketch

[Robert Collins]

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.

The attached script (run from the root of any pack style repository you
want to analyze) gets the following result for bzr.dev:

Original aggregate index size:  10140380
B+Tree aggregate index size:    5644360
Difference:                     4496020

The index2 plugin is available from
lp:~lifeless/+junk/bzr-index2
- you can install it by:
bzr branch lp:~lifeless/+junk/bzr-index2 ~/.bazaar/plugins/index2

I'd love feedback on the design (see
http://bazaar.launchpad.net/~lifeless/+junk/bzr-index2/annotate/robertc%
40robertcollins.net-20080701023304-a01ibps9ycjkhzqj?start_revid=robertc%
40robertcollins.net-20080701023304-a01ibps9ycjkhzqj&file_id=design-20080624222253-p0x5f92uyh5hw734-2)

-Rob


-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testindex2.py
Type: text/x-python
Size: 1990 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080701/8397ba5f/attachment-0001.py 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080701/8397ba5f/attachment-0001.pgp