What Tree structure should I use for indexing?

Question

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

Answer 1

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.

Answer 2

A binary tree is not balanced. Do not use it.

An AVL tree is better balanced than a red-black tree; it has faster lookup.

Much more importantly, the AVL algorithm is straightforward and comprehendable. This is, IME, not the case for the red-black algorithm. You cannot implement algorithms you do not understand, or rather, you can implement them blindly, which is properly tantamount in my view to -not- being able to implement them.