Какой алгоритм структуры данных использовать для написания своего велосипеда?
Алгоритм структуры? В сети немало чудаков, но вы - первый, кто так сопряг эти слова.Стоит ли использовать хеш-таблицы, если да то какую структуру данных использовать (из STL в C++ или в C# из пространства имен System.Collections.Generic )?Можно, любую. В словаре Мюллера полтора кило веса, но для хэш-таблицы это - пустяк.Могу ли я ко всему этому подключить SQL Microsoft базу данных?Можно, но зачем тут многопользовательская база? Достаточно и SQLite.пробовал реализовать нечто подобное в виде двоичного дерева ... терялась скорость поискаКакая скорость, вы вообще о чём? Вам сюда.
Просто реализуйте свой KeyValuePair,  в нём есть всё, что нужно для словаря. А база это на ваше усмотрение, какая БД вам удобна  ту и используйте, но она определённо нужна. Не будете же вы хранить слова в .txt файле