Цитата(Earnest @ 24.12.2008, 18:41  ) |
| Раз строки имеют переменную длину, то без предварительного индексирования не обойтись. |
Это не так. Делим файл на логические блоки. Размер каждого блока не менее двухх максимальных длин записи. Это гарантирует, что вне зависимости от того, откуда мы возьмём такой блок, в нём будет минимум одна полная запись. После чего собсно бинарным поиском ищем БЛОК, в которых находится требуемая запись. На каждом шаге сужается тот кусок файла, в котором ищется нужная запись (отбрасывается чуть менее половины куска с предыдущего шага).
Т.е. для файла в 10 Г и записей по 4к читаем сперва 8к, начиная со смещения 5Г, находим в этом блоке начало первой полной записи (сразу после первого разделителя), экстрагируем ключ и сравниваем. Если больше, то на следующем шаге надо искать в диапазоне смещений 0 - 5Г+4к, если меньше - в диапазоне смещений 5Г - 10Г... можно посчитать, что потребное количество чтений 8-килобайтных блоков не превышает 21, и то при условии что на очередном шаге нам случайно не подвернётся нужный ключ (вероятность чего, кстати, не такая уж и маленькая)... и если на это потребуется 5 секунд, то просто комп надо менять, хотя бы на второй пенёк.
(по непонятным причинам)
