Re: [devel] contents_index trie

[Alexey Tourbin <at@altlinux.ru>]

[-- Attachment #1: Type: text/plain, Size: 2346 bytes --]

On Sat, Nov 01, 2008 at 09:07:50PM +0300, Alexey Tourbin wrote:
> 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
> 
> Это похоже на фаловую систему, только в файловой системе ключ не может
> быть одновременно и файлом, и каталогом.

То есть это префиксное дерево в общем виде.
Вот другой пример (словарь):

["ч","а","й"] -> <напиток>
["ч","а","й","к","а"] -> <птица>

Организация памяти в префиксном дереве должна быть такой, чтобы при
очередном переходе по составному ключу, т.е. "ч"->"а", "а"->"й" и т.д.
выполнялось условие локальности ссылок: ключи и значения в памяти
должны быть размещены (сгруппированы) "близко" друг к другу, то есть
чтобы при проходе по составному ключу вглубь дерева затрагивалось
минимальное число сегментов памяти.

В файловой системе так и происходит: каталог тоже имеет inode, и данные
каталога (dirent.h) локльно "сгруппированы" в "файле" каталога.  Так что
переход из каталога в подкаталог затрагивает минимальное количество
дисковых страниц.  А если бы информация о содержимом каталога была
произвольно разбросана по диску (как указатели на строки при
использовании malloc), тогда для напр. readdir(2) потребовалось бы
читать с диска в буферный кеш большое количество лишних страниц.

Короче, оптимальное размещение в памяти префиксного дерева --
по сложности это задача где-то на уровне реализации файловой системы.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]