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

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

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

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

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

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

К>>Сделать словарь всех имён, или, хотя бы, словарь префиксов имён. Пронумеровать их, например, хеш-функцией и номером в коллизии.
S>Неэффективно, я выше советовал hierarchyid:
S>

S>The average number of bits that are required to represent a node in a tree with n nodes depends on the average fanout (the average number of children of a node). For small fanouts (0-7), the size is about 6*logAn bits, where A is the average fanout. A node in an organizational hierarchy of 100,000 people with an average fanout of 6 levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage.

S>(c)

S>Как раз случай топикстартера, у него глубина максимальная 5-7.

Если арность дерева (fanout — это арность или логарифм?) — как говорит ТС, от 1-2 до 1К, то это не похоже на "small fanouts (0-7)".
Количество листьев — тоже отличается на 7 порядков — 1Г вместо 100К.

Имеется множество ключей порядка 1ККК. Размер ключа порядка одного килобайта.
Ключ представляет из себя "путь" a/b/c/d/e... т.е. строку.
Данные размером порядка десятков байт.
Необходимо:

Не хранить весь "индекс" в оперативной памяти.
По ключу "быстро" получить данные. "Быстро" — быстрее линейного. С этим понятно — B-деревья(и разновидности).
По ключу (для выбранного пути) найти дочерние ключи (т.е. "файлы" лежащие в выбранной директории). Вот с этим не понятно.

PS: много гуглил, B-деревья выглядят подходящими, не могу связать мысли воедино...

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

NB>Необходимо:

Не хранить весь "индекс" в оперативной памяти.
По ключу "быстро" получить данные. "Быстро" — быстрее линейного. С этим понятно — B-деревья(и разновидности).
По ключу (для выбранного пути) найти дочерние ключи (т.е. "файлы" лежащие в выбранной директории). Вот с этим не понятно.

hierarchyid из ms sql? реализацию можно подсмотреть, открыв в ilspy тип SqlHierarchyId, сборка Microsoft.SqlServer.Types.dll

Тип устроен так, что поддерживает range scan, т.е. привернуть поверх него индекс — уже чисто технический вопрос.

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

К>Здравствуйте, 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. Необходимо минимизировать обращение к внешнему источнику хранения "индекса"

Здравствуйте, 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-битных ОС — вообще всё сладко. Всё, что осталось сделать — это минимизировать кешмиссы, насколько возможно.

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

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

К>Сделать словарь всех имён, или, хотя бы, словарь префиксов имён. Пронумеровать их, например, хеш-функцией и номером в коллизии.
Неэффективно, я выше советовал hierarchyid:

The average number of bits that are required to represent a node in a tree with n nodes depends on the average fanout (the average number of children of a node). For small fanouts (0-7), the size is about 6*logAn bits, where A is the average fanout. A node in an organizational hierarchy of 100,000 people with an average fanout of 6 levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage.

(c)

Как раз случай топикстартера, у него глубина максимальная 5-7.

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

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

1. База константная
2. Имена в путях хаотичные

В один момент времени необходимо работать с сотней "баз". Поэтому хочется потратить на "индекс" в памяти не более одного мегабайта.

Спасибо, буду думать дальше

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

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

К>>Сделать словарь всех имён, или, хотя бы, словарь префиксов имён. Пронумеровать их, например, хеш-функцией и номером в коллизии.
S>Неэффективно, я выше советовал hierarchyid:
S>

S>The average number of bits that are required to represent a node in a tree with n nodes depends on the average fanout (the average number of children of a node). For small fanouts (0-7), the size is about 6*logAn bits, where A is the average fanout. A node in an organizational hierarchy of 100,000 people with an average fanout of 6 levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage.

S>(c)

S>Как раз случай топикстартера, у него глубина максимальная 5-7.

Действительно выглядит как то что надо, как бы это реверснуть... + Хочется иметь доказательства сложностей на бумажке

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

NB>Действительно выглядит как то что надо, как бы это реверснуть... + Хочется иметь доказательства сложностей на бумажке
Вот неплохое введение.
Эффективность манипуляций с самим hierarchyid? Там всё ок, строится суффиксное дерево и сжимается в побитовое представление.

Эффективность поиска тоже ок, поиск всех детей сводится к условию "x>текущий узел И x < текущий узел.Сосед()". Обычный range scan, короче.

Засада в тяжёлых обновлениях и необходимости синхронизации при операциях с деревом (или пессимистичной, или оптимистичной блокировкой — один фиг затык). В общем для статичных данных — самое оно, для часто меняющихся — не лучше и не хуже прочих вариантов.

Я копался в этом лет 5 назад, сходу деталей не вспомню, если интересно — завтра могу попробовать поискать.