I coded some very unscientific performance tests for the IndexedBtree class last night. Of course Hashtable wins - unless you need access by numerical index. SortedList provides the numeric indexed access but is much slower on random adds and deletes. The new class IndexedBtree is somewhere in-between, but does give you numerical indexing which could be important in some applications.
I've thought about implementing a skip-list class but I think a blob btree as described by David McCusker has more scope for being used in interesting ways, particularly if the implementation can be used for both in-memory and on-disk blobs.
The test adds 100,000 pseudo-random entries, performs the various operations for each entry, and then removes them pseudo-randomly. All times in msecs.
test: SortedList Add: 92142 Enumerate: 511 Item: 40 GetByIndex: 30 Remove: 96699
test: IndexedBtree Add: 1502 Enumerate: 651 Item: 70 GetByIndex: 441 Remove: 1472