"most of the verification anyway" ... I like to weight this "most" by real-time not by code size or "logical" verification-classes and then it turns out that the signature checking needs 99% or far more of it (depends on your disk speed).

Or put it in actual numbers: I need up to block height 216283:    112.7 sec cpu-time to put all data into place for every possible (including script validation) check. Well, real time is about 2-3 times larger depending on how quick the disk is (I needed e.g. 260 sec) from which I read the block chain.
And doing full verification (with script-verifications) needs 22419827/940 sec > 6.5 hours (I did not do it, only estimated it from a sample of about 890000 OP_CHECKSIG) in the most recent redeeming scripts.

And I don't believe this huge real-time safe is because I use hashtables and not level-DB structures. :-) Therefore I expect when loading a new bootstrap.dat (say to blockheight 216283) from disk into the client with pre-0.8.0 I only need about 5 minutes.

BTW: B-trees may now much better reasoned because you need NOW much more deletions in your data structures due to the redeemed scripts.

smtp