От переводчика: предлагаю вашему вниманию перевод очень старой статьи, опубликованной 15 января 1983 года. Несмотря на столь внушительный возраст, статья показалась мне интересной, и возможно, что она будет полезной для кого-то и сегодня. На эту статью, кстати, ссылается раздел справки man locate(1) на opennet.ru: https://www.opennet.ru/man.shtml?topic=locate.
Краткое содержание
Статья описывает механизм быстрого поиска файлов в UNIX. Он объединяет два метода компрессии данных с новой техникой поиска строк, и предназначен для быстрого поиска произвольных файлов. Код, интегрированный в стандартную утилиту find, производит поиск в предварительно созданной базе данных, обновляемой ежедневно. Это отличает его от обычного механизма поиска совпадений ключа с кандидатами, которые генерируются «на лету» из разбросанной (по диску) структуры директорий.
База данных путей к файлам является инкрементально-кодированным, отсортированным в лексикографическом порядке списком (иногда называемом «сжатым спереди» файлом), который также подвергнут обычному биграмному кодированию с целью получения эффективного сжатия. Коэффициент сжатия составляет от 5 до 6 по сравнению с обычным ASCII-представлением. Список сканируется с использованием модифицированного линейного поиска, специально приспособленного для инкрементального кодирования, при этом типичное время, затрачиваемое алгоритмом, на 40-50% меньше, чем обычный поиск.
Читать полностью »