Search code examples
.nettreeb-treeavl-treered-black-tree

What Tree structure should I use for indexing?

I'm thinking of experimenting with using a tree-structure for indexing as I want to test whether it is faster than my current indexing implementation which is in essence a hash based lookup.

I've read up on various questions and articles about performance of B-Trees, AVL-Trees and Red-Black Trees and can't really see much difference between them performance wise.

What tree structure would people recommend and why? Ideally it should have an existing .Net implementation available though I'm not averse to implementing my own if necessary

Solution

  • A good hashtable is almost always faster than a tree. The great advantage of the tree is that you can use it to query ranges and for ordering. So if you don't need these features I'd rather look into optimizing your hash based solution.

    And AFAIK SortedDictionary<K,V> is tree based.