It’s been a while since I posted last so I thought I would throw my blog a bone… Once again I was looking for a good B-Tree implementation in C# on the net but came up empty. In the hopes of simplifying other developer’s lives I’ve created a generic B-Tree library that allows you to create a B-Tree with an arbitrary key type and value type. I’ve included support for specifying the key order by allowing you to supply a Comparer<T>. I’ve also allowed the B-Tree to support duplicate keys. Value comparison is also customizable by supplying a EqualityComparer<T>.
Why are B-trees a good thing for .NET you ask? Well the standard .NET library implements a hash table using the Dictionary<TKey,TValue> generic class. Hash tables do not support duplicate keys, and B-Trees are also much more efficient for supporting large key sets for both insertion and deletion. For more details on how a B-Tree data structure works see this: Wikipedia B-Tree article
Creating a B-Tree is fairly straight forward:
BTree<string,double> myBTree = new BTree<string,double>();
myBTree["Alpha"] = 1.0;
myBTree["Beta"] = 2.0;
myBTree["Delta"] = 3.0;
//Iterating through the BTree nodes
foreach( BTree<string,double>.Node node in myBTree )
Console.Write("Key = " + node.Key + ", Value = " + node.Value );
A few more interesting B-Tree
functions you can perform:
BTree<string,double>.Node myNode = myBTree.Find("Beta");
Console.WriteLine("Next node is: " + myNode.Next );
Console.WriteLine("Previous node is: " + myNode.Previous );
Console.WriteLine("Maximum depth is: " + myBTree.MaxDepth );
Console.WriteLine( "This should be false: " + myBTree.Contains("Beta",2.0));
Console.WriteLine( "This should be true: " + myBTree.Contains("Delta",3.0));
Take a look at the source code for more API goodies. It's fully documented.
Included in the B-Tree library source code is a unit test that validates the tree code with random keys and values for both insertion and deletion.
100,000 node random insertions took 0.6060537 seconds.
100,000 node random insertion and 50,000 random deletions took 3.0035593 seconds
1,000,000 random node insertions took 7.9972227 seconds.
1,000,000 node random insertion and 500,000 random deletions took 52.0168049 seconds
If there is any interest I might add support for the IQueryable interface, making it LINQ compatible.
For now this B-Tree library is used as the key index for a simple flat file caching database. Although it's far less functional than a full SQL database, caching with an in-memory key structure to a flat file out performs caching to any SQL database hands down.
Below is a link to the library this is released under the version 3 of the GNU public license.
DaisleyHarrison.Collections.Generic.zipx (340.29 kb)