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:

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, 10:02 p.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 сохранит это????

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


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
  • ldim
  • March 4, 2021, 10:57 p.m.

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

  • Result:100points,
  • Rating points10
  • ldim
  • March 4, 2021, 10:39 p.m.

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

  • Result:80points,
  • Rating points4

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

  • Result:80points,
  • Rating points4
Last comments

Django - Tutorial 001. Deploying a site on Django + PostgreSQL + Gunicorn + Nginx

А почему нельзя? Где можно об этом почитать? Киньте, пожалуйста, в меня ссылкой.

Django - Tutoral 049. Optimizing Django Performance with a Real Project

Огромное спасибо вам за статью! Для меня стали открытием select_related и prefetch_related
  • t1m4
  • Feb. 24, 2021, 1:56 p.m.

Django - Tutorial 052. Redefining a User Model

В данном случае я заходил под superuser но все равно не появлялись эти поля

Django - Tutorial 001. Deploying a site on Django + PostgreSQL + Gunicorn + Nginx

Поднял сервис с помощью systemd, вот по этому мануалу: https://habr.com/ru/post/501414/
  • t1m4
  • Feb. 23, 2021, 6:11 p.m.

Django - Tutorial 052. Redefining a User Model

А как дать ему эти права?
Now discuss on the forum

как добавить списки в список, которые созданы динамически

Привет всем! Смотрите новое: https://cazino.website/luchshie-kazino/ лучшие онлайн казино россии - За регистрацию предоставляют до 225 фриспинов бесплатно + 100% бонуса до 500$ на первый д…

Не отдаётся статика на виртуальной машине

В итоге выставил 775 на все файлы проекта и всё заработало. Но я не уверен, что так правильно.
  • Pisych
  • March 3, 2021, 12:06 p.m.

Вывод данных из связанных таблиц.

Не знаю, правильно ли... Но работает <body>{% for i in CatList %} <ul> <li><h3>{{i.title}}</h3></li>{% for j in ProdList %}<ul>{…

нужна помощь с проектом qt c++

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

QScrollArea dynamically add QCheckBoxes

Всё правильно. Это просто спамер, который отправился в вечный бан.
© EVILEG 2015-2020
Recommend hosting TIMEWEB