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

К>Здравствуйте, Nikolay Bespalov, Вы писали:

NB>>Ключ представляет из себя "путь" a/b/c/d/e... т.е. строку.
NB>>По ключу "быстро" получить данные. "Быстро" — быстрее линейного. С этим понятно — B-деревья(и разновидности).

К>Как раз, непонятно. Если строки явно организованы в иерархию, то напрашиваются префиксные деревья.
К>Что значит "быстрее линейного". Линейного по длине ключа или по количеству ключей?

К>Хотелось бы больше конкретики. Характерная глубина иерархии, количество дочерних элементов одного узла.

К>Б-деревья здесь возникают, скорее, как страничная организация оффлайновой памяти.

Вроде подробно описал ситуацию.

Имеем 1ККК ключей вида:
a/b/c
a/b
a/b/c/d
d/a/c
c/a
...
Глубина максимальная 5-7. Потомков в узле от 1-2, до 1КК

Каждому ключу соответствуют данные порядка десятков байт. Пусть будет сотня байт на данные.

Длинна ключа порядка килобайта.

Итого: ключи весят 1ККК * 1К = 1КККК байт.

0. Необходимо использовать не более 1Мб.
1. Необходимо получить данные по ключу за быстрее чем перебор всех ключей.
2. Необходимо получить всех потомков узла. Если "много", то итерационно(не всех сразу)
3. Необходимо минимизировать обращение к внешнему источнику хранения "индекса"