Storage Design of Tree Menu

  Design

Design of Relational Database

parent_id

id name parent_id
1 A NULL
2 B 1
3 C 1
4 D 2

Advantages and disadvantages:

  • Pros: Easy to understand, fast to insert and move

  • Cons: Requires multiple queries to get whole subtrees

For the query problem, cache can be applied to solve it.

left&right

id name parent_id left right
1 A NULL 1 8
2 B 1 2 5
3 C 1 6 7
4 D 2 3 4
  • Pros: Lookup up entire subtrees with a single query (fast), intrinsic ordering of children

  • Cons: Slow to insert and move, due to many modifications of existing records

To solve the problem of modification, the menu is acceptable because it reads more and writes less.

Record path

id name parent_id path
1 A NULL 1-
2 B 1 1-2-
3 C 1 1-2-
4 D 2 1-2-4-

Quick inquiry
Revision trouble

Document database

Json stored directly


{

  "name": "A",

  "children": [

    {"name": "B", "children": [{"name": "D"}]},

    {"name": "C"}

  ]

}
  • Pros: Native tree-like data structure, intrinsic ordering of children

  • Cons: Could get ugly with larger and more complex documents, concurrency is limited

Adding version to Control Version/optimistic locking Concurrency

Use parent_id


{"_id": "A"}

{"_id": "B", "parent_id": "A"}

{"_id": "C", "parent_id": "A"}

{"_id": "D", "parent_id": "B"}
  • Pros: Simple to understand, easy to find parent

  • Cons: Needs good view or index to find child documents, no intrinsic ordering of children

Using children

{"_id": "A", "children": ["B", "C"]}
{"_id": "B", "children": ["D"]}
{"_id": "C"}
{"_id": "D"}

Pros: Simple to understand, easy to find children, intrinsic ordering of children
Cons: Needs good view or index to find parent document

Index method

{

  "leaf": "A",

  "children": [

    {"leaf": "B", "children": [{"leaf": "D"}] },

    {"leaf": "C"}

  ]

}

{"_id": "A", ...}

{"_id": "B", ...}

{"_id": "C", ...}

{"_id": "D", ...}
  • Pros: Two lookups to find any node, native tree data structure, data separate from tree, intrinsic ordering

  • Cons: Traversing from one node to another requires referring back to the tree data structure (maybe this is not a bad thing — it can be cached), concurrency is limited

Storage hierarchy and path

Storing the node path along with hierarchy level int the document.

{ele: "a", path: "/a" , lvl:1} 
{ele: "b", path: "/a/b", lvl:2} 
{ele: "c", path: "/a/b/c", lvl:3}
  • Pros : Easy to fetch a subtree of a given node. Traversing up a tree is not that difficult. Getting all parent nodes of c:db..find({“path” : {“$in” : [“/a”, “/a/b”] } }).

  • Cons : If hierarchical changes are frequent, then path update is needed but still easier than other models.

doc