Cook Computing

IndexedBtree Tests

December 5, 2002 Written by Charles Cook

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: Hashtable  Add:        220  Enumerate:  121  Item:       60  GetByIndex: n/a  Remove:     130
test: SortedList  Add:        92142  Enumerate:  511  Item:       40  GetByIndex: 30  Remove:     96699
test: IndexedBtree  Add:        1502  Enumerate:  651  Item:       70  GetByIndex: 441  Remove:     1472