.NET Generic B-Tree Library and Source Code

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 I’ve also allowed the B-Tree to support duplicate keys. Value comparison is also customizable by supplying a EqualityComparer

Why are B-trees a good thing for .NET you ask? Well the standard .NET library implements a hash table using the Dictionary 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 );

    myNode.Remove();

    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.

A little about me

Aaron Daisley-Harrison is a Software Application Architect living in the Pacific Northwest.
Further more

Recent Projects

Calendar.help

Calendar.help is a new Cortana skill. Schedule meetings, impress your friends.
 http://calendar.help

Visual Studio .Connect Mobile Application

Mobile Web application on IOS, Android, and Windows Phone.
more
All Projects

Gibson Guitars

I love guitars. Playing guitar helps me to relax after a long day of fighting with plugs and wires.
 Visit Gibson

Seattle Sounders FC

My wife and I are avid soccer fans here in Seattle, WA.
 visit Sounders FC

Search this Site