On Wed, Sep 03, 2008 at 01:07:26AM +0400, Alexey Tourbin wrote:
> On Wed, Sep 03, 2008 at 03:05:22AM +0700, Mikhail Gusarov wrote:
> > Twas brillig at 22:59:57 02.09.2008 UTC+03 when mike@osdn.org.ua did gyre and gimble:
> > 
> >  MS> Интересно, в чём проблема будет apt-file адаптировать...
> > 
> > В том, что contents_index - аааахренительного размера. И даже понятно,
> > как его можно катастрофически сжать - сделать radix tree, но ни у кого
> > руки не дошли.
> 
> Я как раз над этим думал, но что-то потерял интерес...
> http://git.altlinux.org/people/at/packages/path-trie.git

Тут ещё такое дело что кодироване указателями иногда ничего не даёт.
Напр. компонент "/usr" в строке занимает четыре байта, и укзатель тоже
занимает четыре байта, так что замена коротких компонентов пути на
указатель ничего не даёт.  Более того, игра в указатели имеет подводную
часть -- malloc bookkeeping (malloc is not *that* free) и фрагментация
памяти.

К тому же как мы будем сериализовать этот trie?  Berkeley DB
поддерживает только одноуровневое хранение ключ->значение.
На каждый ключ создается страница и т.д.  А ведь как раз желательно,
чтобы частые проходы по одному и тому же пути имели какой-то эффект
на буферный кеш ОС (то есть чтобы не всасывать весь файл целиком,
а только e.g. /usr/bin).

Реально наверное лучше всего делать ключ %{DIRNAMES} а значение
сериализованный блоб %{BASENAMES} -> %{NAME}.

Тогда как раз получается постраничное попадание в зависимости от
каталога.

$ rpm -qa --qf '[%{FILENAMES} -> %{NAME}\n]' |perl -pe 's#(.*)/#$1\t#' |sort