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

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

Но сейчас дополнил важными подробностями.

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

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

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

То есть, получаем 1K/5-7 = 100-200 байт в среднем, на каждое /имя/ в пути.

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

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


Сразу несколько мыслей и вопросов.
1. База константная, или модифицируется на лету?
2. Имена в пути вообще хаотичные, или, например, это имена из фиксированного словаря?

Я бы подумал сделать вот что.

Сделать словарь всех имён, или, хотя бы, словарь префиксов имён. Пронумеровать их, например, хеш-функцией и номером в коллизии.
Таким образом, мы делаем 3 полезных вещи.
— экономим память, убирая повторения имён в множестве ключей
— экономим память в каждом ключе, — вместо 100-200 байт там будет 4-8 на ярус, то есть, длина ключа — (5-7)*(4-8) = 20-56, ну хорошо, 64 байта. Это вместо 1К
— приходим к фиксированному формату ключа и структуре дерева, и вообще, можем прибить гвоздями, что там будет ровно 8 ярусов, из которых сколько-то последних — фиктивные

Сам словарь — это хеш-таблица и, тут надо смотреть на нагрузку памяти, либо тупо массив строк, либо префиксное дерево.

Получить строковый ключ из номерного — дорогое удовольствие, т.к. если словарь не влезает в ОЗУ, то придётся делать к нему страничный доступ с подкачкой-выкачкой.
Таким образом, ещё и потребуется MRU/LRU список запросов имён по номерам.

Кстати говоря, а какие ограничения на адресное пространство? Для винды можно просто замапить файл и пусть винда сама возьмёт на себя задачу подкачки нужных страниц. Для 64-битных ОС — вообще всё сладко. Всё, что осталось сделать — это минимизировать кешмиссы, насколько возможно.

Ну а данные надо хранить более-менее последовательно по порядку возрастания ключей — это, как раз, минимизирует кешмиссы при поперечном обходе поддерева.