New toy for bzr developers: B+Tree index sketch

[Ian Clatworthy]

Robert Collins wrote:
> On Wed, 2008-07-02 at 00:27 -0500, John Arbash Meinel wrote:
>> I think fundamentally the indexes should always be a small portion of
>> the total data. (For bzr.dev you are talking 90MB vs 3-10MB). However,
>> they are a *critical* portion, as it is where you start from.
>>
>> The data sizes are nice to see, I would also be very interested in the
>> performance numbers. Like, time to 'bzr log', etc.

> ian - my later scripts will give some much more interesting figures, if
> you'd like to run them. And/or as John says, some real-world figures..

Here are the performance figures from indexbench.py. OOo ...

/home/ian/scm-conversions/OOo/OOo.bzr
ian at humpback:~/scm-conversions/OOo/OOo.bzr$ python ../../indexbench.py ./
Baseline overhead: Read 1149504 keys in 545.816
GraphIndex: Wrote 117596270 bytes in 728.443
GraphIndex: iter_all_entries in 1037.163
GraphIndex: iter_random_one in 761.203
GraphIndex: get_components_positions(2000) in 104.485
GraphIndex: search_from_revid in 93.461
GraphIndex: miss torture in 0.000
GraphIndex: -------Done---------
Baseline overhead: Read 1149504 keys in 554.721
BTreeIndex: Wrote 36143176 bytes in 727.363
BTreeIndex: iter_all_entries in 13.084
BTreeIndex: iter_random_one in 3354.088
BTreeIndex: get_components_positions(2000) in 25.712
BTreeIndex: search_from_revid in 23.508
BTreeIndex: miss torture in 0.000
BTreeIndex: -------Done---------

Mozilla ...

ian at humpback:~/scm-conversions/mozilla/mozilla.bzr$ python ../../indexbench.py ./
Baseline overhead: Read 59725 keys in 2.545
GraphIndex: Wrote 6292035 bytes in 4.020
GraphIndex: iter_all_entries in 3.532
GraphIndex: iter_random_one in 4.582
GraphIndex: get_components_positions(2000) in 1.866
GraphIndex: search_from_revid in 0.194
GraphIndex: miss torture in 0.000
GraphIndex: -------Done---------
Baseline overhead: Read 59725 keys in 2.490
BTreeIndex: Wrote 1642568 bytes in 7.733
BTreeIndex: iter_all_entries in 0.566
BTreeIndex: iter_random_one in 27.705
BTreeIndex: get_components_positions(2000) in 0.726
BTreeIndex: search_from_revid in 0.213
BTreeIndex: miss torture in 0.000
BTreeIndex: -------Done---------

Ian C.