##关系型数据库设计 ###parent_id |id |name | parent_id| |---|-------|-----------| |1 |A |NULL | |2 |B |1 | |3 |C |1 | |4 |D |2 |

优缺点：

• Pros: Easy to understand, fast to insert and move
• Cons: Requires multiple queries to get whole subtrees

针对查询问题，可以应用缓存来解决

###left&right

• 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

针对修改问题，由于菜单读多写少，可以接受

###记录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- |

查询快 修改麻烦

##文档型数据库 ###直接存json

{  "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

增加version，进行版本/乐观锁并发控制

###使用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

###使用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

###索引法

{  "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

##存储层级以及路径 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