Evgenij LegotskojSept. 25, 2016, 1:37 p.m.

Materialized Path in PostgreSQL

Relational databases store information in the form of tree structures is a problem with the additional overhead. Such extra costs can be both, increasing the number of queries and increase the amount of information which is used to organize the data structure.

Widely used approach for the organization of tree structures are:

Adjacency List

The organization of the data structure is that each object on the parent object stores the information that is in a table row has an additional field, which indicates the property ID, which is embedded in the object.
Nested Set Nested sets store information not only about the so-called left and right key, and the level of nesting. This variant of the organization of the data structure easier to read, but it is more difficult amenable to modification.
Materialized Path The idea of this data structure is that each record stores the full path to the root element of the tree.

Consideration of these data structures was caused by the need to support the introduction of the site comments to articles.

Adjacency List seemed somewhat awkward solution for the comments because there may be problems with finding the parent objects and the alignment of the tree structure, although the approach itself makes it quite quickly add or delete items.

Nested Set rather cumbersome method for the organization of comments on a small site, so if you even look at the major resources side, like Habra, there under the articles not so often on the 5000 comments. I was also confused by the fact that it will be necessary to add concealed root element, the so-called first an empty comment in the article, which will be built the whole tree. Why produce extra essence? - Although maybe I am wrong. Well, the last argument "against" was the need for conversion keys when adding new comment. In general, despite the advantages of this structure, in the framework of this site and its current state - this way storage comments will be shooting from a gun on sparrows.

But Materialized Path seemed like just what you need. Each comment contains the full path. And at the same time under the article can organize a few comments of trees. That is, any comment, which is located on the first level are automatically considered to be the root of her tree. And when you add a new comment you need to take the full path of the future parents and to add to it only the ID of the new comment. In addition, in relation to a specific database, but we are talking about PostgreSQL , storage path can be represented as an array of integers, since PostgreSQL supports arrays (By the way, the more I read about working with PostgreSQL in contrast to MySQL , the more I like it). And when selecting trees comments can sort by the data arrays that automatically allows positioning all comments in chronological order with the preservation of the tree structure, and then in Django template to generate the page in the normal cycle without recursion, because all comments will already be sorted properly database means.

Using in PostgreSQL

Now imagine that we have an abstract page, which has a few comments with the following structure:

id | name
1  | comment_1
2  |   comment_1_1
3  |     comment_1_1_1
4  |   comment_1_2
5  | comment_2
6  |     comment_2_1
7  |     comment_2_2
8  | comment_3

As a result, the comment structure will be formed with the following query:

CREATE TABLE comments (
  id serial primary key,
  path integer[] not null,
  content varchar(200) not null

In this structure, there is the auto-increment unique identifier that can be seen more and some semblance of chronological identifier, because theoretically a comment to a later time, can not be in the database before the comment with a smaller ID.

Fill the database:

INSERT INTO comments (path, content) VALUES 
  ('{1}', 'comment_1'),
  ('{1,2}', 'comment_1_1'),
  ('{1,2,3}', 'comment_1_1_1'),
  ('{1,4}', 'comment_1_2'),
  ('{5}', 'comment_2'),
  ('{5,6}', 'comment_2_1'),
  ('{5,7}', 'comment_2_2'),
  ('{8}', 'comment_3');

As a result, we obtain the following table:

id | path    | content       
1  | {1}     | comment_1    
2  | {1,2}   | comment_1_1  
3  | {1,2,3} | comment_1_1_1
4  | {1,4}   | comment_1_2
5  | {5}     | comment_2  
6  | {5,6}   | comment_2_1
7  | {5,7}   | comment_2_2
8  | {8}     | comment_3  

Search child elements

To find child elements overlap operator must use an array &&. With this operator will find items that contain in their path parent element ID. Select all the children of the element with ID = 1.

In addition, we can sort all the items in order of nesting, which is the path length.

In the below query :id = 1.

SELECT * FROM comments
WHERE path && ARRAY[:id]
ORDER BY array_length(path, 1);

At the output we get the following result:

 id |  path   |    content    
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  4 | {1,4}   | comment_1_2
  3 | {1,2,3} | comment_1_1_1
(4 rows)

Search parent elements

Getting a list of all the parent elements is to select all the elements that are part of the path of the current element. For example we get a list of parent cells comment with ID = 3 , that is comment_1_1_1 .

In the above query below :id = 3.

SELECT * FROM comments
WHERE id != :id 
AND array[id] && (
  SELECT path 
  FROM comments 
  WHERE id = :id
ORDER BY path;

As a result, we get the following output:

 id | path  |   content   
  1 | {1}   | comment_1
  2 | {1,2} | comment_1_1
(2 rows)

Add items

When you create a new entry, we need to form a path of the current path of the parent element, to which is added a new element ID. Let's add a new record, whose parent ID is equal to 4.

In the above query below :id = 4.

INSERT INTO comments (content, path)
values (
  (SELECT path FROM comments WHERE id = :id) || (select currval('comments_id_seq')::integer)

The operator || concatenates the path of the parent element with a new element ID. At the same time getting the new value of the sequence ID comments_id_seq , which is created automatically when you create the table, we need to perform a cast, because the path contains an array type Integer[], and currval returns the type biginteger .

We obtain the following table:

 id |  path   |    content    
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  5 | {5}     | comment_2
  6 | {5,6}   | comment_2_1
  7 | {5,7}   | comment_2_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(9 rows)

Deleting an item

Delete an item will do with the removal of all child elements that are also realized through the intersection of arrays.

For example to remove an element with an ID of 5. (:id = 5)

DELETE FROM comments
WHERE path && ARRAY[:id];

As a result, the table would be as follows:

 id |  path   |    content    
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(6 rows)

Move an item

Finally, do the movement of one of the elements, together with the descendants of another element. As already choose not particularly out of what, then move the element with ID = 2, the element with an ID of 8.

In general, the movement of one element to another must be replaced at the element and all its children that part of the path, which corresponds to the current parent, on a path that will correspond to the new parent.

The only difficulty lies in the fact that for the level of the element need to write a stored procedure that will help us to make the movement of a single request. Let's call it level and will transfer it to the ID of the element that will be moved.

CREATE OR REPLACE FUNCTION level(element_id integer) RETURNS integer AS
DECLARE result integer;
SELECT array_length(path, 1) FROM comments WHERE comments.id = element_id INTO result;
RETURN result;
$$ LANGUAGE plpgsql;

After the stored procedure has been registered, we will use it in the request for data transfer.

This request includes:

  • :new_parent_id - a unique identifier for the parent of the future, (it equals 8);
  • :movable_id - a unique identifier carried by the element (it equals 2).
UPDATE comments
SET path = (
  SELECT path
  FROM comments
  WHERE id = :new_parent_id
) || path[(SELECT level(:movable_id)) : array_length(path, 1)]
WHERE path && ARRAY[:movable_id];

The result is a table of the following view:

 id |  path   |    content    
  1 | {1}     | comment_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
  2 | {8,2}   | comment_1_1
  3 | {8,2,3} | comment_1_1_1
(6 rows)

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

простите а Django MPTT в этом варианте не подходит? она вроде как раз для этих целей разрабатывалась

Добрый день. Почитал описание Django MPTT, и да, подойдёт. Рассматривайте статью как базовую теорию.

  • #
  • Nov. 2, 2020, 11:02 a.m.
  • (edited)

Django MPTT использует для построения дерева алгоритм Nested Set

во вторых если надо создавать динамическое дерево прямо в хтмл документе, Django MPTT, не подойдет, а вернее подойдет только если вы знакомы с алгоритмом Nested Set, а это означает что при добавлении нового элемента в дерево надо перешитать полностью все значения записей по полям lft и rght имея в виду еще поля parent_id и tree_id


вопрос к автору статьи, скажите а Materialized Path сохраняет ордер элементов дерева. предположим что у нас есть дерево:


мы тут видим 3 родителя: comment_1, comment_2, comment_3

и мы видим что у родителя comment_2 есть 2 чаилда: comment_2_1 и comment_2_2

вот если мы поменяем местами данные чаилды как Materialized Path сохранит это????


Only authorized users can post comments.
Please, Log in or Sign up

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:10points,
  • Rating points-10

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:0points,
  • Rating points-10

C++ - Test 002. Constants

  • Result:66points,
  • Rating points-1
Last comments

Qt - Selecting data from a QSqlQuery database in a QThread stream and creating a QAbstractTableModel model based on it

Перенес в класс потока все функции для работы с БД, но все по старому когда закрываю поток основное соединение тоже закрывается

Qt - Selecting data from a QSqlQuery database in a QThread stream and creating a QAbstractTableModel model based on it

Упс, видимо нет, буду проверять. У меня просто собраны функции работы с базой данных, и подключение новое, но в функция #ifndef FUNCTIONS_H#define FUNCTIONS_H#include <QTextCodec>#i…

Qt - Selecting data from a QSqlQuery database in a QThread stream and creating a QAbstractTableModel model based on it

Вы полностью создаете новое соединение? И при создании объекта QSqlQuery или модели указываете алиас подключения?

Qt - Selecting data from a QSqlQuery database in a QThread stream and creating a QAbstractTableModel model based on it

Если в: QSQLDatabase db_thread = QSQLDatabase::addDatabase("MYSQL","db_new_name"); крашится после запуска сразу

Qt - Selecting data from a QSqlQuery database in a QThread stream and creating a QAbstractTableModel model based on it

В потоке надо создавать свое соединение с БД с другим именем.
Now discuss on the forum

Qml, tableview

через делегат https://evileg.com/ru/post/624/

Связь таблиц Qt SQL

добрый, у вас по сути два варианта: 1. делать каскадное удаление из БД по внешним ключам(но если архетиктура базы с ошибками то могут быть сбои) 2. делать контролируемо удаление из вто…

Работа с WinAPI в QT(изменение title bar)

void MainWindow::mousePressEvent(QMouseEvent *event){ if(event->pos().y() <= 45 && event->pos().y() >= 16) mpos = event->pos(); else if(event->pos().y…

QSqlTableModel - Как добавить картинки в таблицу, чтобы они отражались в диалоговом окне, но не были частью модели

Ну тогда в этом столбце указывайте пути на несколько картинок

Qt наследование и виджеты

Наверное нужно написать класс-интерфейс IBasic и потом попробовать IBasic *b = qobject_cast (tmpWidget); ? Но у меня в базовых классах A,B - формы... Получается, ч…
© EVILEG 2015-2020
Recommend hosting TIMEWEB