Как в файле хранить дерево?

Если дерево бинарное - то можно в виде кучи. Максимальное время доступа - logN по основанию 2, где N - количество элементов.

Если операций доступа много и они частые то все равно придется все дерево в память грузануть, так что в принципе все равно как оно в файле будет, а если операций немного и нечастые то тогда тоже нет смысла огород городить :)

>Если операций доступа много и они частые то все равно придется все дерево в память грузануть, так что в принципе все равно как оно в файле будет,

все нереально. миллиард интов это четыре гига озу только на значчения а надо еще и обвязку:(

дерево не бинарное

Как хорошо, что СУБД разрабатывают не такие, как ты.

Представь себе, без разницы. Не-бинарное на бинарное отображается элементарно.

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

Насчет третьего вопроса после повторного прочтения все прояснилось. Остальные вопросы в силе.

http://en.wikipedia.org/wiki/B%2B_tree

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

Без точной формулировки это лучший совет, на который я способен :) Если нужно сохранять структуру исходного дерева, то ХЗ... нужна полная формулировка задачи. Может, там нужна хеш-функция и mmap-окно.

>Дерево для поиска используется или для других целей?

1. для поиска
2. добавление новых узлов и ветвей между поисками тож должно быть быстрым

>Нужно ли сохранять структуру этого дерева один-в-один?

сохранять порядок веток не нужно

>Нужна ли быстрая загрузка _всего_ дерева в память или быстрое выполнение определенных операций? Конкретнее задачу поставь.

Тогда тебе действительно нужно Б/Б+ дерево или модификации. Поиск будет очень быстрым (структуры данных такого типа лежат в основе баз данных и поисковых систем). Добавлять рекомендую не по записи, а буферизируя в основной памяти в виде хоть бинарного дерева, а по накоплении N записей (где N достаточно велико) сливать с основной структурой во вторичной памяти.

Спасибо но мое дерево типа B а не B+.

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

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

пока ничего умнее в голову не лезет

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

> Спасибо но мое дерево типа B а не B+.

Несущественно.

> причем с возможным количеством веток из одного узла порядка миллиона

B-деревья с этим справляются. Кроме того, ты можешь просто вести подсчет количества ключей (упрощенно, хранить в дереве не struct { int key; } а struct { int key; int nkeys; }).

вобщем всем спасибо - натолкнули на светлые мысли

Ещё можно посмотреть код прюфера - он самый компактный для деревьев. Возможно тебе подойдёт.