摘要：原文鏈接歡迎作客我們的學(xué)習(xí)群本文翻譯自維基百科嵌套集合模型是一種在關(guān)系型數(shù)據(jù)庫(kù)中表示嵌套集合的特殊技術(shù)。誘因該技術(shù)的出現(xiàn)解決了標(biāo)準(zhǔn)關(guān)系代數(shù)和關(guān)系演算以及基于它們的操作不能直接在層次結(jié)構(gòu)上表示所有期望操作的問(wèn)題。這通常被稱為物料清單問(wèn)題。

原文鏈接：http://www.pilishen.com/posts...; 歡迎作客我們的php&Laravel學(xué)習(xí)群：109256050
本文翻譯自維基百科Nested set model

?nested set model(嵌套集合模型)是一種在關(guān)系型數(shù)據(jù)庫(kù)中表示nested sets（嵌套集合）?的特殊技術(shù)。[nested sets]通常指的是關(guān)系樹(shù)或者層級(jí)關(guān)系。這個(gè)術(shù)語(yǔ)是由?Joe Celko清晰的提出來(lái)的，還有人使用不同的術(shù)語(yǔ)來(lái)描述這一技術(shù)。

該技術(shù)的出現(xiàn)解決了標(biāo)準(zhǔn)關(guān)系代數(shù)和關(guān)系演算以及基于它們的SQL操作不能直接在層次結(jié)構(gòu)上表示所有期望操作的問(wèn)題。層級(jí)可以用parent-child relation (父子關(guān)系)術(shù)語(yǔ)來(lái)表示 - Celko稱之為?[adjacency list model]，但是如果可以有任意的深度，這種模型不能用來(lái)展示類似的操作比如比較兩個(gè)元素的層級(jí)或者確定一個(gè)元素是否位于另一個(gè)元素的子層級(jí)，當(dāng)一個(gè)層級(jí)結(jié)構(gòu)是固定的或者有固定的深度，這種操作必須通過(guò)每一層的?relational join#Joins_and_join-like_operators)?（關(guān)系連接）來(lái)實(shí)現(xiàn)。但是這將很低效。這通常被稱為物料清單問(wèn)題。

通過(guò)切換到圖形數(shù)據(jù)庫(kù)，可以很容易地表達(dá)層次結(jié)構(gòu)。另外在一些關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)中存在并提供了這種關(guān)系模型的解決方案：

支持專門的層級(jí)結(jié)構(gòu)數(shù)據(jù)類型，比如SQL的hierarchical query?facility(層級(jí)查詢工具)。

使用層級(jí)操作擴(kuò)展關(guān)系型語(yǔ)言，比如?nested relational algebra。

使用transitive closure擴(kuò)展關(guān)系型語(yǔ)言，比如SQL的CONNECT語(yǔ)句；這可以在parent-child relation 使用但是執(zhí)行起來(lái)比較低效。

層級(jí)結(jié)構(gòu)查詢可以在支持循環(huán)且包裹關(guān)系的操作的語(yǔ)言中實(shí)現(xiàn)。比如?PL/SQL,?T-SQL?or a?general-purpose programming language

當(dāng)這些解決方案沒(méi)被提供或不容易實(shí)現(xiàn)，就必須使用另一種方法

嵌套集模型是根據(jù)樹(shù)遍歷來(lái)對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，遍歷會(huì)訪問(wèn)每個(gè)節(jié)點(diǎn)兩次，按訪問(wèn)順序分配數(shù)字，并在兩次訪問(wèn)中都分配。這將為每個(gè)節(jié)點(diǎn)留下兩個(gè)數(shù)字，它們作為節(jié)點(diǎn)兩個(gè)屬性存儲(chǔ)。這使得查詢變得高效：通過(guò)比較這些數(shù)字來(lái)獲得層級(jí)結(jié)構(gòu)關(guān)系。但是更新數(shù)據(jù)將需要給節(jié)點(diǎn)重新分配數(shù)字，因此變得低效。盡管很復(fù)雜但是可以通過(guò)不使用整數(shù)而是用有理數(shù)來(lái)改進(jìn)更新速度。

在衣服庫(kù)存目錄中，衣服可能會(huì)更加層級(jí)機(jī)構(gòu)來(lái)分類：

[](//en.wikipedia.org/wiki/File:NestedSetModel.svg)

[](//en.wikipedia.org/wiki/File:Clothing-hierarchy-traversal-2.svg)

處于層級(jí)結(jié)構(gòu)頂端的Clothing分類包含所有的子類，因此它的左值和右值分別賦值為1和22，后面的值即這里的22是展現(xiàn)的所有節(jié)點(diǎn)總數(shù)的兩倍。下一層級(jí)包含Men"s和Women"s兩子類，各自包含必須被計(jì)算在內(nèi)的層級(jí)。每一層的節(jié)點(diǎn)都根據(jù)它們包含的子層級(jí)來(lái)給左值和右值賦值。如上表所示。

使用nested sets 將比使用一個(gè)遍歷adjacency list的儲(chǔ)存過(guò)程更快，對(duì)于天生缺乏遞歸的查詢結(jié)構(gòu)也是更快的選擇。比如MySQL.但是遞歸SQL查詢語(yǔ)句也能提供類似“迅速查詢后代”的語(yǔ)句并且在其他深度搜索查詢是更快，所以也是對(duì)于提供這一功能的數(shù)據(jù)庫(kù)的更快選擇。例如?PostgreSQL,[[5]](//en.wikipedia.org/wiki/Nested_set_model#cite_note-5)
?Oracle,[[6]](//en.wikipedia.org/wiki/Nested_set_model#cite_note-6)
?and?Microsoft SQL Server.[[7]](//en.wikipedia.org/wiki/Nested_set_model#cite_note-7)

The use case for a dynamic endless database tree hierarchy is rare. The Nested Set model is appropriate where the tree element and one or two attributes are the only data, but is a poor choice when more complex relational data exists for the elements in the tree. Given an arbitrary starting depth for a category of "Vehicles" and a child of "Cars" with a child of "Mercedes", a foreign key table relationship must be established unless the tree table is naively non-normalized. Attributes of a newly created tree item may not share all attributes with a parent, child or even a sibling. If a foreign key table is established for a table of "Plants" attributes, no integrity is given to the child attribute data of "Trees" and its child "Oak". Therefore, in each case of an item inserted into the tree, a foreign key table of the item"s attributes must be created for all but the most trivial of use cases.
If the tree isn"t expected to change often, a properly normalized hierarchy of attribute tables can be created in the initial design of a system, leading to simpler, more portable SQL statements; specifically ones that don"t require an arbitrary number of runtime, programmatically created or deleted tables for changes to the tree. For more complex systems, hierarchy can be developed through relational models rather than an implicit numeric tree structure. Depth of an item is simply another attribute rather than the basis for an entire DB architecture. As stated in?SQL Antipatterns:[[8]](//en.wikipedia.org/wiki/Nested_set_model#cite_note-8)

Nested Sets is a clever solution – maybe too clever. It also fails to support referential integrity. It’s best used when you need to query a tree more frequently than you need to modify the tree.[[9]](//en.wikipedia.org/wiki/Nested_set_model#cite_note-9)

The model doesn"t allow for multiple parent categories. For example, an "Oak" could be a child of "Tree-Type", but also "Wood-Type". An additional tagging or taxonomy has to be established to accommodate this, again leading to a design more complex than a straightforward fixed model.
Nested sets are very slow for inserts because it requires updating left and right domain values for all records in the table after the insert. This can cause a lot of database stress as many rows are rewritten and indexes rebuilt. However, if it is possible to store a forest of small trees in table instead of a single big tree, the overhead may be significantly reduced, since only one small tree must be updated.
The?nested interval model?does not suffer from this problem, but is more complex to implement, and is not as well known. It still suffers from the relational foreign-key table problem. The nested interval model stores the position of the nodes as rational numbers expressed as quotients (n/d).?[[1]](//www.sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf)

使用上面描述的nested set modal 在一些特定的樹(shù)遍歷操作上有性能限制。比如根據(jù)父節(jié)點(diǎn)查找直接子節(jié)點(diǎn)需要?jiǎng)h選子樹(shù)到一個(gè)指定的層級(jí)如下所示：

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Parent, Tree as Child
WHERE
    Child.Left BETWEEN Parent.Left AND Parent.Right
    AND NOT EXISTS (    -- No Middle Node
        SELECT *
        FROM Tree as Mid
        WHERE Mid.Left BETWEEN Parent.Left AND Parent.Right
                 AND Child.Left BETWEEN Mid.Left AND Mid.Right
            AND Mid.Node NOT IN (Parent.Node AND Child.Node)
    )
    AND Parent.Left = 1  -- Given Parent Node Left Index

或者:

SELECT DISTINCT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent 
WHERE Parent.Left < Child.Left AND Parent.Right > Child.Right  -- associate Child Nodes with ancestors
GROUP BY Child.Node, Child.Left, Child.Right
HAVING max(Parent.Left) = 1  -- Subset for those with the given Parent Node as the nearest ancestor

當(dāng)查詢不止一層深度的子節(jié)點(diǎn)的時(shí)候，查詢將更加的復(fù)雜，為了突破限制和簡(jiǎn)化遍歷樹(shù)，在模型上增加一個(gè)額外的字段來(lái)維護(hù)樹(shù)內(nèi)節(jié)點(diǎn)的深度：

在這個(gè)模型中，找到指定父節(jié)點(diǎn)的緊跟直接子節(jié)點(diǎn)可以使用下面的SQL語(yǔ)句實(shí)現(xiàn)：

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent
WHERE
    Child.Depth = Parent.Depth + 1
    AND Child.Left > Parent.Left
    AND Child.Right < Parent.Right
    AND Parent.Left = 1  -- Given Parent Node Left Index