[MERGE] Btree Indexes

[John Arbash Meinel]

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

The attached patch was worked on by Robert and I. It is just a b+tree indexing
layer, without any attached repository or actual user.

We've both spent some time tweaking it, and improving performance. For now,
this seems to be a rather high-performing layer, which we feel surpasses our
current KnitGraphIndex in all measurable ways.

It differs slightly from our plugin prototype, in that we don't use Blooms. As
much as I tried, I could only manage to "break even" for local operations, as
the overhead of lookup in the bloom was enough to override the benefit of not
bringing in a different page to check the index directly. We may revisit it in
the future.

As mentioned in the past, the big wins are that the indexes are more compact
(you can fit more keys in the same place), and that you can N-way bisect them.
(On average 80-100 nodes fit in a page, so you get 80-100-way fan out).
Further, the bisecting is done "in parallel", so we don't do N * log80(N) bisects.

As an example, the mysql indexes currently take 49MB on disk. In btree form
they take up only 15MB. And if we set the packing operation to full, we can
get that down to 13.4MB (a good time to do that would be during a 'bzr pack'
operation.)


This is the first step towards bringing in a repository format which uses
btrees for the index files. It also gives something for bzr-search to use, etc.

Robert: on a very positive note, I managed to tweak the three_level test from
taking 68s => 7.8s on my machine. Half of that is just because we only need
100k nodes for 3-levels, and not 200k nodes.

This also has a pyrex helper for the bits that made sense. Namely, reading the
packed nodes into an in-memory structure, and flattening nodes into lines to
be written down. It *might* behoove us to move some of the actual packing
multiple nodes into a page into pyrex, but the bulk of the time spent is
actually in the zlib.compressobj(). (If we really wanted, we could turn the
packing down to 0, and it would shave a modest amount of time off.)

John
=:->

PS> Robert- I did change the disk signature, since the format is different. So
I'm pretty sure I've covered all of your requests.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFIrfXWJdeBCYSNAAMRAlMfAJ4jpRhdcozJ7I/ijDs4N5vvSYVl0wCdGf5c
re3ljHwHOvvZxfpV/MZfAdM=
=qZy8
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: btree.patch
Type: text/x-diff
Size: 187776 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080821/63e02f0c/attachment-0001.bin