樹狀結構(Tree structure)
Last updated
Was this helpful?
Last updated
Was this helpful?
避免文章不見 先暫存 stack overflow 內容
:
Columns: ID, ParentID
Easy to implement.
Cheap node moves, inserts, and deletes.
Expensive to find the level, ancestry & descendants, path
Avoid N+1 via in databases that support them
(a.k.a )
Columns: Left, Right
Cheap ancestry, descendants
Very expensive O(n/2) moves, inserts, deletes due to volatile encoding
Uses separate join table with ancestor, descendant, depth (optional)
Cheap ancestry and descendants
Writes costs O(log n) (size of the subtree) for insert, updates, deletes
Normalized encoding: good for RDBMS statistics & query planner in joins
Requires multiple rows per node
Column: lineage (e.g. /parent/child/grandchild/etc...)
Cheap descendants via prefix query (e.g. LEFT(lineage, #) = '/enumerated/path')
Writes costs O(log n) (size of the subtree) for insert, updates, deletes
Non-relational: relies on Array datatype or serialized string format
Like nested set, but with real/float/decimal so that the encoding isn't volatile (inexpensive move/insert/delete)
Has real/float/decimal representation/precision issues
A modified Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.
Cheap to iterate/paginate over
Expensive move and delete
Good Use: threaded discussion - forums / blog comments
Columns: one for each lineage level, refers to all the parents up to the root, levels down from the item's level are set to NULL
Cheap ancestors, descendants, level
Cheap insert, delete, move of the leaves
Expensive insert, delete, move of the internal nodes
Hard limit to how deep the hierarchy can be
兩種常用類型 加以整合 Adjacency Model + Nested Sets Model
(a.k.a. )
(a.k.a. , Path Enumeration)
adds ancestor encoding (materialized path) for "free", but with the added trickiness of linear algebra.