Evgenij LegotskojSept. 25, 2016, 11: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:

Name Description
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 (
  'comment\_1\_2\_3', 
  (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;
BEGIN
SELECT array\_length(path, 1) FROM comments WHERE comments.id = element\_id INTO result;
RETURN result;
END
$$ 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, 10:02 p.m.
  • (edited)

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

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

=====

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

comment_1
comment_1_1
comment_1_1_1
comment_1_2
comment_2
comment_2_1
comment_2_2
comment_3

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

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

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

Самый простой способ, который приходит на ум, это скопировать comment_2_1 до нового комментария comment_2_3, чтобы у него был более старший id и переписать колонку path. А оригинальный comment_2_1 удалить. Только так.

Comments

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

Let me recommend you a great European Fornex hosting.

Fornex has proven itself to be a stable host over the years.

For Django projects I recommend VPS hosting

Following the link you will receive a 5% discount on shared hosting services, dedicated servers, VPS and VPN

View Hosting
V

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

  • Result:50points,
  • Rating points-4
DK

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

  • Result:20points,
  • Rating points-10
s
  • storm
  • Jan. 20, 2023, 10:30 p.m.

C++ - Тест 003. Условия и циклы

  • Result:0points,
  • Rating points-10
Popular publications in the last 90 Days
Last comments
S

Qt WinAPI - Lesson 004. QtIFW - Automation WinDeployQt and build installers with Qt Installer Framework

Hello Evgenij, regarding the online installer, I've tried many times to use web host for the created repo after repogen step. I tried using github but I found people talking it is not …
  • juvf
  • Jan. 17, 2023, 9:18 a.m.

Qt/C++ - Lesson 051. QMediaPlayer – simple audio player

PS. Почти дописал плеер на QML. Уперся в ограничения QML. Переписываю плеер на с++/qt, а графика останится в qml. Нашел то, что мне надо, а именно индикатор звука. Qt может перехватывать аудиопо…

Qt/C++ - Lesson 039. How to paint stroke in QSqlTableModel by value in the column?

В этом случае вижу только какой-нибудь костыль в стиле перебора по всем индексам в заголовке с помощью методу headerData . То есть пройтись в for цикле пока не будет совпадения н…
a
  • avt
  • Dec. 12, 2022, 8:06 p.m.

Qt/C++ - Lesson 039. How to paint stroke in QSqlTableModel by value in the column?

Спасибо за ответ. Нет, дело не в читаемости кода, в разных таблицах у меня есть столбцы с одинаковым именем, но с разными индексами. Хотел сделать решение по имени столбца для всех таблиц сразу.…
  • juvf
  • Dec. 12, 2022, 3:06 p.m.

Qt/C++ - Lesson 051. QMediaPlayer – simple audio player

Спасибо.
Now discuss on the forum

Как создать уникальное значение поля на основе существующих значений

В принципе это можно сделать так: def unique_field(self): return '{0}_{1}'.format(self.title, self.price)class Tovar(models.Model): title=models.CharField('Наименование',max_length=…
W
  • Wayne
  • Jan. 27, 2023, 12:47 p.m.

Здравствуйте помогите с qml

как сделать так, чтобы зеленая фигура при движения за пределы круга пропадала на qml
AB

Sorting the added QML elements in the ListModel

I am writing an alarm clock in QML, I am required to sort the alarms in ascending order (depending on the date or time (if there are several alarms on the same day). I've done the sorting …

QSqlRelatipnalTabelModel Qt 4.8.1 как получить id внешней связи?

Наконец-то готовы представить полноценное развитие Qt QSqlTableModel и QTableView. Посмотреть можно у нас на сайте здесь На github здесь здесь Радостная новос…
P
  • Pisych
  • Jan. 25, 2023, 10:01 p.m.

Ввод бухгалтерского документа в одной форме

вопрос снят. спасибо за ответы. сообразил, как сделать:)
About
Services
© EVILEG 2015-2022
Recommend hosting TIMEWEB