樹狀結構(Tree structure)

adjacency list model

CTE + with 語法

Nested Sets pattern

a.k.a Modified Preorder Tree Traversal

避免文章不見 先暫存 stack overflow 內容

  1. Adjacency List:

  • Columns: ID, ParentID

  • Easy to implement.

  • Cheap node moves, inserts, and deletes.

  • Expensive to find the level, ancestry & descendants, path

  • Avoid N+1 via Common Table Expressions in databases that support them

  1. Nested Set (a.k.a Modified Preorder Tree Traversal)

  • Columns: Left, Right

  • Cheap ancestry, descendants

  • Very expensive O(n/2) moves, inserts, deletes due to volatile encoding

  1. Bridge Table (a.k.a. Closure Table /w triggers)

  • 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

  1. Lineage Column (a.k.a. Materialized Path, Path Enumeration)

  • 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

  1. Nested Intervals

  • 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

  • Matrix encoding variant adds ancestor encoding (materialized path) for "free", but with the added trickiness of linear algebra.

  1. Flat Table

  • 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

  1. Multiple lineage columns

  • 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

參考資料

Previous執行計劃(Explain)NextHint

Last updated

Was this helpful?