文章內容引用自：
全面了解數據庫設計中分類算法
http://blog.csdn.net/hyzhx/archive/2008/03/21/2201465.aspx
在數據庫中存儲層次數據實現無限級分層
http://www.52web.com/52article/?view-250.html
http://www.thinkly.cn/index.php/archives/354
商品無限分類的算法如何優化?
http://www.javaeye.com/topic/170744
關于無限分類的設計網上討論有很多，說白了就是在數據庫中設計樹的問題，在這里僅對我所知的做些記錄與對比。
假設表結構為下圖，并且為某表的外鍵引用。要求：
1、實現無限層次。
2、能找到節點的路徑。
3、能找到所有子孫節點集合（獲取樹）。
引用："在數據庫中存儲層次數據實現無限級分層"
方案1：鄰接列表模型(The Adjacency List Model)/遞歸方法
http://www.52web.com/52article/?view-250-page-2.html
引用："在數據庫中存儲層次數據實現無限級分層"
優點：結構簡單明了，對于節點的維護并不需要額外的工作。
缺點：實現要求2、3需要進行大量的遞歸操作，每一次數據庫查詢都需要花費一點時間。
方案2：遞歸方法改進
對方案1的擴展，新增 path字段以存儲節點路徑，arrayChild字段存儲其下所有節點。
優點：實現要求1、2只需要一次查詢。
缺點：當節點發生改變時需要維護對應的字段，且 path與 arrayChild以拼串形式存儲于文本字段，容易限制節點長度，并且對于查詢效率有影響。
方案3：改進前序遍歷樹
http://www.52web.com/52article/?view-250-page-2.html
如果作為主鍵標識的節點編號存在外部引用，還需要定義一個鏈表編號 linkId來確保其主鍵標識固定，并重新定義其鏈表左右范圍。
優點：實現要求1、2只需要一次查詢，但比方案2維護起來更見方便（減少大量的拼串），而且因為左右值表示的是鏈表的范圍，所以查詢效率更高。
缺點：算法未經說明前不如方案1、2直觀。
ps:
分類算法要解決的問題
在網站建設中，分類算法的應用非常的普遍。在設計一個電子商店時，要涉及到商品分類；在設計發布系統時，要涉及到欄目或者頻道分類；在設計軟件下載這樣的程序時，要涉及到軟件的分類；如此等等。可以說，分類是一個很普遍的問題。
我常常面試一些程序員，而且我幾乎毫無例外地要問他們一些關于分類算法的問題。下面的舉幾個我常常詢問的問題。你認為你可以很輕松地回答么？
1、分類算法常常表現為樹的表示和遍歷問題。那么，請問：如果用數據庫中的一個Table來表達樹型分類，應該有幾個字段？
2、如何快速地從這個Table恢復出一棵樹？
3、如何判斷某個分類是否是另一個分類的子類？
4、如何查找某個分類的所有產品？
5、如何生成分類所在的路徑。
6、如何新增分類？
在不限制分類的級數和每級分類的個數時，這些問題并不是可以輕松回答的。本文試圖解決這些問題。
posted on 2010-05-02 10:48
黃小二 閱讀(660)
評論(0) 編輯 收藏 所屬分類:
[DB]