.NET Generic B-Tree Library and Source Code

by Aaron D-H 28. July 2010 00:48

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 );

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.

DaisleyHarrison.Collections.Generic.zipx (340.29 kb)

Tags:

Software Engineering

Comments


August 3. 2010 11:43
Muscle Building Routine
I checked out some of the other posts on your blog , but this one really  intrigues  me. Thanks for sharing this  interesting   site.


August 8. 2010 19:15
Min Tedrick
You have a good blog here...Have you ever considered installing the wp-cache plugin ?  It will make your site load a lot faster.  keep up the good work.


August 9. 2010 20:43
aarondh
Thanks for the tip, but my site uses BlogEngine.Net rather than WordPress.  To futher clarify the use of the caching discussed above: I use this type of caching for managing e-commerce data and/or Line-of-Business data to speed up delivery to aspx pages.  Things like catalog information that change slowly overtime are cached in a local flat file for a short time to avoid the need to read from back office systems repeatedly on high volumn sites.

Comments are closed

About the Author

I'd like to introduce myself to you... My name is Aaron Daisley-Harrison.  I have worked in the software engineering field for a number of years, and as an  Application Architect have created solutions for many industry verticals; worked with both Java and Microsoft technologies; Developed SQL database engines as well as full text search systems; and Knowledge management systems.   I am currently doing contract work out of the Pacific North West and have lately been focusing on Microsoft technologies like SharePoint 2007/2010, WCF, Identity Framework, JQuery, Xml and Silverlight.
[more]



 Digg!

 

Disclaimer
The opinions expressed herein are my own personal opinions and do not represent my employer's view in anyway.

© Copyright 2009 Aaron G. Daisley-Harrison - All Rights Reserved.