[devel] contents_index trie

[Alexey Tourbin]

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/6a670145/attachment.bin>