[devel] contents_index trie

[Alexey Tourbin <at@altlinux.ru>]

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

On Mon, Oct 27, 2008 at 12:18:22AM +0600, Mikhail Gusarov wrote:
>  IV> Если распилить один только большой пакет, например wesnoth, то его
>  IV> 150M wesnoth-data покроют 82M как бык овцу.
> 
> Тут нужно считать, как часто обновлется репозиторий, и как часто -
> wesnoth-data и другие noarch-субпакеты.
> 
> Впрочем, из тех 82M очень много - не по существу. Информация из
> contents_index легко ужимается до нескольких мегабайт (trie вместо
> списка файлов).

Trie лишь оптимизирует *доступ* к contents_index (переходы типа
многоуровнего хеша); а с точки зрения размера выгоднее contents_index
просто сжать.

А также trie оптимизирует доступ лишь *логически*.  А на самом деле
доступ к contents_index будет проходить через диск.  Дисковый доступ
имеет сильно выраженную постраничную специфику (4K блоки).  Значит,
нужна нетривиальная логика сериализации trie, которая бы оптимизировала
локальность ссылок при переходе вглубь trie на физических страницах.
Грамотная запись trie на диск -- по сложности это уже задача на уровне
libdb4.

Короче, необходимость оптимального *дискового* представления почти что
компрометирует выбранную идеальную структуру данных.

Если кто не в теме и кому интересно,
http://en.wikipedia.org/wiki/Trie
http://git.altlinux.org/people/at/packages/path-trie.git

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