Last time I created some structure for linking different elements from similar groups. This project needed high performance and easy way to get elements hierarchy, but changes are not often. After consideration I decided to implement nested set tree model to do this. All is based on PHP and use Mongo database and I would like to show you some basis operations with that. It can be helful in some cases, and that model is very efficient in read operations.
First: why nested set? Because it’s very fast, comfortable and easy to get data from elements tree and build hierarchy of any of them – with parents, childs, siblings. It isn’t perfect, because adding new elements isn’t as simple as in many other structures, and moving tree branches is somewhat complicated, but in this case it was no issue, because I did not need such functionality. I will not describe whole nested set model, you can find information about that on many websites, including Wikipedia. It may be similar to binary trees, but uses more data to put data in specific place in tree.
Second thing, we must check assumptions. I decided to store many data in each element, but redundancy in Mongo is “in definition” of this database, so I could do that. Nested set model required left and right id’s, but I also stored depth level in tree and direct parent objectId for each element. Because of that, many operations are much simpler than without such data – we can use not only sides id’s, but also objectId’s and find elements by their depth in hierarchy. First, check code for adding new element:
public function addToTree($newElementId, $treeId, $parentId = null)
{
// Initial data
$data = array();
$data['element_dataId'] = new ObjectId($newElementData);
$data['element_tree'] = new ObjectId($treeId);
// Check if that three has any elements on level 0
if (!$parentId) {
$filters['element_tree'] = array('$eq' => new ObjectId($treeId));
$filters['element_depth'] = array('$eq' => (int) 0);
$collection = $this->getCollection()->find($filters);
$row = $collection->toArray();
if (isset($row[0])) {
$parentId = $row[0]->element_dataId;
}
}
// Get parent node (if exists or not)
$parentNode = $this->get($parentId, $treeId);
// No parents, create root node
if (!$parentNode) {
$data['element_depth'] = 0;
$data['element_left'] = 0;
$data['element_right'] = 1;
}
// Has parent, get parent
else
{
// Update left & right ids to make place for new element
$filters['element_right'] = array('$gte' => (int) $parentNode['element_right']);
$collection = $this->getCollection()->find($filters);
foreach ($collection as $row) {
$dataUpdate = array();
if ($row->element_left > $parentNode['element_left']) {
$dataUpdate['element_left'] = (int) ($row->element_left + 2);
}
$dataUpdate['element_right'] = (int) ($row->element_right + 2);
$this->update($row->_id, $dataUpdate);
}
// Set new element ids
$data['element_left'] = (int) ($parentNode['element_right']);
$data['element_right'] = (int) ($parentNode['element_right'] + 1);
$data['element_depth'] = (int) ($parentNode['element_depth'] + 1);
$data['element_parent'] = new ObjectId($parentId);
}
return $this->insertOne($data);
}
Where newElementId is relation to other collection… but we can also use here data or structure with data, it isn’t problem. This code allows you to use many different nested set tress in collection. I use standard MongoDB extension for PHP and create methods to get current collection, but it should be clear. Getting element by treeId and elementId should be also clear, so move to somthing more interesing – get data. We can add new elements and this “magic” code will build all three automatically – just use parent ids. But what about get parents, childs or sibling? Look here:
public function getByTree($treeId)
{
$options = array(
'sort' => array('element_depth' => 1, 'element_left' => 1)
);
$filters['element_tree'] = array('$eq' => new ObjectId($treeId));
$collection = $this->getCollection()->find($filters, $options);
return $collection;
}
public function getParent($elementId, $treeId)
{
$parentNode = $this->get($elementId, $treeId);
$filters['element_tree'] = array('$eq' => new ObjectId($treeId));
$filters['element_left'] = array('$lt' => (int) $parentNode['element_left']);
$filters['element_right'] = array('$gt' => (int) $parentNode['element_right']);
$filters['element_depth'] = array('$eq' => ((int) $parentNode['element_depth']) - 1);
$collection = $this->getCollection()->find($filters);
$row = $collection->toArray();
return isset($row[0]) ? $row[0] : null;
}
public function getParents($elementId, $treeId)
{
$parentNode = $this->get($elementId, $treeId);
$filters['element_tree'] = array('$eq' => new ObjectId($treeId));
$filters['element_left'] = array('$lt' => (int) $parentNode['element_left']);
$filters['element_right'] = array('$gt' => (int) $parentNode['element_right']);
$collection = $this->getCollection()->find($filters);
return $collection;
}
public function getChilds($elementId, $treeId)
{
$parentNode = $this->get($elementId, $treeId);
$filters['element_tree'] = array('$eq' => new ObjectId($treeId));
$filters['element_left'] = array('$gt' => (int) $parentNode['element_left']);
$filters['element_right'] = array('$lt' => (int) $parentNode['element_right']);
$collection = $this->getCollection()->find($filters);
return $collection;
}
public function getSiblings($elementId, $treeId, $allTree = false)
{
$parentNode = $this->get($elementId, $treeId);
$filters['element_tree'] = array('$eq' => new ObjectId($treeId));
$filters['element_depth'] = array('$eq' => (int) $parentNode['element_depth']);
if (!$allTree) {
$filters['element_parent'] = array('$eq' => $parentNode['element_parent']);
}
$filters['element_dataId'] = array('$ne' => new ObjectId($elementId));
$collection = $this->getCollection()->find($filters);
return $collection;
}