Есть задача быстрого поиска поименованных объектов в древовидной структуре напоминающей файловую систему с каталогами и файлами, файлы это объекты типа "1" а каталоги это объекты типа "2"

Проще привести пример —


дир1:объект1
дир1:объект2
дир1:объект3
дир1:объект4
дир2:объект5
дир2:объект6
дир2:объект1
дир2:объект3
дир3:объект10
дир3:объект11
дир3:объект12
дир3:объект14

В рамках директории объекты уникальны. В аналогии с файловой системой — не могут быть два файла с одним и тем же именем.
Директории также уникальны.

Пример близкий к реальному:

\aaaa\eeee\yyyyy\ooooo(01):\bbbb\cccc\dddd\eeeee 
\aaaa\eeee\yyyyy\ooooo(01):\bbbb\cccc\dddd\qqqqqq
\aaaa\eeee\yyyyy\ooooo(01):\bbbb\cccc\dddd\hhhhh
\aaaa\eeee\yyyyy\vvvvv(02):\bbbb\cccc\dddd\eeeee 
\aaaa\eeee\yyyyy\vvvvv(02):\bbbb\cccc\dddd\qqqqqq
\aaaa\eeee\yyyyy\vvvvv(02):\bbbb\cccc\dddd\jjjjjj 
\aaaa\eeee\yyyyy\ddddd(03):\bbbb\cccc\dddd\eeeee 
\aaaa\eeee\yyyyy\ddddd(03):\bbbb\cccc\dddd\qqqqqq
\aaaa\eeee\yyyyy\ddddd(03):\bbbb\cccc\dddd\wwwww
\aaaa\eeee\yyyyy\lllll(04):\bbbb\cccc\dddd\eeeee 
\aaaa\eeee\yyyyy\lllll(04):\bbbb\cccc\dddd\qqqqqq
\aaaa\eeee\yyyyy\lllll(04):\bbbb\cccc\dddd\ffffff

В скобках перед двоеточием это не часть строки DIR-а, а некий ID для этого DIR-a.

Требуется :

1) быстро искать по запросам типа:

1) найти ID для DIR=\aaaa\eeee\yyyyy\ooooo,
2) найти объект \aaaa\eeee\yyyyy\vvvvv если ID=10
2) Хранить это в неком блобе (двоичный файл), который при загрузке можно уже превратить в некое дерево или что угодно.

Да, забыл важное добавить — ID для DIR, назначается в рантайм, то есть неизвестно заранее — на этапе "компиляции". Ну скажем, во время выполнения возникает некое событие имя которому и есть DIR, его надо найти в нашей базе, и у этого события есть некий ID, который ему надо присвоить. Таких события может одновременно возникать несколько. Затем возникает второй тип события имя которому OBJECT и для него известен ID и вот надо найти этот объект в нашей базе. Затем возникает третий тип события имя которому DIR и его ID известен, и надо найти его в базе и удалить этот ID из DIR.

ps: Заранее спасибо!

Здравствуйте, BLov, Вы писали:

BL>Есть задача быстрого поиска поименованных объектов в древовидной структуре напоминающей файловую систему с каталогами и файлами, файлы это объекты типа "1" а каталоги это объекты типа "2"


BL>Требуется :
BL>

BL>1) быстро искать по запросам типа:
BL>

BL>1) найти ID для дир=\aaaa\eeee\yyyyy\ooooo,
BL>2) найти объект \aaaa\eeee\yyyyy\vvvvv если ID=10
BL>
BL>2) Хранить это в неком блобе (двоичный файл), который при загрузке можно уже превратить в некое дерево или что угодно.
BL>

1) А структура статичная? Задачи пополнять/удалять нет?
2) ID объектов заданы, или только имена? ID можно выбрать как удобно?

Если таки "да" оба раза, то чем плоха закрытая хэш-таблица? Можно даже идеальный хэш привинтить...

Здравствуйте, Erop, Вы писали:

Опередил!

E>1) А структура статичная? Задачи пополнять/удалять нет?

Структура 200% статичная.

E>2) ID объектов заданы, или только имена? ID можно выбрать как удобно?

Описал в описании. Нет, как раз ID может быть несколько и они не известны за ранее.

E>Если таки "да" оба раза, то чем плоха закрытая хэш-таблица? Можно даже идеальный хэш привинтить...

Да я тоже думаю над этим, но тут еще одна проблема — нет никаких библиотек — все надо делать в ручную.

Здравствуйте, BLov, Вы писали:

BL>Описал в описании. Нет, как раз ID может быть несколько и они не известны за ранее.
Ну тогда две таблицы прямая и обратная, если id не плотные.

E>>Если таки "да" оба раза, то чем плоха закрытая хэш-таблица? Можно даже идеальный хэш привинтить...
BL>Да я тоже думаю над этим, но тут еще одна проблема — нет никаких библиотек — все надо делать в ручную.

А язык какой?
В целом написать закрытый хеш -- дело пары часов максимум. Это если с юниттестами и кофе

Там всего-то дел. По хэшу вычисляем позицию в таблице, и от неё идём вперёд по кругу, пока не встретим то, что ищем или пустую ячейку.

В ячейках храним смещения данных или ID объектов или что там ещё бывает в этой конструкции...

Ну и вычисление хэша тоже с полпинка пишется.

Здравствуйте, Erop, Вы писали:

E>Ну и вычисление хэша тоже с полпинка пишется.

"Проблема" не в том, чтобы сделать "как-то", а задача сделать близко к идеалу. То что ты предлагаешь — это далеко не эфективно.
Дерево поиска, это дерево статических (константных) данных, в котором надо искать. Зачем тут хеш? Подумай.

Здравствуйте, BLov, Вы писали:

BL>Дерево поиска, это дерево статических (константных) данных, в котором надо искать. Зачем тут хеш? Подумай.
Дык это вроде как и есть типичная задача для идеального хеша.
Ты конечно, можешь взять lex/yacc, скормить ему свою лексику и получить быстрый парсер, но вообще-то это уже давно сделали в виде gperf. Чего велосипед изобретать?

Здравствуйте, BLov, Вы писали:

А нельзя тут прикрутить кодировку типа Хаффмана по кол-ву объектов в директории? Или это совсем не то?

Здравствуйте, BLov, Вы писали:

BL> Требуется :
BL> [list=1]
BL> 1) быстро искать по запросам типа:
BL>

BL> 1) найти ID для DIR=\aaaa\eeee\yyyyy\ooooo,
BL> 2) найти объект \aaaa\eeee\yyyyy\vvvvv если ID=10
BL>

Судя по "требуется" никакое дерево тебе не требуется. Достаточно сопоставлять строчке "\aaaa\eeee\yyyyy\ooooo" некий ID и обратно. Т.е. две банальные хеш-таблицы, в качестве "компиляции" сделать идеальный хеш.