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:

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, 11:02 a.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
Card image cap
Pulsum Via

Project for travelers from EVILEG.

Go
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
Share on social networks
Donate

The EVILEG project has switched to a non-commercial basis and will develop solely on the enthusiasm of the site creator, the enthusiasm of users, donations and the hosting referral system

Thank you for your support

Available ways to support the project

PayPal

PatreonYandex.MoneyMore

C++ - Test 001. The first program and data types

  • Result:80points,
  • Rating points4

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
GR

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

  • Result:90points,
  • Rating points8
Last comments

Qt/C++ - Lesson 061. Adding images to the application using the Drag And Drop method from the file manager

Доброго времени суток. А если нужно и изображение и текст? Что-то потерялся немного.... // Вместо отрисовки иконки и текста будем отрисовывать только одно изображение // с н…
AS

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

error insert into TableExample " Количество параметров не совпадает" Я путь свой прописывала и даже бд удаляла, чтобы заново сделать, не работает. (всё остальное как у вас... Вроде ка…
i

Qt/C++ - Lesson 042. PopUp notification in the Gnome style using Qt

cialis powder comprare cialis online
LD

GameDev on Qt - Tutorial 1. Track mouse movement in QGraphicsScene

Вполне возможно, что ты не закинул graphicsView в дизайнере в виджет
LD

GameDev on Qt - Tutorial 1. Track mouse movement in QGraphicsScene

Кому интересно, поворот в slotTarget можно в одну строку организовать this->setRotation(90 + rotation() + qRadiansToDegrees(qAtan2(mapFromScene(point).y(), mapFromScene(point).x())));
Now discuss on the forum
M

Sorting the added QML elements in the ListModel

legal online pharmacy
  • Nomad
  • July 30, 2022, 5:42 a.m.

Как работать с HTMX?

Приветствую колеги. На днях наткнулся на вот это : https://htmx.org/ На офф сайте написанно вот такая фраза: htmx gives you access to AJAX, CSS Transitions, We…
h
  • harisr
  • July 25, 2022, 2:56 a.m.

QT - Native App Integration

Привет, у нас уже есть собственное приложение для Android. Можем ли мы интегрировать пользовательское представление QT в приложение со всем приложением QT внутри представления. Если да, ука…

Правильный запуск сервера на vps - Django

О я как то себе дома локальный сервер создавал. Вам же нужно просто сделать ручками конфигурацию системы. Настроить Nginx ну либо Apache (тут кому что нравится). Соответственно БД и всё остально…
o

Распознание объектов

Я к тому, что, возможно, софт уже есть.
About
Services
© EVILEG 2015-2022
Recommend hosting TIMEWEB