On Sat, Nov 01, 2008 at 11:45:41PM +0300, Alexey Tourbin wrote:
> 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
> > 
> > Это похоже на фаловую систему, только в файловой системе ключ не может
> > быть одновременно и файлом, и каталогом.
> 
> То есть это префиксное дерево в общем виде.
> Вот другой пример (словарь):
> 
> ["ч","а","й"] -> <напиток>
> ["ч","а","й","к","а"] -> <птица>

Условие локальности ссылок дополнительно состоит в том, что группировка
данных должна усиливаться при нарастании вложенности.  На пальцах это
означает, что вариативность окончаний следует соотносить с основным
"понятием".  Пример (словарь):

["ч","а","й"] -> <напиток>
["ч","а","й","н","ы","й"] -> прил. муж. относящийся к "чай"
["ч","а","й","н","а","я"] -> прил. жен. относящийся к "чай"

Пример с точки зрения фс:
/usr/lib/perl5 -> perl-base
/usr/lib/perl5/Test -> perl-devel
/usr/lib/perl5/Test.pm -> perl-devel
/usr/lib/perl5/Test/More.pm -> perl-devel

Здесь при углублении в подкаталоги нарастает перловая специфика, что,
кстати, "параллельно" отражается на названии пакетов.  Префиксная
группировка статистически хорошо соответствует смысловой группировке,
а смысловая группировка хорошо реализует условие локальности ссылок.

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