Имеем некое небольшое деревцо ( максимум 1024 ключа),
ключи которого могут иметь разную длину могут редактироваться.

Его нужно разместить непрерывном участке памяти длиной 2к,4к, 8к, 16к, таким образом,
что бы узлы были связаны через смещения в этом участке памяти.

подскажите варианты алгоритма и литературу.

зы отвечаю на вопрос :
- зачем ?
- что бы дерево целяком ложилось в кеш процессора.

Akinaд0kключи которого могут иметь разную длинуОграничения на эту длину имеются?


Минимум 1 байт , максимум 1 К.

Можно держать фиксированную длину но мне жалко кеш процессора....


д0kчто бы узлы были связаны через смещения в этом участке памятиЭту фразу поподробнее...
[/quote]

Указатели на узлы должны храниться как смещение от начала 2к,4к, 8к, 16к блока в котром лежит дерево.

д0kд0kподскажите варианты алгоритмаМожет, посмотреть в сторону нагруженного дерева?
А вообще рекомендации сильнейшим образом зависят от того, что с этим деревом делают. Вряд ли нужно только хранить, редактировать, и при этом не искать, не сортировать и т.п...

Основная задача нужно быстро парсить поток получаемый по сети или из файла.
Побить поток на поля , а потом при необходимости ( попадания в if в зависимосити от данных присутствующих в потоке) некоторые поля
побить на субполя итд ....
Разложить поток в структуры и массивы и собрать их в дерево для последующего быстрого поиска
по значениям полей и поиска похожих сообщений по критерию.

Например , есть пачка ХМL сообщений,
по факту поступления следющего сообщения нужно вреальном режиме времени найти
все ранее пришедшие, в которых некоторые теги равны тегам пришедшего сообщения.
Количество ранее пришедших миллионы и сотни миллионов.
Дерево которое будет индексировать поиск сообщений тема отдельного топика
мне сейчас нужно разложить само сообщение по полям в дерево, что бы потом
это дерево подключать к узлам дерева более высокго уровня( чистому индексу по тегам).
У меня протокол не XML.

д0kчто бы узлы были связаны через смещения в этом участке памяти
Akina
Эту фразу поподробнее...


Указатели на узлы должны храниться как смещение от начала 2к,4к, 8к, 16к блока в котром лежит дерево.

[/quot]

Опять же отвечаю на вопрос:
-зачем ?
- что бы блок с деревцом можно было с минимальными затратами выгузить дерево на диск
и считать обратно.

Если кого интересует предметная область,
цифровая обработка сигналов,
разложение потока для последующей обработки преобразованием фурье,
поиска и иследования множественных отраженных сигналов в спектральной характиристике.

Главная глобальная задача всей этой затеи -
фильтрация множественно отраженных сигналов в потоке.

YesSqlд0kИмеем некое небольшое деревцо ( максимум 1024 ключа),
ключи которого могут иметь разную длину могут редактироваться.

Его нужно разместить непрерывном участке памяти длиной 2к,4к, 8к, 16к, таким образом,
что бы узлы были связаны через смещения в этом участке памяти.

подскажите варианты алгоритма и литературу.

зы отвечаю на вопрос :
- зачем ?
- что бы дерево целяком ложилось в кеш процессора.
В твоем случае деревцо преобразуется в массив смещений отсортированный по ключу.

мне нужно не массив а дерево .

Но идею я понял , с определенной позиции
массив должен становиться 2 мерным , потом 3-мерным и
возвращаясь обратно в одномерный , к концу массива.
То есть нужны некие метаданные для алгоритма,
что бы он участок одномерного массива начал воспринимать
как многомерный массив.

YesSqlд0kпропущено...


мне нужно не массив а дерево .

Но идею я понял , с определенной позиции
массив должен становиться 2 мерным , потом 3-мерным и
возвращаясь обратно в одномерный , к концу массива.
То есть нужны некие метаданные для алгоритма,
что бы он участок одномерного массива начал воспринимать
как многомерный массив.
Нет. ты не понял.

расшифруй.

Leonid Kudryavtsev1. Обычное B-Tree. Или я что-то не понимаю.
https://ru.wikipedia.org/wiki/B-дерево

2. Если все в памяти и кол-во элементов не большое - не очень понятно, нафига дерево. Возьмите например HashTable
"максимум 1024 ключа", "2к,4к, 8к, 16к"

по факту поступления следющего сообщения нужно вреальном режиме времени найти
все ранее пришедшие, в которых некоторые теги равны тегам пришедшего сообщения.
Количество ранее пришедших миллионы и сотни миллионов.
Дерево которое будет индексировать поиск сообщений тема отдельного топика
мне сейчас нужно разложить само сообщение по полям в дерево, что бы потом
это дерево подключать к узлам дерева более высокго уровня( чистому индексу по тегам).

Если действительно важна скорость и компактность, я бы на начальном этапе использовал что-то типа HashTable, когда все данные получены, потом бы эти данные упаковывал в что-то более компактное, например SortedArray и искал двоичным поиском.

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

Но давайте, всетаки не будем забегать наперед и сконецентрируемся на алгоритмах
создания дерева в блоке памяти , так как это сабжевый вопрос топика.

YesSqlд0kпропущено...


расшифруй.
Вернемся к твоему первому посту. Если ты хочешь разместить все в одном участке памяти то к твоему блоку данных добавляется массив смешений на твои структуры в этом блоке данных. Затем этот массив сортируется по ключам твоих структур. И вуаля доступ к твоим структурам через этот массив O(log N) - такой же как и у дерева, и все лежит в одном участке памяти.

Если естественный ключ , то да.
а если нужно сурагантый?
когда поля нужно классифицировать тегами ?

Для каждого тега заводить свой массив?


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

[quot YesSql]д0kпропущено...

Ты сам себе противоречишь. Ранее ты говорил что нужно делать лукап в другом буфере, а теперь ты говоришь что у тебя ключи суррогатные......
Таймаут на подумать - хорошая идея.


нет , не противоречу 19192303 ....
д0kРазложить поток в структуры и массивы и собрать их в дерево для последующего быстрого поиска
по значениям полей и поиска похожих сообщений по критерию.


Критерий похожести и тегирование будет задаваться в формуле преобразования фурье.
Искомый сигнал может быть смещен по спектру и учитывать или не учитывать грамоники ,
его числовое выражение в потоке данных в большенстве случаев поиска будет разным.

schiд0k- что бы дерево целяком ложилось в кеш процессора.

А зачем ? У вас уникальная операционная система, которая гарантирует выделение процессора исключительно вашей задаче на протяжении ее выполнения ?

Операционная система - обычная

Изопропилпреждевременной оптимизацией пахнет...


Еще нет никакой оптимизации, это проектные исследования,
в процессе написания ТЗ.
Попытка нарисовать пазлы, которые потом будут складиваться
в готовое решение, точных формул в точном виде тоже еще нет.
Пока есть только конечная цель, понимание общий принципов ее достижения
и попытка оценить требуемые инвестиции.

maytonд0kНапример , есть пачка ХМL сообщений,
по факту поступления следющего сообщения нужно вреальном режиме времени найти
все ранее пришедшие, в которых некоторые теги равны тегам пришедшего сообщения.
Количество ранее пришедших миллионы и сотни миллионов.
Дерево которое будет индексировать поиск сообщений тема отдельного топика
мне сейчас нужно разложить само сообщение по полям в дерево, что бы потом
это дерево подключать к узлам дерева более высокго уровня( чистому индексу по тегам).
У меня протокол не XML.
Док. Мне кажется тут нужна Марковская сеть. И промоделировать первый раз
твой трафик на ней. А потом на основании данных по узлам и переходам сделать
твоё чудесное дерево.

Спасибо , полезная инфа.

softwarerд0kподскажите варианты алгоритма и литературу.
1. Разбить данные узла на часть постоянного размера (родитель, дети итп) и переменного (ключ)
2. Части постоянного размера укладывать с начала выделенного блока, идентифицируя индексом
3. Части переменного размера укладывать с конца выделенного блока
4. Вести список свободных областей, соответственно его корректируя

Блоки данных в СУБД informix по похожему принципу организованы.

1. заголовок с метаданными ( п4)
2. строки( row) таблицы ( п2) .
3. массив смещений начала строк внутри блока,
который растет навстречу строкам ( п3).

Индекс массива есть последний байт(ы) rowid,
что позволяет играться перемещением строк в рамках блока
без изменения метаданных за его пределами.

Я похожий принцип хочу заложить в организацию хранения по сабжу.

Но мне вместо массива нужно дерево , которое должно описывать
не телько сортировку, а и иерархию зависимостей родитель-дети.