Xранение деревьев в MongoDB

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:04, 1 июня 2018.
MongoDB
MongoDB-Logo.svg
Разработчики: MongoDB Inc.
Выпущена: February 2009, 11 (11-02-2009) [1]
Постоянный выпуск: 3.4.9[2] / 11 September 2017 года; 2 years ago (2017-09-11)
Предыдущий выпуск: 3.5.12[3] / 22 August 2017 года; 2 years ago (2017-08-22)
Состояние разработки: Активное
Написана на: C++, C и JavaScript
Операционная система: Windows Vista и позднее, Linux, macOS 10.7 и позднее, Solaris,[4] FreeBSD[5]
Локализация: Английский язык
Тип ПО: Document-oriented database
Лицензия: Various; see § Licensing
Веб-сайт mongodb.org

Очень часто в реальных задачах существует необходимость хранения деревьев. И "MongoDB", благодаря своим особенностям позволяет это реализовать.

Если реляционные базы данных хранят строки, то MongoDB хранит документы. В отличие от строк документы могут хранить сложную по структуре информацию. Документ можно представить как хранилище ключей и значений. Данные в MongoDB имеют гибкую схему. Коллекции не закрепляют структуру документа. Решения, которые влияют на то, как моделировать данные, могут влиять на производительность приложений и емкость базы данных. В "MongoDB" существует несколько способов хранения больших иерархических или вложенных данных с использованием древовидных структур.

Содержание

Методы хранения деревьев

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

Пример дерева, который будет реализован в статье

При работе с деревьями возникают основные задачи:

  • Добавление новой вершины
  • Удаление вершины
  • Перенос вершины
  • Вывод поддерева
  • Вывод детей вершины
  • Вывод пути до вершины

Именно эти функции будут реализованы для каждого метода хранения деревьев.

Чтение из файла

Для удобства тестирования функций мной был написан скрипт, который загружает в память, изображенное на картинке дерево. Каждая вершина указанного дерева хранит: название вершины (id), указатель на ребенка и на брата (sibling). Далее в статье возможно использование названия "стандартное дерево".

function addChild(node, newId) // Функция добавляет ребенка ноде
//В качестве аргументов передается нода и ID ребенка
{
	if (node.child == null) //Если детей у вершины нет, то просто добавляется ссылка на ребенка
	{
		node.child = { id: newId };
		return node.child;
	}
	node = node.child; 
	while (node.sibling != null) //Производится добавление ссылки на новую вершину к братьям
		node = node.sibling;
	node.sibling = { id: newId };
	return node.sibling;
}

function createDefaultTree() //Функция создает "стандартное дерево" с заранне указанными вершинами
{
	var root = { id: "Educational Literature" };
	

	var nl = addChild(root, "Natural Languages");
		addChild(nl, "English");
		addChild(nl, "French");
		addChild(nl, "German");
	var programming = addChild(root, "Programming");
		addChild(programming, "Programming Languages");
		var db = addChild(programming, "Databases");
			addChild(db, "SQL");
			var noSQL = addChild(db, "NoSQL");
				addChild(noSQL, "MongoDB");
				

	return root;
}

Далее можно загрузить этот скрипт в MongoDB с помощью функции load() и сохранить это как переменную.

load("название файла");
var root = createDefaultTree()

Видео

Деревья с ссылкой на родителя

Теория

При выборе данного метода хранения в памяти хранятся ID вершины и ID родителя [Источник 1] .

Работа из консоли

В MongoDB записать дерево из примера можно используя следующие команды.

db.parRef.insert( { _id: "MongoDB", parent: "NoSQL" } )
db.parRef.insert( { _id: "NoSQL", parent: "Databases" } )
db.parRef.insert( { _id: "SQL", parent: "Databases" } )
db.parRef.insert( { _id: "Databases", parent: "Programming" } )
db.parRef.insert( { _id: "Programming Languages", parent: "Programming" } )
db.parRef.insert( { _id: "Programming", parent: "Educational Literature" } )
db.parRef.insert( { _id: "English", parent: "Natural Languages" } )
db.parRef.insert( { _id: "German", parent: "Natural Languages" } )
db.parRef.insert( { _id: "French", parent: "Natural Languages" } )
db.parRef.insert( { _id: "Natural Languages", parent: "Educational Literature" } )
db.parRef.insert( { _id: "Educational Literature", parent: null } )

Тогда узнать родителя вершины будет делом одной команды.

db.parRef.findOne( { _id: "English" } ).parent

Аналогичная ситуация обстоит с поиском детей вершины.

db.ParRef.find( { parent: "Programming" } )

Индексацию будет логично сделать по полю "parent" [Источник 1].

db.parRef.createIndex( { parent: 1 } )

Реализация на JavaScript

Ввод дерева в MongoDB

Однако, если использовать вышеописанный способ загрузки дерева в память (функция createDefaultTree()), то можно загрузить следующий скрипт.

function loadTree(collection, root) //Функция загрузки дерева
//В качестве аргументов передается коллекция и дерево, хранящееся с помощью ссылок на детей и братьев
{
	loadTreeImpl(collection, root, null);	//Чтобы не передавать слишком много аргументов используется вспомогательная функция
    indexing(collection);
}
function indexing(collection) //Индексация проводится по полю родителей
{
	collection.createIndex( { parent: 1 } );	
}
function loadTreeImpl(collection, root, parentId) //Вспомогательная функция
//В качестве аргументов принимает коллекцию, ID вершины и ID родителя вершины
{
	while(true)
	{
		collection.insert({_id: root.id, parent: parentId}); //Добавление новой вершины
		if (root.child != null) //Рекурсивный алгоритм вызывается для всех потомков вершины
			loadTreeImpl(collection, root.child, root.id);

		if (root.sibling == null) //Если у вершины нет братьев, то алгоритм завершает работу
			return;

		root = root.sibling; //Повторяется для всех братьев вершины
	}
}

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

loadTree(db.parRef, root)

Использование предложенной функции позволит сократить время и возможное количество ошибок.

Добавление новой вершины

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

function treeAddNode(collection, rootId, newId) //Функция добавляет новую вершину
//На вход передается коллекция, ID родителя и ID новой вершины 
{
	collection.insert({_id: newId, parent: rootId});
}

И затем эту функцию можно будет использовать следующим образом: необходимо добавить лист "С++" с родителем "Programming Language". Тогда,

treeAddNode(db.parRef, "Programming Language", "C++");
Удаление вершины

Удаление вершины также не требует никаких дополнительных действий.

function treeRemoveNode(collection, id) //Функция удаления вершины
//На вход в качетсве аргументов подается коллекция и ID удаляемой вершины.
{
	collection.remove({ _id: id});
}

Тогда при необходимости удаления листа с названием "С++" можно использовать эту функцию.

treeRemoveNode(db.parRef,  "C++");
Перенос вершины

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

function treeMoveNode(collection, newRootId, id) //Функция переноса вершины
//На вход в качетсве аргументов подается коллекция, ID нового родителя и ID переносимой вершины
{
	collection.update({_id: id },{$set:{parent: newRootId}});
}

Тогда, чтобы переместить лист с названием "English" из ветки "Natural Languages" в ветку "Programming Languages", можно использовать

treeMoveNode(db.parRef, "Programming Languages", "English");
Вывод детей вершины

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

function treePrintChild(collection, root) //Функция вывод детей вершины
//В качестве аргументов передается коллекция и ID вершины.
{
        var childs = collection.find({parent: root}); //Запись в массив всех нод, у которых родитель - указанная вершина
        var childsId = [];
        for (i = 0; i < childs.length(); i++)
        {
                childsId.push(childs[i]._id); //Запись в массив всех ID ранее найденных вершин
        }
        print(childsId.join(',')); //Печать массива через запятую
}

Тогда функцию можно использовать следующим образом.

treePrintChild(db.parRef, "Programming");
Вывод поддерева

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

function treePrint(collection, root) //Функция распечатывает поддерево
//В качестве аргмента подается коллекция и ID корня поддерева, которое надо распечатать
{
	treePrintImpl(collection, root, 1);
}
function treePrintImpl(collection, root, indent) //Вспомогательная функция
//В качестве аргмента подается коллекция, ID корня поддерева и значение отступа
{
	indent+=1; //Отступ увеличивается на один
	print(Array(indent).join("|"), root); //Знак "|" распечатывается indent раз, после него пишется ID вершины
	var childs = collection.find({parent: root}) //Находятся все дети корня
	childs.forEach(function(node, i, childs) //Рекурсивно печатаются все потомки
	{
		treePrintImpl(collection, node._id, indent);
	})
}

Таким образом возможно вывести все дерево:

treePrintChild(db.parRef, "Educational Literature");

или какое-либо поддерево:

treePrint(db.parRef, "Programming");
Вывод пути до вершины

Очень важная функция - функция вывода пути до вершины.

function treeShowPath(collection, nodeId) //Функция печати пути до вершины
//В качестве аргументов передаеют коллекция и ID интересующей ноды
{
        var path =[]; //Создается пустой массив 
        var node = collection.findOne({_id: nodeId}) //По ID находится интересующая нода
        while (node.parent !== null) //Цикл будет выполняться пока не дойдет до корня
        {
		        node = collection.findOne({_id: node.parent}); //Находится нода, являющаяся родителем рассматриваемой в данный момент вершины
                path.push(node._id) //Ее ID записывается в массив
        }
        print(path.reverse().join('/')); //Производится печать массива
}

Видео

Вывод

Используя данный способ хранения деревьев в базе данных можно легко реализовать хранение деревьев, добавление/удаление новых листов. Однако работа с поддеревьями требует значительных затрат по времени[Источник 1].

Деревья с ссылкой на детей

Теория

В дереве, реализованным следующим методом в каждой вершине хранится ID вершины и ID ее детей. Такая реализация удобна при существовании необходимости часто работать именно с детьми, но не с поддеревьями. Также ее можно использовать для реализации графов, когда у вершины есть несколько родителей [Источник 2] .

Работа из консоли

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

db.chiRef.insert( { _id: "MongoDB", childs: [] } )
db.chiRef.insert( { _id: "NoSQL", childs: ["MongoDB"] } )
db.chiRef.insert( { _id: "SQL", childs: [] } )
db.chiRef.insert( { _id: "Databases", childs: [ "NoSQL", "SQL" ] } )
db.chiRef.insert( { _id: "Programming Languages", childs: [] } )
db.chiRef.insert( { _id: "Programming", childs: [ "Programming Languages", "Databases" ] } )
db.chiRef.insert( { _id: "English", childs: [] } )
db.chiRef.insert( { _id: "German", childs: [] } )
db.chiRef.insert( { _id: "French", childs: [] } )
db.chiRef.insert( { _id: "Natural Languages", childs: ["English", "German", "French"] } )
db.chiRef.insert( { _id: "Educational Literature", childs: [ "Programming", "Natural Languages"] } )

Индексацию следует проводить по полю children [Источник 2].

db.chiRef.createIndex( { childs: 1 } )

Реализация на JavaScript

Ввод дерева в MongoDB

Или можно воспользоваться следующим скриптом.

function loadTree(collection, root) //Функция загрузки дерева
//В качестве аргументов передается коллекция и дерево, хранящееся с помощью ссылок на детей и братьев
{
	loadTreeImpl(collection, root, null); //Для удобства использования используется вспомогательная функция
    indexing(collection);
}

function indexing(collection)
{
        collection.createIndex( { childs: 1 } ); //Индексация проводится по полю "childs"       
}
function loadTreeImpl(collection, root, parentId) //Вспомогательная функция
//В качестве аргументов принимает коллекцию, ID вершины и ID родителя вершины
{
	while(true)
	{
		collection.insert({_id: root.id, childs: []}); // Добавление нового листа, массив детей, соответсвенно, пуст
		if (parentId != null) //Если лист не является корнем, то в вершину его родителя добавляется ссылка на нового ребенка
		{
			collection.update({_id:parentId}, {$addToSet: {childs: root.id}})
		}
                if (root.child != null) // Если у добавленной вершины есть дети, то алгоритм рекурсивно для них выполняется
                        loadTreeImpl(collection, root.child, root.id);

                if (root.sibling == null) // Если нет братьев,то алгоритм заканчивает свою работу
                        return;

                root = root.sibling; // Если есть братья, то для них повторяется цикл
        }
}
Добавление новой вершины

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

function treeAddNode(collection, rootId, newId) //Функция добавляет новую вершину
//На вход передается коллекция, ID родителя и ID новой вершины 
{
    collection.insert({_id: newId, childs: []}); //Добавляется вершина с пустым массивом детей и указанным ID
	collection.update({_id: rootId}, {$addToSet: {childs: newId}}); //В вершину родителя добавляется ссылка на новую ноду
}

Воспользоваться функцией можно как и функцией из раздела Parent Reference.

treeAddNode(db.parRef, "Programming Language", "C++");
Удаление вершины

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

function treeRemoveNode(collection, id) //Функция удаления вершины
//На вход в качетсве аргументов подается коллекция и ID удаляемой вершины.
{
	root = collection.findOne({childs: id})._id; //Находится родитель вершины, которую требуется удалить
	collection.update({_id: root}, {$pull: {childs: id}}); //Из массива детей в root удаляется ID вершины
	collection.remove({ _id: id}); //Удаляется сама вершина	
}
Перенос вершины

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

function treeMoveNode(collection, newRootId, id) //Функция переноса вершины
//На вход в качетсве аргументов подается коллекция, ID нового родителя и ID переносимой вершины
{
	oldRoot = collection.findOne({childs: id})._id; //Находится старый родитель переносимой вершины
	collection.update({_id: oldRoot}, {$pull: {childs: id}}); //Из его массива детей удаляется ID переносимой вершины
	collection.update({_id: newRootId },{$addToSet:{childs: id}}); //В массив детей нового родителя добавляется ID переносимой вершины
}
Вывод детей вершины

Благодаря способу хранения дерева в памяти, данная задача не представляет труда.

function treePrintChild(collection, root) //Функция вывод детей вершины
//В качестве аргументов передается коллекция и ID вершины.
{
	print(collection.findOne({_id: root}).childs);
}
Вывод поддерева

Вывод поддерева осуществлен с помощью рекурсивного алгоритма.

function treePrint(collection, root)//Функция распечатывает поддерево
//В качестве аргмента подается коллекция и ID корня поддерева, которое надо распечатать
{
	treePrintImpl(collection, root, 1);
}
function treePrintImpl(collection, root, indent) //Вспомогательная функция
//В качестве аргмента подается коллекция, ID корня поддерева и значение отступа
{
        indent+=1; //Отступ увеличивается на один
        print(Array(indent).join("|"), root); //Знак "|" распечатывается indent раз, после него пишется ID вершины
        var childs = collection.findOne({_id: root}).childs; //Сохраняется массив детей корня
        childs.forEach(function(node, i, childs) //Для каждого элемента массива вызывается функция  treePrintImpl()
        {
                treePrintImpl(collection, node, indent);
        })
}
Вывод пути до вершины

В данном случае решение данной задачи аналогично решению, описанному в методе хранения деревье "Parent Reference".

function treeShowPath(collection, nodeId) //Функция печати пути до вершины
//В качестве аргументов передаеют коллекция и ID интересующей ноды
{
	var path =[]; //Создается пустой массив 
	var node = collection.findOne({_id: nodeId}) //По ID находится интересующая нода
	while ((node = collection.findOne({childs: node._id}))) //Цикл будет выполняться пока не дойдет до корня
	{
		path.push(node._id) //ID ноды записывается в массив
	}
	print(path.reverse().join('/')); //Производится печать массива
}

Видео

Вывод

Этот метод также предоставляется удобное решение для хранения деревьев и работе с листами, но неудобен для работы с поддеревьями. Также этот метод интересен тем, что его можно использовать для хранения графов (когда у вершины может быть несколько родителей) [Источник 2].

Деревья с массивом предков

Теория

При реализации хранения деревьев этим методом в вершине хранится: ID вершины, ID родителя и массив ID всех предков. Шаблон Array of Ancestors (или Массив Предков) обеспечивает быстрое и эффективное решение для поиска потомков и предков узла путем создания индекса по элементам поля предков. Это делает Array of Ancestors хорошим выбором для работы с поддеревьями [Источник 3].

Работа из консоли

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

db.arOfAn.insert( { _id: "MongoDB", ancestors: [ "Educational Literature", "Programming", "Databases" , “NoSQL” ], parent: "NoSQL" } )
db.arOfAn.insert( { _id: "NoSQL", ancestors: [ "Educational Literature", "Programming", "Databases"], parent: "Databases" } )
db.arOfAn.insert( { _id: "SQL", ancestors: [ "Educational Literature", "Programming", "Databases"], parent: "Databases" } )
db.arOfAn.insert( { _id: "Databases", ancestors: [ "Educational Literature", "Programming" ], parent: "Programming" } )
db.arOfAn.insert( { _id: "Programming Languages", ancestors: [ "Educational Literature", "Programming" ], parent: "Programming" } )
db.arOfAn.insert( { _id: "English", ancestors: [ "Educational Literature", "Natural Languages" ], parent: "Natural Languages" } )
db.arOfAn.insert( { _id: "German", ancestors: [ "Educational Literature", "Natural Languages" ], parent: "Natural Languages" } )
db.arOfAn.insert( { _id: "English", ancestors: [ "Educational Literature", "Natural Languages" ], parent: "Natural Languages" } )
db.arOfAn.insert( { _id: "French", ancestors: [ "Educational Literature" ], parent: "Educational Literature" } )
db.arOfAn.insert( { _id: "Natural Languages", ancestors: [ "Educational Literature" ], parent: "Educational Literature" } )
db.arOfAn.insert( { _id: "Educational Literature", ancestors: [ ], parent: null } )

Чтобы обеспечить быстрый поиск узлами предков, можно создать индекс по полю ancestors [Источник 3].

db.arOfAn.createIndex( { ancestors: 1 } )

Реализация на JavaScript

Ввод дерева в MongoDB

Или же воспользоваться скриптом, написанным на JavaScript, который из "стандартного дерева", описанного ранее запишет в MongoDB аналогичное дерево, но с методом хранения "Хранения массива предков".

function loadTree(collection, root) //Функция загрузки дерева
//В качестве аргументов передается коллекция и дерево, хранящееся с помощью ссылок на родителей и братьев
{
	loadTreeImpl(collection, root, null); //Чтобы не передавать один "лишний" аргумент, используется вспомогательная функция
	indexing(collection); //Индексация   
}

function indexing(collection)
{
	collection.createIndex( { ancestors: 1 } ); //Индексация проводится по полю "ancestors"       
}
function loadTreeImpl(collection, root, parentId) //Функция построения деревьев
//В качестве аргументов принимает коллекцию, ID вершины и ID родителя вершины
{
	while(true)
	{
		if (parentId == null) //Если вершина является корнем, то в качестве ID родителя передается null, 
// А в качестве массива предков - пустой массив
		{
			collection.insert({_id: root.id, parent: null, ancestors: []});
		}
		else
		{
			var ancestorPath = collection.findOne({_id: parentId}).ancestors; // Массив предков у родителя сохраняется в отдельную переменную
			ancestorPath.push(parentId); //Затем в массив добавляется ID родителя
			collection.insert({_id: root.id, parent: parentId,ancestors: ancestorPath }); //Создается новая вершина
		} 
             if (root.child != null) //По рекурсии ыункция вызывается для всех детей вершины
                loadTreeImpl(collection, root.child, root.id);

             if (root.sibling == null)
                return;

             root = root.sibling; //По рекурсии выполняется для всех братьев
        }
}
Добавление новой вершины

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

function treeAddNode(collection, rootId, newId) //Функция добавляет новую вершину
//На вход передается коллекция, ID родителя и ID новой вершины 
{
    var ancestorPath = collection.findOne({_id: rootId}).ancestors; //В переменную сохраняется весь массив предков родителя
	ancestorPath.push(rootId); //В переменную дописывается ID самого родителя
	collection.insert({_id: newId, parent: rootId, ancestors: ancestorPath}); //Создание новой вершины с полем ancestors заполненным переменной ancestorPath
}
Удаление вершины

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

function treeRemoveNode(collection, id)//Функция удаления вершины
//На вход в качетсве аргументов подается коллекция и ID удаляемой вершины.
{
   collection.remove({ _id: id});
}
Перенос вершины

Перенос вершины аналогичен действиям, которые происходит при добавлении вершины.

function treeMoveNode(collection, newRootId, id) //Функция переноса вершины
//На вход в качетсве аргументов подается коллекция, ID нового родителя и ID переносимой вершины
{
	var ancestorPath = collection.findOne({_id: newRootId}).ancestors; //В переменную сохраняется весь массив предков нового родителя             
	ancestorPath.push(newRootId); //В переменную дописывается ID самого родителя
	collection.update({_id: id},{$set: {parent: newRootId}}); //В перемещаемой ноде обновляется ID родителя
	collection.update({_id: id},{$set: {ancestors: ancestorPath}}); //В перемещаемой ноде обновляется массив предков
}
Вывод детей

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

function treePrintChild(collection, root)//Функция вывод детей вершины
//В качестве аргументов передается коллекция и ID вершины.
{
        var childs = collection.find({parent: root}); //Находятся все вершины, являющиеяся детьми корня
        var childsId = []; //Создается пустой массив, который далее будет заполнен ID детей
        for (i = 0; i < childs.length(); i++) //Все ID  детей вносятся в ранее созданный массив
        {
                childsId.push(childs[i]._id);
        }
        print(childsId.join(',')); //Массив распечатывается через запятую
}
Вывод поддерева

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

function treePrint(collection, root) //Функция распечатывает поддерево
//В качестве аргмента подается коллекция и ID корня поддерева, которое надо распечатать
{	
	treePrintImpl(collection, root, 1);
}
function treePrintImpl(collection, root, indent) //Вспомогательная функция
//В качестве аргмента подается коллекция, ID корня поддерева и значение отступа
{
        indent+=1; //Отступ увеличивается на один
        print(Array(indent).join("|"), root); //Знак "|" распечатывается indent раз, после него пишется ID вершины
        var childs = collection.find({parent: root}) //Находятся все дети корня
        childs.forEach(function(node, i, childs) //Рекурсивно печатаются все потомки
        {
                treePrintImpl(collection, node._id, indent);
        })
}
Вывод пути до вершины

Благодаря способу хранения деревьев, задача вывода пути до вершины в данном случае не составляется труда. Следует лишь найти интересующую вершину и распечатать ее массив предков через знак "/".

function treeShowPath(collection, nodeId) //Функция печати пути до вершины
//В качестве аргументов передаеют коллекция и ID интересующей ноды
{
		var ancestorPath = collection.findOne({_id: nodeId}).ancestors; //Находится интересующая нода
		print(ancestorPath.join('/')); //Производится печать массива предков через знак "/"
}

Видео

Вывод

Метод "Array of Ancestors" обеспечивает быстрое и эффективное решение для поиска потомков и предков узла путем создания индекса по элементам поля "ancestors". Это делает данный метод одним из наилучших при работе с поддеревьями [Источник 3].

Деревья с хранением пути

Теория

Шаблон "Materialized Paths" хранит каждый узел дерева в документе в следующем виде: ID узла и строка идентификаторов предков (пути узла). Хотя для шаблона Materialized Paths требуются дополнительные шаги для работы со строками и регулярными выражениями, шаблон также обеспечивает большую гибкость при работе с этим путем, например, поиск узлов по частичным путям [Источник 4].

Работа из консоли

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

db.matPath.insert( { _id: "Educational Literature", path: null } )
db.matPath.insert( { _id: "Programming", path: ",Educational Literature," } )
db.matPath.insert( { _id: "Natural Languages", path: ",Educational Literature," } )
db.matPath.insert( { _id: "English", path: ",Educational Literature,Natural Languages," } )
db.matPath.insert( { _id: "German", path: ",Educational Literature,Natural Languages," } )
db.matPath.insert( { _id: "French", path: ",Educational Literature,Natural Languages," } )
db.matPath.insert( { _id: "Databases", path: ",Educational Literature,Programming," } )
db.matPath.insert( { _id: "Programming Languages", path: ",Educational Literature,Programming," } )
db.matPath.insert( { _id: "NoSQL", path: ",Educational Literature,Programming,Databases," } )
db.matPath.insert( { _id: "SQL", path: ",Educational Literature,Programming,Databases," } )db.matPath.insert( { _id: "MongoDB", path: ",Educational Literature,Programming,Databases, NoSQL," } )

Индексацию следует проводить по полю path [Источник 4].

db.matPath.createIndex( { path: 1 } )

Можно найти потомков вершины, используя регулярные выражения [Источник 4]. Например,

db.matPath.find( { path: /,Programming,/ } )

Можно найти детей вершины. Например:

db.matPath.find( { path: /,Programming$/ } )

Реализация на JavaScript

Ввод дерева в MongoDB

Или можно воспользоваться следующим скриптом.

function loadTree(collection, root) //Функция загрузки дерева
//В качестве аргументов передается коллекция и дерево, хранящееся с помощью ссылок на детей и братьев
{
    loadTreeImpl(collection, root, ""); //Чтобы не передавать слишком много аргументов используется вспомогательная функция. В качестве строки пути передается пустая строка
    indexing(collection);
}

function indexing(collection) //Индексация проводится по полю "path"
{
    collection.remove({ _id: id});     
}

function loadTreeImpl(collection, root, path) //Вспомогательная функция
//В качестве аргументов принимает коллекцию, ID вершины и ID родителя вершины
{
	collection.insert({_id: root.id, path: path}); //Добавляется корень
	if (root.child != null) //Если у вершины есть дети, то к строке пути прибавляется ID вершины и фунция рекурсивно вызывается для всех детей
	{
		var newPath = path + ", " + root.id;
        loadTreeImpl(collection, root.child, newPath);
	}

    if (root.sibling == null) //Если у вершины нет братьев, то алгоритм завершает работу
        return;
	loadTreeImpl(collection, root.sibling, path); //Функция вызывается для всех братьев вершины
}
Добавление новой вершины

Добавление новой вершины в данном случае происходит по следующему алгоритму: сначала находится родитель вершины, после этого создается переменная, являющаяся "путем" новой вершины (в эту переменную вносится путь родителя и ID родителя), затем происходит добавление в коллекцию новой вершины с указанным ID и ранее созданным путем.

function treeAddNode(collection, rootId, newId) //Функция добавляет новую вершину
//На вход передается коллекция, ID родителя и ID новой вершины 
{
	var root = collection.findOne({_id: rootId}); //Находится родитель вершины
	var newPath = root.path + ', ' + root._id; //Создается переменная, являющаяся "путем" новой вершины. В нее вносится путь корня и его ID
	collection.insert({_id: newId, path: newPath}); //Добавляется новая вершина
}
Удаление вершины

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

function treeRemoveNode(collection, id) //Функция удаления вершины
//На вход в качетсве аргументов подается коллекция и ID удаляемой вершины.
{
    collection.remove({ _id: id});
}
Перенос вершины

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

function treeMoveNode(collection, newRootId, id) //Функция переноса вершины
//На вход в качетсве аргументов подается коллекция, ID нового родителя и ID переносимой вершины
{
	treeRemoveNode(collection, id);
	treeAddNode(collection, newRootId, id);
}
Вывод детей вершины

Вывод детей вершины был реализован с помощью регулярных выражений. Знак "$" в данном случае будет значить конец строки, а знак "^" начало. Это значит, что указанный ниже алгоритм базируется на поиске вершин с конкретным путем.

function treePrintChild(collection, rootId) //Функция вывод детей вершины
//В качестве аргументов передается коллекция и ID вершины.
{
	var root = collection.findOne({_id: rootId}); //Находится интересующая вершина (корень)
	var path = '^' + root.path + ', ' + root._id + '$'; //С помощью регулярных выражений проводится поиск вершин, для которых корень является последней вершиной в пути
	var childs = collection.find({path: { $regex: path } });
	childs.forEach(function(node, i, childs) //Пороизводится печать ID детей интересующей вершины
	{
		print(node._id);
	})
}
Вывод поддерева

Функция печати поддерева аналогична функции печати детей вершины.

function treePrint(collection, rootId) //Функция распечатывает поддерево
//В качестве аргмента подается коллекция и ID корня поддерева, которое надо распечатать
{       
	var root = collection.findOne({_id: rootId}); //В данном случае требуется совершить поиск самой вершины, так как необходимо узнать ее путь
    treePrintImpl(collection, root._id, root.path);
}
function treePrintImpl(collection, rootId, path) //Вспомогательная функция
//В качестве аргмента подается коллекция, ID корня поддерева и значение отступа
{
	var indent = (path.match(new RegExp(", ", "g")) || [ ]).length + 2; //Подсчет верного значения отстпуа
	print(Array(indent).join('|') + ' ' + rootId); //Знак "|" распечатывается indent раз, после него пишется ID вершины

	var newPath = "^" + path + ', ' + rootId + "$"; //С помощью регулярных выражений проводится поиск вершин, для которых корень является последней вершиной в пути
    var childs = collection.find({path: { $regex: newPath} }); 
    childs.forEach(function(node, i, childs) //Для всех детей вершины рекурсивно вызывается функция treePrintImpl()
    {
        treePrintImpl(collection, node._id, node.path);
    })
}
Вывод пути до вершины

Вывод пути до вершины в данном случае является легкой задачей. Можно было бы просто вывести поле "path", однако я хотела, чтобы вывод пути совершался через знак "/".

function treeShowPath(collection, nodeId) //Функция печати пути до вершины
//В качестве аргументов передаеют коллекция и ID интересующей ноды
{
	var path = collection.findOne({_id: nodeId}).path; //Нахождение пути
	return path.replace(new RegExp(', ?', 'g'), '/'); //Замена знака "," на "/"
}

Видео

Вывод

Метод "Materialised Path" отличается от других тем, что он позволяет использовать регулярные выражения для поиска нужных вершин, что сокращает время поиска и является удобным инструментом при работе с поддеревьями. Данный метод немного быстрее, нежели метод "Array of Ancestors", однако сложнее в реализации [Источник 4].

Деревья с обсчетом вершин

Теория

Шаблон "Nested Sets" идентифицирует каждый узел в дереве как остановку в обходном пути дерева. Алгоритм дважды посещает каждый узел в дереве; сначала во время начального обхода, а второй во время обратного хода. Шаблон хранит каждый узел дерева как: ID вершины, идентификатор родителя узла, начальная остановка узла в левом поле и его возврат в правом поле [Источник 5]. Если посмотреть на картинку, то алгоритм обсчета вершин становится ясен.

Дерево с правилом хранения Nested Sets

Работа из консоли

В MongoDB записать дерево из примера можно используя следующие команды [Источник 5].

db.nestSets.insert( { _id: "Educational Literature", parent: null, left: 1, right: 22 } )
db.nestSets.insert( { _id: "Natural Languages", parent: "Educational Literature" , left: 2, right: 9} )
db.nestSets.insert( { _id: "English", parent: "Natural Languages", left: 3, right: 4 } )
db.nestSets.insert( { _id: "German", parent: "Natural Languages", left: 5, right: 6 } )
db.nestSets.insert( { _id: "French", parent: "Natural Languages", left: 7, right: 8 } )
db.nestSets.insert( { _id: "Programming", parent: "Educational Literature", left: 10, right: 21} )
db.nestSets.insert( { _id: "Programming Languages", parent: "Programming", left: 11, right: 12} )
db.nestSets.insert( { _id: "Databases", parent: "Programming", left: 13, right: 20} )
db.nestSets.insert( { _id: "SQL", parent: "Databases", left: 14, right: 15 } )
db.nestSets.insert( { _id: "NoSQL", parent: "Databases", left: 16, right: 19 } )
db.nestSets.insert( { _id: "MongoDB", parent: "NoSQL", left: 17, right: 18 } )

Индексацию можно провести по индексам "правый" и "левый".

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

Реализация на JavaScript

Ввод дерева в MongoDB

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

function loadTree(collection, root)//Функция загрузки дерева
//В качестве аргументов передается коллекция и дерево, хранящееся с помощью ссылок на детей и братьев
{
	loadTreeImpl(collection, root, 0, null);	//Чтобы не передавать слишком много аргументов используется вспомогательная функция
	indexing(collection);
}

function indexing(collection) //Индексация проводится по полям "left" и "right"
{
	collection.createIndex( { left: 1, right: 1 } );	
}
function loadTreeImpl(collection, root, parentLeftIndex, parentId) //Вспомогательная функция
//В качестве аргументов принимает коллекцию, ID вершины и ID родителя вершины
{
	var currentLeftIndex = parentLeftIndex + 1; //Левый индекс - всегда родительский левый индекс + 1
	var currentRightIndex = currentLeftIndex + 1; //Правый индекс, это как минимум левый индекс + 1
	
	collection.insert({_id: root.id, parent: parentId, left: currentLeftIndex, right: 0}); //Правый индекс пока не известен - оставим 0
	if (root.child != null)
		currentRightIndex = loadTreeImpl(collection, root.child, currentLeftIndex, root.id) + 1; //Если есть потомки, то загружаем их и получаем новый правый индекс

	collection.update({_id: root.id}, { $set: {right: currentRightIndex}}); //Обновляем правый индекс

	if (root.sibling == null)
		return currentRightIndex; // Если нет братьев - возращаем текущий правый индекс
	
	return loadTreeImpl(collection, root.sibling, currentRightIndex, parentId); //Загружаем следующего брата
}
Добавление новой вершины

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

function treeAddNode(collection, rootId, newId) //Функция добавляет новую вершину
//На вход передается коллекция, ID родителя и ID новой вершины 
{
	var root = collection.findOne({_id: rootId}); //Находится вершина родителя (root)
	collection.update({ left: {$gt: root.left}}, { $inc: {left: 2}}, false, true); //Чтобы добавить вершину нужно увеличить значение левого индекса на 2, у всех вершин, находящихся после root, то есть у которых левый индекс больше левого индекса root 
	collection.update({ right: {$gte: root.right}}, { $inc: {right: 2}}, false, true); //Чтобы добавить вершину нужно увеличить значение правого индекса на 2, у всех вершин, находящихся после root, то есть у которых правый индекс больше правого индекса root или равен ему
	collection.insert({_id: newId, parent: rootId, left: root.left+1, right: root.left+2});
}
Удаление вершины

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

function treeRemoveNode(collection, id) //Функция удаления вершины
//На вход в качетсве аргументов подается коллекция и ID удаляемой вершины.
{
	var node = collection.findOne({_id: id}); //Находится требуемая вершина
	collection.update({ left: {$gt: node.left}}, { $inc: {left: -2}}, false, true); //Все левые индексы, которые меньше левого индекса удаляемой вершины, уменьшаются на 2
	collection.update({ right: {$gt: node.right}}, { $inc: {right: -2}}, false, true); //Все правые индексы, которые меньше правого индекса удаляемой вершины, уменьшаются на 2
	collection.remove({ _id: id});
}
Перенос вершины

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

function treeMoveNode(collection, newRootId, id) //Функция переноса вершины
//На вход в качетсве аргументов подается коллекция, ID нового родителя и ID переносимой вершины
{
	treeRemoveNode(collection, id);
	treeAddNode(collection, newRootId, id);
}
Вывод детей

Алгоритм вывода детей в данном случае аналогичен алгоритму, описанному в пункте "Ссылка на родителей".

function treePrintChild(collection, root)//Функция вывод детей вершины
//В качестве аргументов передается коллекция и ID вершины.
{
    var childs = collection.find({parent: root}); //Запись в массив всех нод, у которых родитель - указанная вершина
	var childsId = []; 
    for (i = 0; i < childs.length(); i++) //Запись в массив всех ID ранее найденных вершин
    {
        childsId.push(childs[i]._id);
    }
    print(childsId.join(',')); //Печать массива через запятую
}
Вывод поддерева

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

function treePrint(collection, rootId) //Функция распечатывает поддерево
//В качестве аргмента подается коллекция и ID корня поддерева, которое надо распечатать
{
	var indent = 2;
	var root =  collection.findOne({_id: rootId});
	var subTree = collection.find({ left: {$gte: root.left}, right: {$lte: root.right}}).sort({left: 1}) //Так как происходит сортировка дерева по левому индексу, в переменную записываются вершины в нужном порядке
	var lastLeft = subTree[0].left-2; //Необходимо для верного отступа (чтобы для root значение indent было верным
	for ( i = 0; i< subTree.length(); i++) 
	{	
		indent+= lastLeft - subTree[i].left + 2;
		lastLeft = subTree[i].left;
		print(Array(indent).join("|"), subTree[i]._id);
	}
}
Вывод пути до вершины

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

function treeShowPath(collection, nodeId) //Функция печати пути до вершины
//В качестве аргументов передаеют коллекция и ID интересующей ноды
{
    var path =[];
    var node = collection.findOne({_id: nodeId});
	var ancestors = collection.find({left: {$lt: node.left}}, {right: {$gt: node.right}}).sort({left:1}); //Происходит поиск таких вершин, у которых левый индекс меньше левого индекса интересующей вершины и правый- больше правого
    ancestors.forEach(function(node, i, childs) //Каждый предок вносится в массив
	{
		path.push(node._id)
	})
    print(path.reverse().join('/')); //Производится печать массива
}

Видео

Вывод

Метод "Nested Sets" обеспечивает быстрое и эффективное решение для поиска поддеревьев, но является крайне неэффективным при изменении древовидной структуры. Таким образом, этот шаблон лучше всего подходит для статических деревьев, которые не меняются [Источник 5].

Вывод

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

Метод Работа с поддеревьями Поиск вершин по каким-либо параметрам Перемещение листа Печать дерева Вывод пути Особенности
Parent Reference
Медленно Медленно Быстро Средне Медленно
Child Reference
Медленно Медленно Средне Средне Средне Можно использовать при работе с графами
Array of ancestors
Быстро Медленно Средне Средне Быстро
Materialised Path
Медленно Быстро Средне Быстро Быстро Можно использовать регудярные выражения
Nested Sets
Быстро Быстро Медленно Медленно Средне Крайне неэффективен при работе с динамическими деревьями

Сноски

Источники

  1. 1,0 1,1 1,2 MongoDB Documentation [Электронный ресурс]: Model Tree Structures with Parent References: 02.05.2018 /Режим доступа: [1]
  2. 2,0 2,1 2,2 MongoDB Documentation [Электронный ресурс]: Model Tree Structures with Child References: 02.05.2018 /Режим доступа: [2]
  3. 3,0 3,1 3,2 MongoDB Documentation [Электронный ресурс]: Model Tree Structures with an Array of Ancestors: 02.05.2018 /Режим доступа: [3]
  4. 4,0 4,1 4,2 4,3 MongoDB Documentation [Электронный ресурс]: Model Tree Structures with Materialized Paths: 02.05.2018 /Режим доступа: [4]
  5. 5,0 5,1 5,2 MongoDB Documentation [Электронный ресурс]: Model Tree Structures with Nested Sets: 02.05.2018 /Режим доступа: [5]