Cook Computing

IndexedBtree Class

November 24, 2002 Written by Charles Cook

David McCusker has a piece on dicts as arrays. This has spurred me to make available an IndexedBtree class I worked on a while ago after reading David's writing on btree-based blobs. At the time I mentioned that I did not know much about traditional computer science algorithms and after doing some testing which demonstrated that the NET class SortedList does not scale very well, I was inspired to implement the IndexedBtree class both as an exercise in learning how btrees work and to provide something which provided the functionality of SortedList but which could scale to ten of thousands of members.

I originally implemented the class as a traditional btree but realised that adding the functionality to access the collection as a numerically indexed list was fairly trivial, as David suggested. Each non-leaf node, as well as storing the first key of each sub-node, stores the cumulative count of the nodes in each sub-node. Thus, when retrieving a value, instead of doing a binary search on the keys in stored in each node, you can do a binary search of the counts, which means that it is just as fast to access the collection by numerical index as by random key (probably slightly faster for numerical index because the comparisons in the search will usually be faster).

Ive spent some time today tidying up the code and adding some unit tests to the test harness. It should be completed in a day or two.