Посоветуйте структуру данных

Если данных не много и добавление чаще поиска -- хеш-таблицы Поиск чаще добавления -- сбалансированные деревья

SQLite, по-моему, умеет работать в памяти, если в качестве файла указать :memory:

> Если данных не много и добавление чаще поиска -- хеш-таблицы Поиск чаще добавления -- сбалансированные деревья

А вы слышали, что при хорошей хеш-функции сложность поиска в хэш-таблице O(1), а в сбалансированном дереве - O(log_2(n))?

ЗЫ: Для хэш-таблиц в худшем случае сложность поиска - O(N), но ЕМНИП это будет только в случае плохой хэш-функции.

ЗЗЫ: если структура изменяется достаточно редко, то вместо деревьев можно использовать отсортированные массимы и двоичный поиск.

В среднем сложность поиска в хеш-таблице при хорошей хеш-функции (n/размер_хеш_таблицы)/2

>в сбалансированном дереве - O(log_2(n))

в самом диком случае

>В среднем сложность поиска в хеш-таблице при хорошей хеш-функции (n/размер_хеш_таблицы)/2

Согласен, коллега. Гонево про O(1) - это если данных меньше, чем слотов. С таким же успехом можно для индексирования выделить сразу массив размерностью, равной максимальному значению индекса, а потом гордо говорить, что в нем поиск O(1)

> в самом диком случае

в самом типичном случае. В сбалансированном дереве большинство узлов -- листья и их приближенные

http://en.wikipedia.org/wiki/Trie

Хорошо, скажу по-другому: сложность поиска в avl не хуже log_2(n), rb 2*log_2(n) и в _любом_ случае нет провалов производительности как у хешей с O(n).

> Гонево про O(1) - это если данных меньше, чем слотов.

А изменить размер таблицы тебе религия запрешает?

> С таким же успехом можно для индексирования выделить сразу массив размерностью, равной максимальному значению индекса, а потом гордо говорить, что в нем поиск O(1)

И в ряде случаев это будет хорошим решением.

кстати, нашел такую интересную структуру данных -- T-дерево:

http://en.wikipedia.org/wiki/T-tree

но с поиском ее реализации туго :(