Оптимизация доступа к данным в деревьях

[Utkin]

Я не понимаю - чем все что описано отличается от ближайшей файловой системы?

Чисто внешне да, бинго! Внутренне я знаю очень поверхностно, фактически не знаю никак. С другой стороны хочу сказать, что в файловой системе не то чтобы прям много элементов - тормоза от 10000 элементов будут наверно. В моем случае число детей неизвестно и может быть теоретически больше 10 000.

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

Имена там пример, но суть верная - имена строки.

[waleri]

У меня на диске (NTFS) больше двух миллионов файлов - тормозов не замечаю, правда специальных бенчмарков не делал...

Почитайте организацию как-либо файловой системы по-новее (а то ФАТ конечно не айс) - наверняка натолкнет на идеи.

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

[Utkin]

У меня на диске (NTFS) больше двух миллионов файлов

Ну они же не в одной папке накиданы, а вообще по диску. А вот конкретно в одну папку накидайте тысяч 20 файлов и попробуйте пооткрывать.

Почитайте организацию как-либо файловой системы по-новее (а то ФАТ конечно не айс) - наверняка натолкнет на идеи.

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

(говорю про виндовс, хотя наверняка и на лин есть подобное)

Там это штатная фича, можно шифровать на лету.

[Pavia]

Вы видите проблему или нет? Я дал конкретную задачу:
Есть 2 пути - источник Планета-Континенты-Европа-Москва, приемник Планета-Континенты-Австралия. Перенесите Москву в Австралию. Когда поэтапно будете это делать - увидите что мне не нравится.

Прекрасно вижу. Я всё это уже делал во многих вариантах. А вот вы пока ходите в потемках. Любую операцию можно сделать за T(1) :
и вставку, и удаление, и поиск, и индексный доступ, и обмен - но в разных коллекциях.
Какие-то коллекции можно скрестить, какие-то нельзя. Задачу надо рассматривать глобально, что бы найти оптимум для вашей задачи.
Если никакие критерии неизвестны, то берем Деревья-Б+ она для всех четырех операций дает O(Log(N)).

Чудес не бывает. Каждая коллекция имеет свои недостатки.

Файловые системы NFTS и EXT2, EXT3, EXT4 используют Деревья-Б+

А вот конкретно в одну папку накидайте тысяч 20 файлов и попробуйте пооткрывать.

У меня не тормозит. Особенно если своим файловым менеджером открывать.

[Utkin]

Дайте мне пошагово для указанного выше примера. Все же просто. Мне нужен алгоритм, условия задачи выше. Использовать только указанную структуру деревьев, что указана в первом посте. Её физическая реализация в данном случае не важна.

Особенно если своим файловым менеджером открывать.

Мне вот и нужно знать как быстро открывать.

Файловые системы NFTS и EXT2, EXT3, EXT4 используют Деревья-Б+

Я вот глянул Reiser FS - почти тот же самый велосипед, что и мы изобретаем. Разница в том, что нужно как-то сортировать массив. Есть идеи? Проблема там описанная как раз показывает, что нужен внешний какой-то индексатор. Ровно то чего я хочу, помноженный на рецепт от evg_m.

[MihalNik]

Сообщение от Utkin

 Nodes: Array of TSNode;// Набор узлов

Вот сразу написал, что надо делать на нижнем уровне.
Array выкинуть, это не деревья, заменить за самоупорядочивающееся древовидное строение (аля map на красно-черных деревьях там есть, или обертка или переписано по STL).
http://wiki.freepascal.org/Data_Stru...s,_Collections

[oldsnowman]

полюбопытствую, а зачем вся эта морока с массивам, узлами да рекурсиями? Ведь можно sql-ем сделать. Уткин, пишите кому-то дипломную, или просто решили поэкспериментировать?

[Utkin]

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

Ведь можно sql-ем сделать.

Никто от БД не отказывается, речь об обычных программных данных - массивы, списки, записи и т.д.

Array выкинуть, это не деревья, заменить за самоупорядывающееся древовидное строение

Там внутри тоже Array - ОЗУ все равно линейно и рано или поздно кто-то должен начать оборачивать массив во что-то высокоинтеллектуальное.

[MihalNik]

Сообщение от Utkin

Там внутри тоже Array - ОЗУ все равно линейно и рано или поздно кто-то должен начать оборачивать массив во что-то высокоинтеллектуальное.

Там уже есть коллекции с временем поиска, вставки и удаления окололинейно log(N).