Дерево в файле

[Space]

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

[RayShade]

XML

[jangle]

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

[Хакер]

Рэй, ты всюду XML будешь рекламировать, не читая, о чём просят?

[RayShade]

Пока не придумали более эффективного не бинарного метода хранения древовидных структур, буду

[Хакер]

Бинарность рулит в рамках данной задачи.

[RayShade]

Бинарность как мне кажется, отрицается автором топика Но в любом случае, XML's like a violence - if it doesn't solve all your problems you're simply not using enough of it

[Хакер]

XML — классная вещь, но только не здесь.

Два недостатка текстовых форматов хранения данных: за маркеры формата могут приняты части хранимых данных, значит, надо обеспечить, чтобы в данных не встретилось ничего похожего на форматные маркеры. Способа сделать это так, чтобы хранимые данные не увеличились в размере, не существует.

Чтобы найти "конец данных", надо просканировать каждый символ этих данных.

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

[RayShade]

Какие маркеры? О чем это ты? Единственная проблема, которая тут может быть - это объем Но все равно проще чем написать схему, засунуть данные в разметку из тегов и потом искать/читать/писать через DOM - врядли что то придумается.

[ANDLL]

Действительно! DOM наше все! И зачем всякие идиоты придумывают SAX, для чтения того же XML?
И зачем придумывают двоичные аналоги? Что может быть проще - распарсить файл в модель и вынуть нужные ноды с помощью одного xpath'а. Ведь не бывает же файлов на диске размером больше чем ОЗУ компьютера, все то сказки будто бы DOM может не влезть в оперативку. Затолкают.

[Space]

Ведь не бывает же файлов на диске размером больше чем ОЗУ компьютера

Бывает и ещё как. А даже и влезет в ОЗУ, мне жалко забивать ОЗУ таким объёмом данных. Да, если кто не понял, мне надо читать только 1 веточку с последовательным выбором "Страна-Область-Город..." Где бы ещё данные выкачать

[ANDLL]

Ведь не бывает же файлов на диске размером больше чем ОЗУ компьютера

Бывает и ещё как.

Так, добро пожаловать страну сарказма

[Space]

ANDLL, у меня ОЗУ 512Мб, а файлы бывают под 2Гб. А бывает ОЗУ и меньше. Читай также правку предыдущего поста.

[ANDLL]

Госпаде, space, ну и туго же до вас доходит этим утром
На, читай: http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 0%B7%D0%BC

[Space]

о, у вас ещё утро

[Zenitchik]

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

Стоп. Нужен именно двоичный алгоритм... Дерево - суть ацикличный орграф. Если сделать записи вида
(Адрес родителя, Адрес первого потомка, Адрес следующего на уровне, Длина содержимого, Содержимое)

[Александр Дмитриев]

Дерево - суть ацикличный орграф.

Связный ациклический граф. Хотя здесь, по-моему, связности нет, ацикличность проверять долго и не нужно, да и граф не граф, а орграф

А что если использовать чанки? По-моему, здесь подойдут чанки с таким заголовком: длина чанка, длина содержимого непосредственно самого чанка, далее непосредственное содержимое чанка, далее сабчанки.

(Адрес родителя, Адрес первого потомка, Адрес следующего на уровне, Длина содержимого, Содержимое)

А ведь адрес следующего на уровне может быть вычислен через длину содержимого.

Space А данные велики из-за размеров элементов дерева или из-за кол-ва элементов?

[Space]

ну смотри: выбираем Страну -> массив областей Страны -> массив Городов области...

[Александр Дмитриев]

То есть средний размер элемента дерева 10-15 символов, а элементов вплоть до сот миллионов и больше? (По-моему только так могут получится Гб)

[Space]

ну не знаю, но чувтвую одним местом, будет очень много. Я ещё не выкачал списки, ищу...

[iGrok]

ну не знаю, но чувтвую одним местом, будет очень много. Я ещё не выкачал списки, ищу...

Вообще, бинарная бд GeoIP со странами весит метр. С регионами - около 5 метров что ли.. С городами, кажись метров 30.. Понятное дело, там далеко не всё.. Но тем не менее.

Вот импортированная в аксесс - да. 300 метров. Но у аксесса избыточность данных поистине безумная. )

Так что кажется мне, до гигабайта ты не дотянешь.

[alibek]

Так что кажется мне, до гигабайта ты не дотянешь.

А какая связь?
Гигабайт, если что, это миллиард, а не миллион.

[iGrok]

Гигабайт, если что, это миллиард, а не миллион.

Я в курсе. )

Ну, как, какая связь? У него же БД стран/регионов/городов/и т.п.. А GeoIP это что такое?

Нет, я не забыл, что у него там ещё какая-то информация помимо просто названий городов. Ну так и разница между гигабайтом и 30 мегабайтами несколько.. Как бы это сказать.. Существенная, что ли? )

Мне думается, там суммарный объём всё-таки будет существенно меньше гигабайта.

[Space]

30 Метров в распакованном виде? А мне и 30 метров памяти жалко Я всё равно буду держать в файле и читать оттуда только нужное, тем более, чтение совсем не частое.

[iGrok]

30 Метров в распакованном виде? А мне и 30 метров памяти жалко Я всё равно буду держать в файле и читать оттуда только нужное, тем более, чтение совсем не частое.

Да.. 27883К. Только что посмотрел. Судя по внутренностям APIшки для работы с нею - она не жатая.. Правда, текста в чистом виде я внутри не нашёл.
Так что хрен её. Я особо не копался..

Но насчёт целесообразности - полностью согласен. Лучше грузить что-то типа индекса (или корень) в память, а потом вытаскивать ветки куста по необходимости..

Тут есть ещё момент. Тебе нужна возможность легко, быстро и просто изменять содержимое, или там в будут статические данные, обновляемые крайне редко?

[Space]

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

[iGrok]

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

Ну отгда вариант с chunk'ами, предложенный Александром Дмитриевым весьма неплох..
Стран у нас не очень много - это будут корневые записи, потом регионы - сабчанки в странах, города - сабчанки в регионах, и т.п.
Если читаться в основном будут именно все значения категории (выбрали страну - показали все подходящие регионы, выбрали регион - показали все подходящие города, и т.п.) тогда это действительно удобно, и реально быстро. В принципе, даже изменять файл такого формата не очень сложно, ибо все значения относительные, все указатели вычисляются исходя из размеров чанков.. Т.е. при изменении значения просто сдвигаем остаток файла на нужное место, после чего проходимся вверх до корня, правя размеры чанков.

Очень неудобным будет обратный поиск - в каком регионе находится конкретный город - придётся перебирать ВЕСЬ файл, или строить дополнительный индекс.

[Zenitchik]

Код: Выделить всё

может быть вычислен через длину содержимого

А где гарантия, что они идут последовательно?

[Александр Дмитриев]

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