Comments 16
WHERE name LIKE 'начало%'
и обретя GoLang понял что можно теперь пользовать оперативной памятью и создавать:
простое дерево
Для погромистов на настоящих языках Rust оставлю здесь crate https://docs.rs/fst/0.4.4/fst/
Эта реализация трансдюсеров — лучшая из всех что я встречал.
У меня на входе было 100 миллионов ключей со средней длиной 25 байт. У групп ключей часто встречался общий префикс от 7 байт и до двух третей всей длины строки. Ещё нужно было 8 байт для значения, в качестве value были числа от 1 до N. Итого 2.5Гб ключей + 800 Мб значений.
После засовывания всего добра в fst, выхлоп занял около 240 мегабайт в памяти, при этом вся структура сериализуется в файл и может mmapиться прямо из этого файла, не требуя никаких дополнительных приседаний.
LZMA на этих же ключах, соединенных через \n дал даже чуть больший размер и это без возможности RA и префиксного поиска.
Если же упороться дальше и сам выхлоп fst прогнать через LZMA, то байтов получится в два раза меньше — 116 Мб.
Из минусов — иммутабельность и необходимость класть ключи в отсортированном порядке, поэтому для миллиардов ключей придется вспомнить решения любимых задач на собеседованиях про merge sort на файлах.
Но для задачи из ОП-поста вроде можно обойтись и так.
С вашими данными явно стоило память экономить. В моей задаче случай проще и я выбрал скорость в обмен на память. А так да, могу убрать SearchItem.Key и получить сжатый индекс.
Если задачи экономии памяти особо не стоит, а нужна скорость — пробовали сравнивать свою реализацию с map[string] []SearchItem, где в качестве ключей использовать все встречающиеся префиксы?
Мысль хорошая, и реализация была бы совсем простой. По началу хотелось в таком духе и сделать по быстрому, но в итоге не пробовал, так как понадобилось бы сильно больше памяти для ключей, и для поиска по началу строки пришлось бы еще класть много дублей в значения. С увеличением данных память росла бы нелинейно. Но так поиск работал бы еще быстрее.
Стоит написать, что эта структура данных называется trie или "бор" в русской литературе.
Текстовый индекс по котировкам в памяти на Go