Storing hierarchical data flat
For example, storing the tree comments.
Many probably faced with the problem of storing comments, at least thought about it. The obvious solution "in the forehead" is a link to the parental comment and, as a result, recursive calls if necessary to display a tree. Modern DBMSs support hierarchical queries, but it seems to me that this is just a transfer of the problem out of scope, maybe I'm wrong. In any case, I wrote for Google Application Engine, there is no talk about hierarchical queries at all.
I really didn’t like the perspective of recursion and a lot of small queries to the database, so I began to invent some way to get all the comments with one simple query. And this way I quickly invented. I interviewed several acquaintances, it turned out that very few people thought about this topic, so I will take the liberty to describe what I realized.
')
So, the main requirement is to get all comments at once in the right order in one request. Accordingly, I have to store 1) the display order 2) the nesting level.
The first paragraph says that the answers to the first comment should be displayed before the second comment, regardless of the time they were added.
To solve these two tasks, it is proposed to enter a certain field, sorting by which will give the desired order of comments.
Below is a small comment tree with examples of hash.
Here, the numbers like “1.1.x” are just part of the comment, not part of the hash, as the classic “materialized way” suggests.
The proposed hash stands at the beginning of each line. In this case, the hash contains, as it were, three two-digit digits: zero-level comments are numbered in the first two digits, the second in the second two, and so on. I think the calculation of this field is quite obvious from the picture.
Two limitations follow automatically:
1) the number of comments at each level is limited.
2) the number of levels is limited.
The comments kindly suggest that the obviousness of the second restriction when switching to symbolic hashes is no longer so obvious .
In fact, I decided that you can close your eyes to both of these limitations. In the case of storing comments and their number and nesting is quite possible to limit. In addition, I went to a little trick and "allowed" to add a comment to the 4th level, but in fact I am making it as a third-level comment and also display it. This is done in order not to limit the discussion of two enthusiastic commentators.
Implementation details
Developing this idea, I decided to abandon the digital field in favor of the text field. In this case, I lose a little in efficiency, but then I’m not at all limited by the length of the hash. Instead of numbers, I use the characters AZ and ax, that is, I actually use numbers with a base of 50 (a five-system system).
In a fifty-decimal system, I single out one 50 digits at once, two - already 2500, this is enough for my purposes. The nesting levels I use are 8. Both of these parameters change easily, but this can only be done once, before use.
In order to calculate the hash for each record except for its nesting level, I also keep the number of child records, so that when adding a new record, you do not have to make unnecessary requests (google data storage, in fact, does not know how to perform select count (*)).
The calculation of the hash, or rather, the update of the counter of child records must be performed within the transaction. You can add the comment itself beyond the scope of the transaction, since the hash value does not depend on anything.
By the way, just in case, I keep a link to the parent element. If I suddenly decide to change everything - I will have all the initial data to restore the picture.
findings
easy discomfort due to the presence of restrictions;
some difficulties in calculating this service field;
instant delivery of all results in one flat query without unnecessary server load.
In my opinion, it is worth bearing in mind this or a similar way of storing hierarchical data, sometimes it is quite applicable and gives good results.
For example, here you can see how it all looks and works.
PS Oh, yes, if someone prompts classic names or implementations of the solution to this problem, it will be great.
Many probably faced with the problem of storing comments, at least thought about it. The obvious solution "in the forehead" is a link to the parental comment and, as a result, recursive calls if necessary to display a tree. Modern DBMSs support hierarchical queries, but it seems to me that this is just a transfer of the problem out of scope, maybe I'm wrong. In any case, I wrote for Google Application Engine, there is no talk about hierarchical queries at all.
I really didn’t like the perspective of recursion and a lot of small queries to the database, so I began to invent some way to get all the comments with one simple query. And this way I quickly invented. I interviewed several acquaintances, it turned out that very few people thought about this topic, so I will take the liberty to describe what I realized.
')
So, the main requirement is to get all comments at once in the right order in one request. Accordingly, I have to store 1) the display order 2) the nesting level.
The first paragraph says that the answers to the first comment should be displayed before the second comment, regardless of the time they were added.
To solve these two tasks, it is proposed to enter a certain field, sorting by which will give the desired order of comments.
Below is a small comment tree with examples of hash.
000000 1
000100 1.1
000101 1.1.1 ...
000102 1.1.2 ...
000103 1.1.3 ...
000104 1.1.4 ...
000200 1.2
000300 1.3
010000 2
010100 2.1
010200 2.2 ...
020000 3
Here, the numbers like “1.1.x” are just part of the comment, not part of the hash, as the classic “materialized way” suggests.
The proposed hash stands at the beginning of each line. In this case, the hash contains, as it were, three two-digit digits: zero-level comments are numbered in the first two digits, the second in the second two, and so on. I think the calculation of this field is quite obvious from the picture.
Two limitations follow automatically:
1) the number of comments at each level is limited.
2) the number of levels is limited.
The comments kindly suggest that the obviousness of the second restriction when switching to symbolic hashes is no longer so obvious .
In fact, I decided that you can close your eyes to both of these limitations. In the case of storing comments and their number and nesting is quite possible to limit. In addition, I went to a little trick and "allowed" to add a comment to the 4th level, but in fact I am making it as a third-level comment and also display it. This is done in order not to limit the discussion of two enthusiastic commentators.
Implementation details
Developing this idea, I decided to abandon the digital field in favor of the text field. In this case, I lose a little in efficiency, but then I’m not at all limited by the length of the hash. Instead of numbers, I use the characters AZ and ax, that is, I actually use numbers with a base of 50 (a five-system system).
In a fifty-decimal system, I single out one 50 digits at once, two - already 2500, this is enough for my purposes. The nesting levels I use are 8. Both of these parameters change easily, but this can only be done once, before use.
In order to calculate the hash for each record except for its nesting level, I also keep the number of child records, so that when adding a new record, you do not have to make unnecessary requests (google data storage, in fact, does not know how to perform select count (*)).
The calculation of the hash, or rather, the update of the counter of child records must be performed within the transaction. You can add the comment itself beyond the scope of the transaction, since the hash value does not depend on anything.
By the way, just in case, I keep a link to the parent element. If I suddenly decide to change everything - I will have all the initial data to restore the picture.
findings
easy discomfort due to the presence of restrictions;
some difficulties in calculating this service field;
instant delivery of all results in one flat query without unnecessary server load.
In my opinion, it is worth bearing in mind this or a similar way of storing hierarchical data, sometimes it is quite applicable and gives good results.
For example, here you can see how it all looks and works.
PS Oh, yes, if someone prompts classic names or implementations of the solution to this problem, it will be great.
Source: https://habr.com/ru/post/125729/
All Articles