¿Qué estructura de árbol se debe utilizar para la indexación?

Question

Estoy pensando en experimentar con el uso de una estructura de árbol para la indexación como quiero comprobar si es más rápido que mi aplicación de indexación actual que es, en esencia, un hash basa búsqueda.

He leído sobre diversas cuestiones y artículos sobre el rendimiento de los árboles B, AVL-Árboles y Rojo-Negro Árboles y no se puede ver realmente mucha diferencia entre ellos se refiere a rendimiento.

¿Qué estructura de árbol se recomiendan las personas y por qué? Idealmente, debería tener una aplicación .Net existente disponible, aunque no soy reacio a implementar mi propia si es necesario

Answer 1

Una buena tabla hash es casi siempre más rápido que un árbol. La gran ventaja del árbol es que se puede usar para consultar rangos y para el pedido. Así que si usted no necesita estas características Prefiero mirar en la optimización de su solución basada en hash.

Y yo sepa SortedDictionary<K,V> se basa árbol.

Answer 2

Un árbol binario no es equilibrada. No lo utilice.

Un árbol AVL está mejor equilibrado que un árbol rojo-negro; que tiene más rápido de búsqueda.

Mucho más importante, el algoritmo de AVL es sencillo y comprehendable. Esto es, IME, no es el caso para el algoritmo de color rojo-negro. No se puede implementar algoritmos que no entienda, o más bien, se puede implementar a ciegas, que es propiamente equivalente en mi opinión, a -not- ser capaz de ponerlas en práctica.