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