你還在用遞迴產生樹狀結構嗎?

edited 十月 2013 in 進階PHP討論
是的,在今天以前,在資料庫裡面的樹狀結構,我幾乎都是透過遞迴處理;這棵樹越大,程式的執行效率就越糟。但是書本都這麼教,我也沒想過要改變些什麼。在看 CakePHP 社群的討論中,我發現了一個新名詞:

Nested Sets pattern

而我習慣使用的方式被稱之為 adjacency list model 。

講的簡單些,如果我想要在一個資料表中表達一個樹狀結構,一般我都會設定一個 parent_id 欄位,也就是父節點;當我想要找爸爸的爸爸時,我必須透過遞迴的方式,先找到目前資料項目的爸爸,接著才有辦法找出他爸爸的爸爸,也就是說,如果要找到他祖宗十八代,那我就得對資料庫做十八次查詢,很沒效率,但是大部分的書上都這麼寫,我也就司空見慣了。

但是,如果資料表改採 Nested Sets pattern 設計,管你祖宗幾代(用詞如果粗俗了些敬請見諒 :) ),我都只需要對資料庫查詢一次,反之亦然,效率上有很大的差異,概念也沒有那麼難以理解。記得以前在上課時,老師有介紹過這個觀念(modified preorder tree traversal),可惜不夠認真 ^^||

找了一些教學(英文的):
http://www.sitepoint.com/article/hierarchical-data-database
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=1266295
http://www.dbazine.com/oracle/or-articles/tropashko4

歹命的程式設計師,就麻煩自己 K 吧 :)

原始討論: http://twpug.net/x/modules/newbb/viewtopic.php?topic_id=3034

評論

  • edited 十二月 2007
    凡事利就有弊,這個方法我也曾在書上看過,研究過一陣子。
    我的結論是:
    1. 使用這種方式,在插入跟更新資料時,必須要用交易的方式,以確保不會因為意外造成住的混亂。
    2. 對於插入或更新付出的成本太大。
    3. 這個模型比原先的鄰接模型更難令人理解,資料結構基礎不穩的人很容易寫出難以除錯的碼。

    因此我不會用這種方法來作,取而代之的是,我會用原本的方法來作,但get_path的地方稍作修改。

    更動的地方是,我會直接先把parent_id, id這兩欄從資料表讀出來,在程式語言中去過濾出我要的。

    由於parent_id, id這兩欄通常是數字,直接讀出來並不會耗費多少資源,如果表真的很大,可以考慮使用快取。
  • edited 十二月 2007
    如果看不懂英文的朋友們,可以找這本書來看:
    SQL 程式設計徹底研究
    旗標出版社出版的,在第28章講的是一般大多數人會用的鄰接串列模型,而第29章講的就是kaing所說的Nested Sets pattern,巢式集合模型。
  • edited 十二月 2007
    因為大部分的效能瓶頸會出現在 Select ,Insert與Update 頻率相對來說少很多,出錯的機率其實不大;但也的確,一旦中間的程序出了問題,要重建這個樹狀結構可能有些棘手,也許需要搭配一些備份的機制來避免問題有朝一日出現在假日的緊急電話中 :)
  • edited 十二月 2007
    其實這是一個迷思,套我學長說的一句話:如果資料庫多select幾次就會掛掉的話,這個資料庫不用也罷。

    我個人是覺得只要select的次數可以固定下來,其實就還好。
    以我的解法來看,get_path不過多select一次,而且這個select可以靠快取來達到降低實質select的效果,比起要處理複雜的insert/update還要可靠,所以我個人喜歡用這種方法。
  • edited 十二月 2007
    補充一些東西,我記得在博碩的「MySQL徹底研究」的這本書上,有提到增加一張表來輔助紀錄相關的資訊,不過也是同樣的問題,在insert/update時要同步維護那張表。

    簡單的說,如果我們要解決的問題只是上下左右追蹤這類的模式,可以不需要用到巢式集合模型,簡單的鄰接串列模型就足以應付了。

    但是如果要解決的是專屬於「樹」或是「圖」之類的問題,那我個人建議,乖乖的找別人寫好的程式來用就好,自己寫風險太大~
  • edited 十二月 2007
    後來想想,會不會兩種狀態並存比較好?保留鄰接串列模型來作為災後重建的參考,大部分查詢透過巢式集合模型進行。 :)
  • edited 十二月 2007
    剛剛才發現, CakePHP 內建的樹狀結構處理就是保留了兩種方式所需要的欄位 :)
  • edited 十二月 2007
    如果是這樣,接下來就要review看看cakephp裡面的程式碼,做一下驗證,看看有沒有問題。
  • edited 二月 2009
    分享一下好人使用遞迴產生tree的心得

    通常會用這個方法,都是為了開放「靜態」頁面

    為什麼會這麼說? 因為一個人查一棵樹,十個人查,百個人查,相信逾時的情況會很多,遜一點的DB,很快就當了

    有鑑於此,可以先用遞迴產生一棵樹,然後存成「單純的」html網頁

    再include到某個頁面,供大家使用,內容可以不定時更新

    這樣就不用重覆查詢囉 ^_^




    這個觀念用在現行的資料交換上

    現在同行的朋友,在寫程式時,幾乎很少用到insert、update等指令

    他們全都在用xml作資料交換了,每天的工作就是爬節點

    例如銀行跟其他相關單位要交換資料時,不可能直接對銀行的資料庫作存取,那是給建立資料的人用的

    他們的系統,會在某個時間裡,「自動」產生一個xml檔,再讓其他相關單位的程式設計人員,去抓它的xml

    再存到他們自己善用的環境裡

    (例如我讀某個遙遠伺服器的xml,丟到我的DB裡,再產生一個xml,存放到某個遙遠的地方,讓那一邊的人去抓)

    基本上,我們每天在存取的資料,說穿了,就是人家一天只「匯出」幾次(相當於只用一次遞迴)的檔案啦

    以上所述,是小弟好人的拙見,若是有不同的見解,一起提出來討論,讓好人我有更進一步的空間

    ^_^
  • edited 二月 2009
    許多應用遞迴的機制還是希望能夠即時取得整個樹狀結構,像是社交圈、討論區等等,不過當然快取的設計是比較普遍的 :)
  • edited 三月 2009
    請問一下,PHP 的快取要如何實現?

    謝謝 ~~
  • edited 三月 2009
    就...寫入檔案?
  • edited 十一月 2009
    又有個高手提出另外一種方法:
    http://www.akbkhome.com/blog.php/View/179/nested_trees_in_mysql__handy_stored_procedures.html

    透過 MySQL 的 stored procedure 處理,還沒實際試過,該找白老鼠了 ;)
Sign In or Register to comment.