Какую древовидную структуру я должен использовать для индексации?

Question

Я подумываю поэкспериментировать с использованием древовидной структуры для индексации, поскольку я хочу проверить, является ли она быстрее, чем моя текущая реализация индексации, которая по сути является поиском на основе хеш-функции.

Я читал различные вопросы и статьи о производительности B-деревьев, AVL-деревьев и красно-черных деревьев и не вижу большой разницы в их производительности.

Какую древовидную структуру рекомендуют люди и почему? В идеале у него должна быть доступная существующая реализация .Net, хотя я не против реализации своей собственной в случае необходимости

Answer 1

Хорошая хеш-таблица почти всегда быстрее дерева. Большим преимуществом дерева является то, что вы можете использовать его для запроса диапазонов и для упорядочивания. Поэтому, если вам не нужны эти функции, я бы предпочел оптимизировать ваше решение на основе хеша.

И AFAIK SortedDictionary<K,V> основано на дереве.

Answer 2

Бинарное дерево не сбалансировано.Не используйте его.

Дерево AVL лучше сбалансировано, чем красно-черное дерево;У него более быстрый поиск.

Гораздо важнее то, что алгоритм AVL прост и понятен.Это, IME, не относится к красно-черному алгоритму.Вы не можете реализовать алгоритмы, которые вы не понимаете, или, скорее, вы можете реализовать их вслепую, что, на мой взгляд, равносильно тому, что я не могу их реализовать.