Хранение древесных конструкций в Mongodb: примеры кода

Это образовательная статья, демонстрирующая подходы для хранения древесных структур с базой данных NoSQL, MongoDB.

Задний план

В реальной жизни практически любой проект имеет дело с древесными структурами.

Различные виды таксономии, структуры сайта и т. Д., Требуют моделирование иерархических отношений. В этом учебном пособии MongoDB я проиллюстрирую, как использовать пять типичных подходов (плюс одно сочетание работы с иерархиями данных) на примерном наборе данных.

Эти подходы:

Модель дерева Структуры с дочерними ссылками
Структуры дерева модели с родительскими ссылками
Модель дерева структур с массивом предков
Модель дерева Структуры с материализованными путями
Модель дерева Структуры с вложенными наборами

Примечание: Эта статья вдохновлена другой статьей ‘ Модель дерева Структуры в Монгодб «Монгодб, но не копирует это. Вместо этого учебник дает Дополнительные примеры на типичных операциях с управлением деревами. Пожалуйста, обратитесь к статье MongoDB, чтобы получить более твердое понимание подхода.

Во всяком случае, я буду использовать необходимую таксономию Fake Fake E-Shop для демонстрационного набора данных.

Проблемы для решения

В типичном сценарии сайта мы должны быть в состоянии:

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

В соответствующие примерные ситуации мы будем работать, являются как:

Добавить новый узел под названием LG под электроникой
Переместить LG Узел под Cell_phones_and_smartphones узел
Удалить LG Узел из дерева
Получить детей узлов Электроника узел
Получите путь к Nokia узел
Получить все потомки Cell_Phones_and_acessories узел

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

Структура дерева с родительской ссылкой

Это наиболее часто используемый подход. Для каждого узла мы храним ID , ParentReference и Заказать :

Работать с деревом

Это довольно просто, но изменение положения узла внутри братьев и сестер потребует дополнительных расчетов. Возможно, вы захотите установить высокие номера, такие как позиция предмета * 10 ^ 6 Для заказа, чтобы вы могли установить новый узел порядок как trunch (порядок нижнего брата - более высокий братский завод)/2 – Это даст вам достаточно операций, пока вам не нужно будет пройти целое дерево и настроить по умолчанию по умолчанию на большие числа.

Добавление нового узла

var existingelemscount = db.categoriesPCO.find({parent:'Electronics'}).count();
var neworder = (existingelemscount+1)*10;
db.categoriesPCO.insert({_id:'LG', parent:'Electronics', someadditionalattr:'test', order:neworder})
//{ "_id" : "LG", "parent" : "Electronics", "someadditionalattr" : "test", "order" : 40 }

Обновление/перемещение узла

existingelemscount = db.categoriesPCO.find({parent:'Cell_Phones_and_Smartphones'}).count();
neworder = (existingelemscount+1)*10;
db.categoriesPCO.update({_id:'LG'},{$set:{parent:'Cell_Phones_and_Smartphones', order:neworder}});
//{ "_id" : "LG", "order" : 60, "parent" : "Cell_Phones_and_Smartphones", "someadditionalattr" : "test" }

Удаление узла

db.categoriesPCO.remove({_id:'LG'});

Получение узел детей (заказано)

db.categoriesPCO.find({$query:{parent:'Electronics'}, $orderby:{order:1}})
//{ "_id" : "Cameras_and_Photography", "parent" : "Electronics", "order" : 10 }
//{ "_id" : "Shop_Top_Products", "parent" : "Electronics", "order" : 20 }
//{ "_id" : "Cell_Phones_and_Accessories", "parent" : "Electronics", "order" : 30 }

Получение всех потомков узла

К сожалению, также включает рекурсивную работу

var descendants=[]
var stack=[];
var item = db.categoriesPCO.findOne({_id:"Cell_Phones_and_Accessories"});
stack.push(item);
while (stack.length>0){
    var currentnode = stack.pop();
    var children = db.categoriesPCO.find({parent:currentnode._id});
    while(true === children.hasNext()) {
        var child = children.next();
        descendants.push(child._id);
        stack.push(child);
    }
}


descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,Nokia,Samsung,Apple,HTC,Vyacheslav

Получение пути к узлу

К сожалению, это включает рекурсивные операции:

var path=[]
var item = db.categoriesPCO.findOne({_id:"Nokia"})
while (item.parent !== null) {
    item=db.categoriesPCO.findOne({_id:item.parent});
    path.push(item._id);
}

path.reverse().join(' / ');
//Electronics / Cell_Phones_and_Accessories / Cell_Phones_and_Smartphones

Индексы

Рекомендуемый индекс находится на полях родителя и порядок

db.categoriesPCO.ensureIndex( { parent: 1, order:1 } )

Структура дерева с дочерней ссылкой

Для каждого узла мы будем хранить ID и ChildReferences Отказ

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

Добавление нового узла

db.categoriesCRO.insert({_id:'LG', childs:[]});
db.categoriesCRO.update({_id:'Electronics'},{  $addToSet:{childs:'LG'}});
//{ "_id" : "Electronics", "childs" : [ 	"Cameras_and_Photography", 	"Shop_Top_Products", 	"Cell_Phones_and_Accessories", 	"LG" ] }

Обновление/перемещение узла

Перестановка ордера под тем же родителем:

db.categoriesCRO.update({_id:'Electronics'},{$set:{"childs.1":'LG',"childs.3":'Shop_Top_Products'}});
//{ "_id" : "Electronics", "childs" : [ 	"Cameras_and_Photography", 	"LG", 	"Cell_Phones_and_Accessories", 	"Shop_Top_Products" ] }

Перемещение узла:

db.categoriesCRO.update({_id:'Cell_Phones_and_Smartphones'},{  $addToSet:{childs:'LG'}});
db.categoriesCRO.update({_id:'Electronics'},{$pull:{childs:'LG'}});
//{ "_id" : "Cell_Phones_and_Smartphones", "childs" : [ "Nokia", "Samsung", "Apple", "HTC", "Vyacheslav", "LG" ] }

Удаление узла

db.categoriesCRO.update({_id:'Cell_Phones_and_Smartphones'},{$pull:{childs:'LG'}})
db.categoriesCRO.remove({_id:'LG'});

Получение узел детей (заказано)

Примечание: Это требует дополнительной сортировки на стороне клиента в родительской последовательности массива

var parent = db.categoriesCRO.findOne({_id:'Electronics'})
db.categoriesCRO.find({_id:{$in:parent.childs}})

Результат:

{ "_id" : "Cameras_and_Photography", "childs" : [ 	"Digital_Cameras", 	"Camcorders", 	"Lenses_and_Filters", 	"Tripods_and_supports", 	"Lighting_and_studio" ] }
{ "_id" : "Cell_Phones_and_Accessories", "childs" : [ 	"Cell_Phones_and_Smartphones", 	"Headsets", 	"Batteries", 	"Cables_And_Adapters" ] }
{ "_id" : "Shop_Top_Products", "childs" : [ "IPad", "IPhone", "IPod", "Blackberry" ] }

//parent:
{
  "_id" : "Electronics",
  "childs" : [
    "Cameras_and_Photography",
    "Cell_Phones_and_Accessories",
    "Shop_Top_Products"
  ]
}

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

Получение всех потомков узла

var descendants=[]
var stack=[];
var item = db.categoriesCRO.findOne({_id:"Cell_Phones_and_Accessories"});
stack.push(item);
while (stack.length>0){
    var currentnode = stack.pop();
    var children = db.categoriesCRO.find({_id:{$in:currentnode.childs}});

    while(true === children.hasNext()) {
        var child = children.next();
        descendants.push(child._id);
        if(child.childs.length>0){
          stack.push(child);
        }
    }
}

//Batteries,Cables_And_Adapters,Cell_Phones_and_Smartphones,Headsets,Apple,HTC,Nokia,Samsung
descendants.join(",")

Получение пути к узлу

var path=[]
var item = db.categoriesCRO.findOne({_id:"Nokia"})
while ((item=db.categoriesCRO.findOne({childs:item._id}))) {
    path.push(item._id);
}

path.reverse().join(' / ');
//Electronics / Cell_Phones_and_Accessories / Cell_Phones_and_Smartphones
```sql

### Indexes
Recommended index is putting index on childs:
```sql
db.categoriesCRO.ensureIndex( { childs: 1 } )

Структура дерева с массивом предков

Для каждого узла мы будем хранить ID , ParentReference и Предки Как в примере ниже:

Добавление нового узла

var ancestorpath = db.categoriesAAO.findOne({_id:'Electronics'}).ancestors;
ancestorpath.push('Electronics')
db.categoriesAAO.insert({_id:'LG', parent:'Electronics',ancestors:ancestorpath});
//{ "_id" : "LG", "parent" : "Electronics", "ancestors" : [ "Electronics" ] }

Обновление/перемещение узла

Перемещение узла:

ancestorpath = db.categoriesAAO.findOne({_id:'Cell_Phones_and_Smartphones'}).ancestors;
ancestorpath.push('Cell_Phones_and_Smartphones')
db.categoriesAAO.update({_id:'LG'},{$set:{parent:'Cell_Phones_and_Smartphones', ancestors:ancestorpath}});
//{ "_id" : "LG", "ancestors" : [ 	"Electronics", 	"Cell_Phones_and_Accessories", 	"Cell_Phones_and_Smartphones" ], "parent" : "Cell_Phones_and_Smartphones" }

Удаление узла

db.categoriesAAO.remove({_id:'LG'});

Получать узел детей (неупорядоченные)

Примечание: Если вы не представите поле заказа, невозможно получить заказанный список детей узла. Вы должны рассмотреть Еще один подход, если вам нужно его заказано.

db.categoriesAAO.find({$query:{parent:'Electronics'}})

Получение всех потомков узла

Есть два варианта, чтобы получить все потомки узла. Один – классический подход через рекурсию:

var ancestors = db.categoriesAAO.find({ancestors:"Cell_Phones_and_Accessories"},{_id:1});
while(true === ancestors.hasNext()) {
       var elem = ancestors.next();
       descendants.push(elem._id);
   }
descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,Nokia,Samsung,Apple,HTC,Vyacheslav

Другой – использовать агрегационную структуру, введенную в MongoDB 2.2:

var aggrancestors = db.categoriesAAO.aggregate([
    {$match:{ancestors:"Cell_Phones_and_Accessories"}},
    {$project:{_id:1}},
    {$group:{_id:{},ancestors:{$addToSet:"$_id"}}}
])

descendants = aggrancestors.result[0].ancestors
descendants.join(",")
//Vyacheslav,HTC,Samsung,Cables_And_Adapters,Batteries,Headsets,Apple,Nokia,Cell_Phones_and_Smartphones

Структура дерева с материализованным путем

Для каждого узла мы будем хранить ID и Патритоведение

Добавление нового узла

var ancestorpath = db.categoriesMP.findOne({_id:'Electronics'}).path;
ancestorpath += 'Electronics,'
db.categoriesMP.insert({_id:'LG', path:ancestorpath});
//{ "_id" : "LG", "path" : "Electronics," }

Обновление/перемещение узла

Перемещение узла

ancestorpath = db.categoriesMP.findOne({_id:'Cell_Phones_and_Smartphones'}).path;
ancestorpath +='Cell_Phones_and_Smartphones,'
db.categoriesMP.update({_id:'LG'},{$set:{path:ancestorpath}});
//{ "_id" : "LG", "path" : "Electronics,Cell_Phones_and_Accessories,Cell_Phones_and_Smartphones," }

Удаление узла

db.categoriesMP.remove({_id:'LG'});

Получение узла детей (неупорядоченная):

Примечание: Если вы не введуете поле заказа, невозможно заказать список детей узла. Вы должны рассмотреть еще один подход, если вам нужен заказ.

db.categoriesMP.find({$query:{path:'Electronics,'}})
//{ "_id" : "Cameras_and_Photography", "path" : "Electronics," }
//{ "_id" : "Shop_Top_Products", "path" : "Electronics," }
//{ "_id" : "Cell_Phones_and_Accessories", "path" : "Electronics," }

Получение всех потомков узла

Одноместный выбор, Regexp начинается с ^ , что позволяет использовать индекс для соответствия

var descendants=[]
var item = db.categoriesMP.findOne({_id:"Cell_Phones_and_Accessories"});
var criteria = '^'+item.path+item._id+',';
var children = db.categoriesMP.find({path: { $regex: criteria, $options: 'i' }});
while(true === children.hasNext()) {
  var child = children.next();
  descendants.push(child._id);
}


descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,Nokia,Samsung,Apple,HTC,Vyacheslav

Получение пути к узлу

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

var path=[]
var item = db.categoriesMP.findOne({_id:"Nokia"})
print (item.path)
//Electronics,Cell_Phones_and_Accessories,Cell_Phones_and_Smartphones,

Индексы

Рекомендуемый индекс вкладывает индекс на пути

  db.categoriesAAO.ensureIndex( { path: 1 } )

Структура дерева с вложенными наборами

Для каждого узла мы будем хранить ID , левый и правильно :

Левое поле также можно рассматривать как поле заказа

Добавление нового узла

Пожалуйста, обратитесь к изображению выше. Предположим, что мы хотим вставить LG узел после shop_top_products (14,23) Отказ Новый узел будет иметь левое значение 24 , что повлияет на все остальные левые значения в соответствии с правилами обхода. У него также будет иметь правильное значение 25 , что повлияет на все остальные правильные значения, включая корневой.

Шаги, чтобы добавить узел:

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

var followingsibling = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});

var newnode = {_id:'LG', left:followingsibling.left,right:followingsibling.left+1}

db.categoriesNSO.update({right:{$gt:followingsibling.right}},{$inc:{right:2}}, false, true)

db.categoriesNSO.update({left:{$gte:followingsibling.left}, right:{$lte:followingsibling.right}},{$inc:{left:2, right:2}}, false, true)

db.categoriesNSO.insert(newnode)

Давайте проверим результат:

 +-Electronics (1,46)
     +---Cameras_and_Photography (2,13)
           +------Digital_Cameras (3,4)
           +------Camcorders (5,6)
           +------Lenses_and_Filters (7,8)
           +------Tripods_and_supports (9,10)
           +------Lighting_and_studio (11,12)
       +----Shop_Top_Products (14,23)
           +------IPad (15,16)
           +------IPhone (17,18)
           +------IPod (19,20)
           +------Blackberry (21,22)
       +----LG (24,25)
       +----Cell_Phones_and_Accessories (26,45)
           +------Cell_Phones_and_Smartphones (27,38)
                 +---------Nokia (28,29)
                 +---------Samsung (30,31)
                 +---------Apple (32,33)
                 +---------HTC (34,35)
                 +---------Vyacheslav (36,37)
             +-------Headsets (39,40)
             +-------Batteries (41,42)
             +-------Cables_And_Adapters (43,44)

Удаление узла

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

Примечание: Узел Удаление без удаления своих детей не выходит из объема этой статьи. На данный момент мы предполагаем, что Узел для удаления нет детей, то есть.

Шаги для удаления узла идентичны шагам для добавления узла – I.E. Мы регулируем пространство, уменьшая пораженные значения влево/правильные значения, а также путем удаления исходного узла.

var nodetoremove = db.categoriesNSO.findOne({_id:"LG"});

if((nodetoremove.right-nodetoremove.left-1)>0.001) {
    print("Only node without childs can be removed")
    exit
}

var followingsibling = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});

//update all remaining nodes
db.categoriesNSO.update({right:{$gt:nodetoremove.right}},{$inc:{right:-2}}, false, true)
db.categoriesNSO.update({left:{$gt:nodetoremove.right}},{$inc:{left:-2}}, false, true)
db.categoriesNSO.remove({_id:"LG"});

Давайте проверим результат:

 +-Electronics (1,44)
   +--Cameras_and_Photography (2,13)
         +-----Digital_Cameras (3,4)
         +-----Camcorders (5,6)
         +-----Lenses_and_Filters (7,8)
         +-----Tripods_and_supports (9,10)
         +-----Lighting_and_studio (11,12)
     +---Shop_Top_Products (14,23)
         +-----IPad (15,16)
         +-----IPhone (17,18)
         +-----IPod (19,20)
         +-----Blackberry (21,22)
     +---Cell_Phones_and_Accessories (24,43)
         +-----Cell_Phones_and_Smartphones (25,36)
               +--------Nokia (26,27)
               +--------Samsung (28,29)
               +--------Apple (30,31)
               +--------HTC (32,33)
               +--------Vyacheslav (34,35)
           +------Headsets (37,38)
           +------Batteries (39,40)
           +------Cables_And_Adapters (41,42)

Обновление/перемещение одного узла

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

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

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

В качестве примера давайте переместим LG Узел из примера вставки под Cell_phones_and_smartphones Узел как последний брат (то есть у вас нет следующего узла брата, как в примере вставки)

Шаг 1 было бы удалить LG Узел из дерева с использованием процедуры удаления узла, описанной выше.

Шаг2 состоит в том, чтобы взять правильное значение нового родителя.

Новый узел будет иметь левое значение правильного значения его родителей. Правильное значение будет правильным значением его родителей, увеличиваемых на 1.

Теперь мы должны создать место для нового узла: Обновление влияет на правильные значения всех узлов на дополнительном пути траверса

var newparent = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Smartphones"});
var nodetomove = {_id:'LG', left:newparent.right,right:newparent.right+1}


//3th and 4th parameters: false stands for upsert=false and true stands for multi=true
db.categoriesNSO.update({right:{$gte:newparent.right}},{$inc:{right:2}}, false, true)
db.categoriesNSO.update({left:{$gte:newparent.right}},{$inc:{left:2}}, false, true)

db.categoriesNSO.insert(nodetomove)

Давайте проверим результат:

 +-Electronics (1,46)
   +--Cameras_and_Photography (2,13)
         +-----Digital_Cameras (3,4)
         +-----Camcorders (5,6)
         +-----Lenses_and_Filters (7,8)
         +-----Tripods_and_supports (9,10)
         +-----Lighting_and_studio (11,12)
     +---Shop_Top_Products (14,23)
         +-----iPad (15,16)
         +-----iPhone (17,18)
         +-----iPod (19,20)
         +-----Blackberry (21,22)
     +---Cell_Phones_and_Accessories (24,45)
         +-----Cell_Phones_and_Smartphones (25,38)
                 +---------Nokia (26,27)
                 +---------Samsung (28,29)
                 +---------Apple (30,31)
                 +---------HTC (32,33)
                 +---------Vyacheslav (34,35)
                 +---------LG (36,37)
             +-------Headsets (39,40)
             +-------Batteries (41,42)
             +-------Cables_And_Adapters (43,44)

Получать узел детей (неупорядоченные)

Примечание: Если у всех узел у детей нет детей самих детей, невозможно получить прямой ребенок узла.

Рассмотрите возможность использования модифицированного подхода сочетания Gestedsets с родительским полем.

Получение всех потомков узла

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

var descendants=[]
var item = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});
print ('('+item.left+','+item.right+')')
var children = db.categoriesNSO.find({left:{$gt:item.left}, right:{$lt:item.right}}).sort(left:1);
while(true === children.hasNext()) {
  var child = children.next();
  descendants.push(child._id);
}


descendants.join(",")
//Cell_Phones_and_Smartphones,Headsets,Batteries,Cables_And_Adapters,Nokia,Samsung,Apple,HTC,Vyacheslav

Получение пути к узлу

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

var path=[]
var item = db.categoriesNSO.findOne({_id:"Nokia"})

var ancestors = db.categoriesNSO.find({left:{$lt:item.left}, right:{$gt:item.right}}).sort({left:1})
while(true === ancestors.hasNext()) {
  var child = ancestors.next();
  path.push(child._id);
}

path.join('/')
// Electronics/Cell_Phones_and_Accessories/Cell_Phones_and_Smartphones

Индексы

Рекомендуемый индекс является индекс в левом и правом значении:

  db.categoriesAAO.ensureIndex( { left: 1, right:1 } )

Структура дерева с использованием комбинации

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

Для каждого узла мы будем хранить ID , Родитель , Заказать , левый и правильно :

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

Добавление нового узла

Добавление нового узла может быть принята из вложенных наборов таким образом:

var followingsibling = db.categoriesNSO.findOne({_id:"Cell_Phones_and_Accessories"});
var previoussignling = db.categoriesNSO.findOne({_id:"Shop_Top_Products"});
var neworder = parseInt((followingsibling.order + previoussignling.order)/2);
var newnode = {_id:'LG', left:followingsibling.left,right:followingsibling.left+1, parent:followingsibling.parent, order:neworder};
db.categoriesNSO.update({right:{$gt:followingsibling.right}},{$inc:{right:2}}, false, true)
db.categoriesNSO.update({left:{$gte:followingsibling.left}, right:{$lte:followingsibling.right}},{$inc:{left:2, right:2}}, false, true)

db.categoriesNSO.insert(newnode)

Перед вставкой

          +----Cameras_and_Photography (2,13)  ord.[10]
          +-----Shop_Top_Products (14,23)  ord.[20]
          +-----Cell_Phones_and_Accessories (26,45)  ord.[30]

После вставки:

   +--Electronics (1,46) 
           +----Cameras_and_Photography (2,13)  ord.[10]
                       +-------Digital_Cameras (3,4)  ord.[10]
                       +-------Camcorders (5,6)  ord.[20]
                       +-------Lenses_and_Filters (7,8)  ord.[30]
                       +-------Tripods_and_supports (9,10)  ord.[40]
                       +-------Lighting_and_studio (11,12)  ord.[50]
           +-----Shop_Top_Products (14,23)  ord.[20]
                       +-------IPad (15,16)  ord.[10]
                       +-------IPhone (17,18)  ord.[20]
                       +-------IPod (19,20)  ord.[30]
                       +-------Blackberry (21,22)  ord.[40]
           +-----LG (24,25)  ord.[25]
           +-----Cell_Phones_and_Accessories (26,45)  ord.[30]
                       +-------Cell_Phones_and_Smartphones (27,38)  ord.[10]
                                   +----------Nokia (28,29)  ord.[10]
                                   +----------Samsung (30,31)  ord.[20]
                                   +----------Apple (32,33)  ord.[30]
                                   +----------HTC (34,35)  ord.[40]
                                   +----------Vyacheslav (36,37)  ord.[50]
                       +--------Headsets (39,40)  ord.[20]
                       +--------Batteries (41,42)  ord.[30]
                       +--------Cables_And_Adapters (43,44)  ord.[40]

Обновление/перемещение одного узла

Это будет идентично для введения подхода

Удаление узла

Это будет использовать подход из вложенных наборов.

Получение узел детей (заказано)

Это наконец возможно, используя пару (родитель, порядок)

db.categoriesNSO.find({parent:"Electronics"}).sort({order:1});
/*

{ "_id" : "Cameras_and_Photography", "parent" : "Electronics", "order" : 10, "left" : 2, "right" : 13 }
{ "_id" : "Shop_Top_Products", "parent" : "Electronics", "order" : 20, "left" : 14, "right" : 23 }
{ "_id" : "LG", "left" : 24, "right" : 25, "parent" : "Electronics", "order" : 25 }
{ "_id" : "Cell_Phones_and_Accessories", "parent" : "Electronics", "order" : 30, "left" : 26, "right" : 45 }

*/

Получение всех потомков узла

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

Получение пути к узлу

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

Код в действии

Вы можете скачать код из Github Отказ

Все файлы упаковываются в соответствии со следующей Конвенцией о именовании:

ModelReference.js – Файл инициализации с данными деревьев для модельного подхода
ModelReference_Operating.js – Добавить/обновить/переместить/удалить/получить примеры детей
ModelReference_Pathonode.js – код, иллюстрирующий, как получить путь к узлу
ModelReference_nodedEscendantans.js – код, иллюстрирующий, как получить все потомки узла

Окончательные слова

Обратите внимание, что Mongodb не обеспечивает кислотные транзакции. Это означает, что для операций обновления разделены на отдельные команды обновления, ваше приложение должно реализовать дополнительный код для поддержки ваших операций, специфичных к кодам.

Формальный совет MongoDB выглядит следующим образом:

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

Вы можете смешать узоры (введя поле заказа и т. Д.) Для соответствия операциям данных, необходимых для вашего приложения.

Задний план

Проблемы для решения

Структура дерева с родительской ссылкой

Работать с деревом

Добавление нового узла

Обновление/перемещение узла

Удаление узла

Получение узел детей (заказано)

Получение всех потомков узла

Получение пути к узлу

Индексы

Структура дерева с дочерней ссылкой

Добавление нового узла

Обновление/перемещение узла

Удаление узла

Получение узел детей (заказано)

Получение всех потомков узла

Получение пути к узлу

Структура дерева с массивом предков

Добавление нового узла

Обновление/перемещение узла

Удаление узла

Получать узел детей (неупорядоченные)

Получение всех потомков узла

Структура дерева с материализованным путем

Добавление нового узла

Обновление/перемещение узла

Удаление узла

Получение узла детей (неупорядоченная):

Получение всех потомков узла

Получение пути к узлу

Индексы

Структура дерева с вложенными наборами

Добавление нового узла

Удаление узла

Обновление/перемещение одного узла

Получать узел детей (неупорядоченные)

Получение всех потомков узла

Получение пути к узлу

Индексы

Структура дерева с использованием комбинации

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

Добавление нового узла

Обновление/перемещение одного узла

Удаление узла

Получение узел детей (заказано)

Получение всех потомков узла

Получение пути к узлу

Код в действии

Окончательные слова

Читайте ещё по теме: