15

What class in the C# (.NET or Mono) base class libraries directly implements B-trees or can be quickly overridden/inherited to implement B-trees? I see the Hashtable class but can't seem to find any classes for anything from the Tree family...

There must be a base Tree class that can be overridden to generate specific Tree implementations (like B-tree or Red-Black or Binary Tree etc by specifying the tree invariant conditions). Doesn't make sense to have programmers reinvent the wheel for basic data structures (Tree's are pretty basic in CompSci), especially in an object oriented language; so I'm pretty sure I'm just not searching right...

Edit:

  1. I'm not using Hashtable nor do I think it's related to a Tree. I merely used it as an example of "another data structure class in the BCL".
  2. For those curious about the background aka the use case. It's for O(log(N)) searches for an in-memory associative set. Imagine creating an index for that associative set...
DeepSpace101
  • 13,110
  • 9
  • 77
  • 127
  • The good news is that the B-tree pattern is highly publicized and there are many implementations for you to port to C#. Or, you could just find a 3rd party implementation. – crush Jan 03 '14 at 19:03
  • 4
    `Hashtable` does not use a tree based structure. It uses a hash table. You should also never use it outside of legacy code; you should use the generic `Dictionary` instead. A `SortedDictionary`, unlike `Dictionary` uses a tree based structure internally, as does `SortedSet`, although neither expose said tree structure externally. – Servy Jan 03 '14 at 19:07
  • 1
    `SortedSet` is a red-black tree implementation. I don't know how you'd make a "base Tree class" that you can use to derive other kinds of trees. If you do, please publish it. – Gabe Jan 03 '14 at 19:10
  • If you think you have an idea for a base tree framework then you should implement it. – Nick Bray Jan 03 '14 at 19:12
  • Why do you want a tree class? Unless it's for academic reasons, you can probably choose a built-in class that does everything you need. – Tim S. Jan 03 '14 at 19:18
  • 2
    The deeper question is, what do you need such a specific collection for? The system collections are versatile enough and efficient enough for most purposes (especially with the immutable collections thrown in). OTOH if your needs are so specific that these collections are insufficient, you'd likely be better off implementing one from books or papers. – Anton Tykhyy Jan 03 '14 at 19:19
  • 2
    Trees are only basic in education, they perform too poorly on modern processors to be considered. [Cache is king](http://stackoverflow.com/a/16562482/17034). – Hans Passant Jan 03 '14 at 19:21
  • 8
    @HansPassant I wouldn't say that; it does depend on context. Look at, say `Expression`, and everything done with that recently. Expressions are all trees. Databases also (at least to the best of my knowledge) rely on trees (interestingly enough, B-trees, specifically) to handle indexes as they are both highly efficient, and are well suited for being partially in memory and partially on disk, which is key when there is more data than can fit into memory. I would agree though that their use tends to be fairly specialized, but they're not just academic. – Servy Jan 03 '14 at 19:27
  • 3
    @Hans Passant: SQL Server databases use B*-Trees very effectively. – Mitch Wheat Jan 04 '14 at 01:32
  • @HansPassant : I need to add/remove a lot of items each second and keep the list ordered. The LinkedList is good for insert/remove, but is slow to find right location to insert new item. So B-trees could be an alternative – Elo Mar 25 '20 at 09:55

5 Answers5

8

There is no (public) implementation of a B-Tree in .NET.

There is no generic Tree class exposed that provides a partial implementation of a tree based structure.

You would need to write something like this from scratch, or use a 3rd party implementation rather than a .NET implementation.

Servy
  • 202,030
  • 26
  • 332
  • 449
6

Unfortunately .Net doesn't provide any library for Tree.

But you can get some help online for B-trees

1) https://github.com/rdcastro/btree-dotnet

2) http://social.msdn.microsoft.com/Forums/vstudio/en-US/c51b655d-f288-4fbf-9312-9ae4278ff8b7/b-tree-implementation?forum=csharpgeneral

Rakhi
  • 174
  • 4
2

I know I'm terribly late to the party but I've had great success with BPlusTree. The authors did a fantastic job with it. http://csharptest.net/projects/bplustree/

joelc
  • 2,687
  • 5
  • 40
  • 60
  • This one is unfortunately no longer maintained, and the [.NET Standard fork](https://github.com/mamift/CSharpTest.Net.Collections/) also seems not to be fully working. – Rei Miyasaka Sep 13 '20 at 21:52
2

You may want to look at my generic C# implementations of both B & B+ trees in GitHub.

Advanced-Algorithms

Jehonathan Thomas
  • 2,110
  • 1
  • 28
  • 34
1

There is an implementation of B-Tree for .NET on codeplex which looks promising. Performance-wise too.

Code uses the Store API to store & manage key/value pairs of data. Internal Store implementation uses an enhanced, modernized B-Tree implementation that virtualizes RAM & Disk storage.

Couple of key enhancements to this B-Tree as compared to traditional

implementations are:

  • node load optimization keeps it at around 75%-98% full average load of inner & leaf nodes. Traditional B-Trees only achieve about half-full (50%) average load. This translates to a more compressed or more dense data Stores saving IT shops from costly storage hardware.
  • leaf nodes' height in a particular case is tolerated not to be perfectly balanced to favor speed of deletion at zero/minimal cost in exchange. Also, the height disparity due to deletion tends to get repaired during inserts due to the node load optimization feature discussed above.
  • etc... a lot more enhancements waiting to be documented/cited as time permits.
Ognyan Dimitrov
  • 6,026
  • 1
  • 48
  • 70