On Sat, Nov 01, 2008 at 09:01:36PM +0300, Alexey Tourbin wrote:
> On Sat, Nov 01, 2008 at 06:42:07PM +0300, Денис Смирнов wrote:
> > On Tue, Oct 28, 2008 at 10:50:13AM +0300, Алексей Турбин wrote:
> > 
> > Правильно ли я понимаю что речь идет о задаче создания чего-то вроде cdb,
> > с некоторыми уточнениями:
> > - нет key/data, есть только key
> > - поддерживается единственная операция "проверить на существование данный
> >   key"
> > - нужно обеспечить минимальное количество pagefaults при выполнении этой
> >   операции
> > 
> > Я правильно понял?
> 
> Нет, имееется в виду trie.  Это дерево.  С каждым ключом ассоциировано
> значение _и_ последующие вложенные ключи.  Так что идёт доступ по
> составному ключу, типа ["usr","bin","perl"]->"perl-base".  То есть
> значение ключа "накапливается", а дополнительный переход на каждом этапе
> выполняется рекурсивно (хвостовая рекурсия с "остатком" составного ключа).
> http://en.wikipedia.org/wiki/Trie

Это похоже на фаловую систему, только в файловой системе ключ не может
быть одновременно и файлом, и каталогом.