Python-сообщество

Вот понадобилось нарисовать деревья немного поискав примеры нашол http://wiki.apache.org/couchdb/How_to_store_hierarchical_data вроде неплохой пример но на начальной стадии реализации возникла ошибка, при выполнении редуса:

function(keys, vals) {
    tree = {};
    for (var i in vals)
    {
        current = tree;
        for (var j in vals[i].path)
        {
            child = vals[i].path[j];
            if (current[child] == undefined) 
                current[child] = {};
            current = current[child];
        } 
        current['_data'] = vals[i];
    }
    return tree;
}

{"error":"reduce_overflow_error","message":"Reduce output must shrink more rapidly: Current output: ..."}

Отредактировано (Дек. 5, 2010 01:13:44)

Мне кажется я нашол решение этого вопроса, насколько я понял ограничение на редус существовало до 0.11 версии http://guide.couchdb.org/draft/cookbook.html по мотивам этой версии была написана эта книга. В 1.0.1 в конфигурации есть параметр reduce_limit по умолчанию он естественно true меняем на false и редус выдает любое количество байт так сказать но я не экспериментировал на больших объемах еще

Как насчет перемещения узла? Ведь у всех потомков нужно изменить path.

В момент перемещения кто-то вставил узел в перемещаемую ветку, или убил процесс/поток… Часть узлов обновили, а другую - нет. Дерево поламалось. Транзакций то нет.

Какие есть идеи?

dimabest
Транзакций то нет.

zheromo

OMG :)

Ты снова одел большие розовые очки и выдаешь желаемое за действительное?

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

{
   "_id": "tree",
   "_rev": "3-cca3e6d9201d3f07784d8578edf7bb87",
   "tree": {
       "3": {  "2": {    },   "4": { "5": {   }   }   },
       "6": {    }
   }
}

Отредактировано (Дек. 6, 2010 09:51:00)

Окак - топик как для меня - я как раз смотрю на реализацию иерархической структуры данных в mongo! Сам нарыл такое - http://stackoverflow.com/questions/1619058/storing-directory-hierarchy-in-a-key-value-data-store - может Вам поможет.

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

не дописал

Отредактировано (Дек. 6, 2010 19:29:33)

По ссылке http://stackoverflow.com/questions/1619058/storing-directory-hierarchy-in-a-key-value-data-store хранить путь в строке советует какой-то дятел. В MongoDB путь надо засунуть в список, поставить на него индекс и получить быстрые и удобные операции по разворачиванию веток, поиску детей и родителей и т.д. У этого метода есть всего 2 минуса:
невозможно безопасно переместить ветку, нет пользовательской сортировки узлов (например, вы хотите, что одни пункты меню были выше других).


Хранения дерева (как дерева) в одном документе решает проблему с перемещением узлов.
Но добавляет другие:

1. нельзя просто получить узел по ID.
Только рекурсивный обход дерева в поисках узла. Если нужно развернуть ветку от корня до узла - все становится еще сложнее.
2. размер документа.
в MongoDB ограничение на размер документа в 4MB, в CouchDB больше (вуху!!), но парсить JSON в несколько мегабайт операция небыстрая. Решение есть - хранить только структуру дерева в одном документе.

Если хранить дерево так:

{
   "_id": "tree",
   "_rev": "3-cca3e6d9201d3f07784d8578edf7bb87",
   "tree": {
       "3": {  "2": {    },   "4": { "5": {   }   }   },
       "6": {    }
   }
}

{
   "_id": "tree",
   "_rev": "3-cca3e6d9201d3f07784d8578edf7bb87",
   "tree": [
       {
           "id": 1,
           "childs": [
                {
                     "id": 11,
                     "childs": []
                },
                {
                     "id": 12,
                     "childs": []
                }
           ]
        },
        {
             "id": 2,
             "childs": []
        }
   ]
}

{
   1: {
       'parent_id': None,
   },
   2: {
       'parent_id': None,
   },
   11: {
       'parent_id': 1,
   },
   12: {
       'parent_id': 1,
   }
}

{
   1: {
       'childs': [11, 12],
   },
   2: {
       'childs': [],
   },
   11: {
       'childs': [],
   },
   12: {
       'childs': [],
   }
}

{
   1: {
       'parent_id': None,
       'childs': [11, 12],
   },
   2: {
       'parent_id': None,
       'childs': [],
   },
   11: {
       'parent_id': 1,
       'childs': [],
   },
   12: {
       'parent_id': 1,
       'childs': [],
   }
}

Отредактировано (Дек. 6, 2010 19:47:58)