[devel] contents_index trie

[Alexey Tourbin]

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

Это похоже на фаловую систему, только в файловой системе ключ не может
быть одновременно и файлом, и каталогом.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 197 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20081101/68158955/attachment.bin>