[MERGE] Use a dict for Btree internal nodes instead of LRU

[John Arbash Meinel]

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

At the moment we use an LRUCache for btree internal nodes, with a max of
100 records. However, experience has shown that we get 100 nodes per
page (interestingly this holds true for chk pages). For the Launchpad
.cix we have 340k records, which fits on 3190 total pages. Of that, 21
are internal nodes.

At a factor of 100:1 at each level, you need to have 100*100*100 = 1M
nodes before the internal node cache would ever start dropping entries.
As such, it doesn't seem worthwhile to spend any time maintaining an LRU
for internal nodes.

I know we intend to have btree's be memory capped, but it just seems
that just naturally we won't get many internal nodes. We already put
them into a separate cache because we didn't want leaf-nodes flushing
them out of the cache.

I don't know that this is a big win either way, but it just made sense
to me as I was looking at the code.

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

iEYEARECAAYFAknL7C4ACgkQJdeBCYSNAAMXKwCcC9nu3GKsFKcdN0D/vHQo3yka
hhcAn0XIcJ7vEGRShjJfBFX7SLr2NLf/
=hFOp
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: btree_internal_node_dict.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20090326/244121f3/attachment-0001.diff