Hierarchy Storage Analysis
 Share
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

 
View only
 
 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
Let max depth be d, and number of records be n, and total hierarchy nodes = h
MySQL/MariaDB – Oracle – PostgreSQL – SQLite – SQL Server
2
Idea is to keep 2 tables in case of Single Valued Hierarchy : T1 - Stores Hierarchy Nodes; T2 - Stores data and references T1 via node id
3
DEMOS : (Will be updating soon)
4
Resource Link : http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
5
Assumig hashed search O(1) and hash join O(m+n)
6
7
SchemeAdjacency ListNested Set
8
Tasks to be done
9
1. Searching on fields (be it leaf or internal node) for normal WHERE querySingle : O(n+h) [using hash join for single], O(h) also possible if we find the exact rqd hierarchy.
Multiple : O(n + h + n ) - Join and then where using multiple OR then group by then count
Single : O(n+h) [using hash join for single] - O(h) also possible if we find the exact rqd hierarchy.
Multiple : O(n + h + n ) - Join and then where using multiple OR then group by then count
10
2. Searching on field according to hierarchy ancestors for 'WITHIN' query.Single : O(h+ h) if Larger Data Table is Hashed [find the required hierarchies by traversing and then search in data table - may perform slow as PHP will need to traverse ] else O(h + n) [ if larger table is not hashed ]
May look for multiple joins.
Single : O(1 + n) [ Simple check node.left is Between par.left and par.right ]
11
3. Searching on field having list of values for 'HOLDS WITHIN' query.Multiple : O(h + h) [find required hierarchies, perform ORed WHERE = on each hiearchy node and return Distinct Entries]
May look for multiple joins
Multiple : O(1 + n) [Find left and right for required hierarchy node(hashed name column in hierarchy table), then compare left of each multi-value to be in between left and right of required node, return DISTINCT]
12
4. Counting all the 'allowed values' of the tree in the table for DrillDown.Single : O(h + n.h ) [make tree, count from leaf nodes, then up the tree (add the child counts to report node counts)]

Multiple : O(h + h.h.n)[Make tree and store all successor info in list, for each hierarchy node run WHERE = all successor and then DISTINCT count]
Single : O(h.n) [count for each hierarchy node using left and right relations. Easier to compute - tree data structure required in PHP]

Multiple : O(h.n)[DISTINCT count for each hierarchy node using left and right relations. Easier to compute - tree data structure required in PHP]
13
What if change addition in nodes of hierarchyeasy to scale - more categories added {not deleted/modified}Tough to scale even while addition of more categories (nodes/allowed values) BUT NOT A PROBLEM AS WE RECREATE TABLES FROM SCRATCH
14
Key pointIn some tasks we might need to create tree data structure in PHP, which might slow down the processingHere Tree creation need is eliminated, here more computation can be shifted over to the databse, hence could be faster
15
16
Idea : store children as a list in a column
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Loading...
 
 
 
Hierarchy
Nested Set - Single
Nested List - Multiple
Status
Adjacency List - Single
Adjacency List - Multiple