使用物化路徑對樹進行排序？

Question

我在桌子上有一個樹形結構，它使用物化路徑讓我快速找到孩子。不過，我還需要對結果進行深度優先排序，正如人們期望的線程論壇回覆一樣。

id | parent_id | matpath |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 

所以，最後的結果實際上應該排序是這樣的：

id | parent_id | matpath |   created 
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 

如何將我的工作說出來？我可以用直接SQL（這是PostgreSQL 8.4）來做到這一點嗎？還是應該將其他信息添加到此表中？

更新：試圖更好地解釋排序標準。

想象一下，ID'1'是論壇的根帖，而以'1'開頭的'matpath'是該帖子的子項。所以ids 2到5是直接回復1並獲得'1'的matpath。但是，id 6是回覆2，而不是直接回復1，所以它獲得了1.2的matpath。這意味着，對於螺紋論壇與適合的套裝，與表中所示的所有ID，論壇的結構是這樣的，因此訂貨要求：

* id 1 (root post) 
    * id 2 
     * id 6 
      * id 8 
    * id 3 
    * id 4 
    * id 5 
     * id 9 
    * id 7 

Answer 1

我通常會創建一個額外的columnn爲此，稱爲像SortPath。它將包含您需要排序的數據，並置在一起。該列將是varchar類型，並以字符串形式進行排序。事情是這樣的：

id | parent_id | matpath |   created   |     sortpath 
---+-----------+---------+-----------------------------+-------------------------------------------------------------------------------------- 
2 |   1 | 1  | 2010-05-08 15:18:37.987544 | 2010-05-08 15:18:37.987544-2 
6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6 
8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8 
3 |   1 | 1  | 2010-05-08 17:38:14.125377 | 2010-05-08 17:38:14.125377-3 
4 |   1 | 1  | 2010-05-08 17:38:57.26743 | 2010-05-08 17:38:57.267430-4 
5 |   1 | 1  | 2010-05-08 17:43:28.211708 | 2010-05-08 17:43:28.211708-5 
9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9 
7 |   1 | 1  | 2010-05-08 18:18:11.849735 | 2010-05-08 18:18:11.849735-7 

一對夫婦的事情，這裏要注意：

• sortpath將被歸類爲一個字符串，所以重要的是所有日期有它正確排序相同的長度。例如，觀察如何在sortpath列中添加額外的零。
• 我已將每個節點的PK附加到其日期的末尾。這是因爲如果您碰巧有兩行具有完全相同的日期，則由於我們追加的附加數據，它們將始終以相同的順序返回。
• 對我來說，數據看起來與我寫的方式不對稱，因爲我們在sortpath中顯示當前節點的日期，但它不在matpath中。我寧願看到它在兩個。
• 您可能還想將節點ID 1的日期放在每個sortcolumn的開頭。這樣如果你想一次查詢多個論壇（你可能不會），那麼它仍然會正確排序。

Answer 2

我相信你的物化道路是不正確的。

你什麼邏輯，像這樣的事情

1 
1.2 
1 
1.5 

排序爲什麼是第二個1與第一個不能在一起？

如果你有

1 
1.2 
2 
2.5 

這將是微不足道的。

編輯： 我看了你的例子，你沒有存儲一行的物化路徑，但你正在存儲父行的物化路徑。 以下是該行實際路徑實際應該如何的示例。直接在matpath排序，如果你不會有超過9個分公司會工作，如果你保存它作爲：

id | parent_id | matpath |   created 
----+-----------+-----------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 

否則（> 9），你將不得不轉matpath成類似

001.002.006 
001.002.006.008 

這將支持多達999個分支機構。

請注意

• 即使有4個固定的數字的方法，如0001.0002.0006會給你一個字段是短則在接受的答案
• 你可以解析的飛行matpath的產品排序值與用戶功能
• ，你可以直接matpath存儲在這種格式（它有其它的一些特性，太）

Answer 3

我想不出一個簡單的方法在直接的SQL中執行此操作。而不是matpath，我會在這裏使用node_path。 NODE_PATH是matpath ||「」 || ID

id | parent_id | node_path |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 

現在你要根據NODE_PATH訂購樹，與已運行的排序次數定義的排序字段。

一個在PLPGSQL上split_part排序自定義遞歸函數（NODE_PATH， ''，recursion_depth）會工作。您將不得不檢查來自split_part的NULL值（並忽略這些值）。

Answer 4

我不知道我理解爲什麼接受的解決方案，使任何意義。它可以工作，但它比@ Unreason的解決方案（只填充物化路徑中的ID）更規範化，效率更低（更多磁盤空間，更多索引等）。

了OP的面孔似乎從一個事實，即，作爲@Unreason正確地指出，物化路徑（MP）的實現是不正確的乾的整個場景。 OP已將MP提供給父節點，而不是當前節點。在接受溶液中的SortPath柱通過提供物化路徑到當前節點糾正此（使用日期這個時候 - 爲什麼？ - 代替主鍵）。

僅供參考考慮以下excerpt：

物化路徑

在這種方案中，每個記錄存儲的完整路徑到根。在我們的 前面的例子中，讓我們假設KING是一個根節點。然後， 記錄用的ename =「SCOTT」經由路徑 SCOTT-> JONES-> KING連接到根部。現代數據庫允許代表 節點爲單一值的列表，但由於物化路徑已經 發明長在此之前，該公約堅持純文字 字符串一些分離級聯節點;最經常 '。'或 '/'。

Answer 5

雖然@ Unreason關於填充的答案很有效，但我想提供另一種解決方案，我相信這是我自己發明的解決方案。

您正在尋找創建字節流的函數f(x)=b_1b_2..b_i（抱歉，沒有MatJax on SO），其中b_i是一個字節。我們知道兩個字節流與第一個不同的字節相同。我們想要這樣一個功能，f(x)<f(y) iff x<y。

用0填充到相同長度，很容易就可以獲得這個目標。你需要兩個數字，看看第一個非零字節，你就是這樣。大約八年前，Steven Wittens（acko.net）向Drupal核心引入了一個不同的技巧：將字符串前面的數字位數作爲另一個數字。所以，數字97685變成字符5 9 7 6 8 5。這也適用：首先查看字節長度，如果它們不相同，那麼較大的字節肯定會較大。除此之外，你知道這兩個數字是等長的。他還使用了基數爲36的數字，0-9a-z是數字，就像每個字母的十六進制一樣。此編碼需要前36個節點有兩個字節，接下來的1260個需要兩個字節...

請注意，儘管爲了便於閱讀，填充和此狡猾可變長度編碼都不需要用於物化路徑的分隔符。

numconv支持base85編碼，但需要區分大小寫的排序規則。如果刪除小寫字母，則仍有94個ASCII字符，但仍有base68。

但是，如果你使用'二進制'字段，那麼你可以做base256：而不是一個狡猾的編碼，只需將數字寫成一系列字節，然後將整個字節流的長度作爲單個字節前綴。這將允許你編碼小於2^2048左右的樹。對於前256個節點，您使用兩個字節，對於下一個65280，您正在查看三個字節。這已經非常有效。

我提名了utf8encode(x)函數。考慮一下！您需要下降到bitsorting而不是bytesorting，但不會改變結果：找到最左邊的零位。如果另一個字符串在那裏有一個1，那麼它將是一個更長的UTF-8編碼，所以絕對要大一些。如果他們在同一個地方有第一個零，那麼我們有相同長度的比特串，這對我們來說比較好。

這很好，但分離器呢。 UTF-8算法純粹是一種創建比特流的算法，它可以處理31位數 - 所以它可以用於包含少於20億個節點的樹。您的物化路徑將是UTF-8編碼數字的比特流，其比較好：丟棄最左邊相同的UTF-8編碼數字，我們回到前一段。證明完畢因爲我們不需要分隔符或前綴字節，所以我們可以將前128個節點編碼爲一個字節，然後將下一個1920編碼爲兩個字節，最多可以編碼65535個三字節。對於四個字節，base256將獲勝。對於真正的大樹，可以將UTF-8作爲0-2147483647的編碼器轉換爲字節流。所以你可以使用它作爲base2147483647編碼：D

總結：UTF-8最適合小型樹，並且不比基於256低於20億個節點更差。除此之外，直到2^2048左右前綴長度基數256勝。除了前綴長度base2147483647勝，除此之外沒有什麼。