I have just created a T-Tree project on github: http://github.com/andrevdm/ttree/tree/master
“A T-tree is a balanced index tree data structure optimized for cases where both the index and the actual data are fully kept in memory, just as a B-tree is an index structure optimized for storage on block oriented external storage devices like hard disks. T-trees seek to gain the performance benefits of in-memory tree structures such as AVL trees while avoiding the large storage space overhead which is common to them.” (from wikipedia)
See also: Tobin J. Lehman and Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986 for a comprehensive discussion of T-Trees
The project is a C# implementation of a T-Tree. There is also a very simple command line profiler and a GUI for visualising inserts and deletes.
There are still a few things outstanding (e.g. Making the class enumerable and supporting the visitor pattern) but all the basics (insert, search and delete) are now working.
I'm sure that more can be done to speed up this implementation but it already performs very well. That coupled with the efficient use of memory makes it quite an attractive data structure.
A quick disclaimer: I have only just gotten the basics working I'm sure there are still some bugs lurking. I'll be doing more testing and adding more unit tests as I have time.
The code is released under the BSD licence.
Please let me know if you find it useful, spot any bugs or can think of way to improve it.
