Mô hình dữ liệu phân cấp: Danh sách adjacency so với Nested Sets

Question

Tôi có một danh mục sản phẩm. Mỗi thể loại bao gồm các số khác nhau (sâu) các tiểu thể loại. Số lượng các cấp (sâu) là không xác định, nhưng tôi khá chắc chắn rằng nó sẽ không vượt quá 5,6 cấp độ. Những thay đổi dữ liệu ít khi đọc nhiều hơn.

Câu hỏi đặt ra là: loại mô hình dữ liệu phân cấp nào phù hợp hơn cho tình huống như vậy. Dự án được dựa trên khuôn khổ Django và nó đặc thù (admin i-face, mô hình xử lý ...) cần được xem xét.

Rất cám ơn!

Answer 1

Nested sets tốt hơn cho hiệu suất, nếu bạn không cần cập nhật thường xuyên hoặc sắp xếp thứ bậc.

Nếu bạn cần cập nhật cây hoặc sắp xếp thứ bậc, tốt hơn nên sử dụng mô hình dữ liệu parent-child.

Dễ dàng được xây dựng trong Oracle và SQL Server 2005+ và không dễ dàng (nhưng vẫn có thể) trong MySQL.

Answer 2

Tôi sẽ sử dụng thuật toán Chuyển đổi cây đặt hàng trước đã sửa đổi, MPTT, cho loại dữ liệu phân cấp này. Điều này cho phép hiệu suất tuyệt vời khi đi ngang qua cây và tìm con, nếu bạn không ngại một chút hình phạt khi thay đổi cấu trúc.

May mắn là Django có sẵn thư viện tuyệt vời cho việc này, django-mptt. Tôi đã sử dụng điều này trong một số dự án với rất nhiều thành công. Ngoài ra còn có django-treebeard trong đó cung cấp một số thuật toán thay thế, nhưng tôi đã không sử dụng nó (và nó không có vẻ là phổ biến như mptt anyway).

Answer 3

http://www.sqlsummit.com/AdjacencyList.htm

Answer 4

Theo những bài viết này:

http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/ http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/

"MySQL là hệ thống duy nhất của tứ đại (MySQL, Oracle, SQL Server, PostgreSQL) mà bộ lồng nhau mô hình cho thấy hiệu suất tốt và có thể được xem xét để lưu trữ dữ liệu phân cấp. "

Answer 5

Danh sách Adjacency là dễ dàng hơn nhiều để duy trì và Nested Sets nhanh hơn rất nhiều để truy vấn.

Vấn đề luôn là việc chuyển đổi Danh sách Adjacency thành Nested Sets đã thực hiện một cách lâu dài nhờ phương pháp "push stack" thực sự khó chịu được nạp bằng RBAR. Vì vậy, mọi người sẽ thực hiện một số bảo trì thực sự khó khăn trong Nested Sets hoặc không sử dụng chúng.

Bây giờ, bạn cũng có thể ăn bánh và ăn nó! Bạn có thể thực hiện chuyển đổi trên 100.000 nodesin dưới 4 giây và trên một triệu hàng trong chưa đầy một phút! Tất cả trong T-SQL, nhân tiện! Vui lòng xem các bài viết sau.

Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations