Самый быстрый алгоритм плиска по неизменяемым данным?
Ищу самый быстрый алгоритм поиска по большому файлу (до нескольких терабайт). Реализовываю с нуля, задача в общем виде - по запрошенной строке найти все строки из файла, имеющие такое начало. Таким образом поиск по хэшу не сработает. Но файл не изменяется,новые данные не добавляются, что упрощает работу. Сперва я реализовал просто бинарный поиск через перемещение указателя по файлу. Скорость порядка 200 запросов в секунду на ssd (с кэшированием всех промежуточных точек). Интерполяционный поиск пробовал, оказался медленнее из-за не такого эффективного кэширования. Затем я оптимизировал поиск при помощи деревьев. Разделил файл на несколько частей. Сперва извлëк все строки на букву А в отдельный файл, затем все на букву б и.т.д В общем, достал все подфайлы, которые больше 100 мб получались, остальные строки в оставил в исходном файле. Затем полученные файлы рекурсивно поделил на подфайлы аа, аб и.т.д до тех пор пока все файлы не стали меньше 100 мб. Скорость выросла до 1000 запросов в секунду. Делить файлы дальше нельзя из-за лимита на число открытых файлов да и общего замедления доступа к ним. Поэтому дальше я сделал внутри каждого файла структуру как в хэшмапе ну или по мотивам. В первой строке указано в каких точках файла начинается каждая буква алфавита (без учëта общего начала файла). В каждой из этих точек такое же оглавление для этого диапазона и следующей буквы. И так далее рекурсивно я расставил оглавления до тех пор, пока размер наибольшего оглавления не стал меньше 1 мегабайта. Найдя нужную точку применяем бинарный поиск. Дальше уменьшать размеры такого кластера нет смысла, так как есть риск переполнения оперативной памяти (все считанные оглавления кэшируются). Да и физической памяти много тратится. С таким алгоритмом скорость поиска стала 3000 запросов в секунду. Сложность уже линейная. Ищу способы ещë сильнее оптимизировать поиск. Накидайте идей, что можно попробовать и как оптимизировать ещë сильнее. Для кэширования доступно 64GB. Увеличение базы данных индексами допустимо на 20%. Общий размер базы 100 миллиардов строк.