mORMot Open Source

lele9

Member

Registered: 2011-10-28

Posts: 170

trees structure

hi,
there is some orm's feature or suggested way to implement a trees structure in mormot?

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,205

Website

Re: trees structure

It is in the roadmap, but not yet implemented.

Several implementation patterns are envisaged.
But nothing is determined yet.

I suspect a tree structure could be made as with plain SQL.
See http://www.codeproject.com/Articles/835 … -databases
and http://mikehillyer.com/articles/managin … -in-mysql/

mpv

Member

From: Ukraine

Registered: 2012-03-24

Posts: 1,539

Website

Re: trees structure

Currently for tree I prefer  Materialized Path + parentID pattern. In fact for every tree table I add 3 additional column: parentID, treePath, isLeaf. Tree path is list of parent ID's separanet by '/' varchar(4000)
so I have something like this:
ID  parentID   treePath  isLeaf  name
1     NULL           /1/          0         the root
2       1               /1/2/       0         child 1
3       2               /1/2/3     1         child 1 1

Such structure VERY good for store large amount of data  and very quick select of childs:
  - select * from tree where treePath like '/1/%' - return all nested child of element with ID = 1 using indexed field treePath
  - select * from tree where treePath where parentID = 1 - return all direct child of element using indexed field parentID

Selecting of parent  list is simple but not very quick
  -  select * from tree where treePath like '%/3' - no index used . In this case I try to use some database- depended feature like  "connect by" in case of Oracle

2 contra - limited level of tree depth (max is varchar (4000) = newar 15 levels ) and hard to update parentID in case element have child.

ab

Administrator

From: France

Registered: 2010-06-21

Posts: 14,205

Website

Re: trees structure

Currently for tree I prefer  Materialized Path + parentID pattern. In fact for every tree table I add 3 additional column: parentID, treePath, isLeaf. Tree path is list of parent ID's separanet by '/' varchar(4000)

With the proper index, it will indeed be very nice.

MichaelR

Member

Registered: 2014-01-24

Posts: 4

Re: trees structure

2 contra - limited level of tree depth (max is varchar (4000) = newar 15 levels ) and hard to update parentID in case element have child.

I like this style too, but your limits are not absolute.

The first / is redundant and can be eliminated. Most tree data has a variety of object types linked to it and I often use punctuation differences to indicate which type a link has. (especially useful for filtering, not every type needs its own punctuation, just groups) A further refinement is to use an encoding 0-9A-Za-z for the integer keys giving a significant reduction in size because the numbers are recorded in base 62, and hence a deeper tree. In practice if you insist on lower layered ids having small values then you can go even deeper bc you know that highly repeating values are short.

It would also be great to extend this to allow a pre-defined security filter set such that you could link it up for fast user/ role based access from a particular node down. I have done this a few times. It is similar to Active Directory in practice and it works quite well. Actually linking it to AD is another matter.

sag2007

Member

From: Moscow, RU

Registered: 2015-09-23

Posts: 10

Re: trees structure

In case there is still interest in subject.

I implement this

Materialized Path + parentID pattern

approach since 1997 and it never failed me :-)

Well, ID is usually INT or BIGINT, so maximum length of ID key in plain VARCHAR terms will be 20 symbols (for BIGINT ID).

When making treePath I make it with fixed length blocks instead of separating by anything padding zeroes in front of each ID block, so to guess list of 'all parents' chain is quite simple as well as level calculation.

ID(INT)    parentID(INT)   treePath(varchar(500))                isLeaf       name
===========================================================================================
1          NULL            0000000001                            0            the root (1)
2          3               000000000100000000030000000002        0            child (1.3.2)
3          1               00000000010000000003                  1            child (1.3)

isLeaf is usually autocalculated, but can be reset along with treePath calculation procedure.

And to find all children of a certain element I use collation instead of LIKE operator, say to select all children of node ID=1 in above table I would use:

select * from tree where treePath > '0000000001' AND treePath < '0000000001'||'Z'

Never came across tree structure deeper than 25 levels, so treePath = VARCHAR(500) in all my cases (to be on the safe side twice), besides 255 varchars are easily indexed, so VARCHAR(4000) should accomodate 400 levels with INT ID, please correct me if I am wrong.

And nice idea about 62-encoded integer keys, it will still work with all above but with something else but 'Z' for collation.

p.s. I LovE mORMot!

Last edited by sag2007 (2015-09-23 13:27:00)

edwinsn

Member

Registered: 2010-07-02

Posts: 1,215

Re: trees structure

@sag2007, thanks for sharing, very helpful.

---

Delphi XE4 Pro on Windows 7 64bit.
Lazarus trunk built with fpcupdelux on Windows with cross-compile for Linux 64bit.