2008-08-21 23 views
31

Tôi có một bộ sưu tập các đối tượng trong cơ sở dữ liệu. Hình ảnh trong thư viện ảnh, sản phẩm trong danh mục, chương trong sách, v.v. Mỗi đối tượng được thể hiện dưới dạng hàng. Tôi muốn có thể tự ý đặt những hình ảnh này, lưu trữ thứ tự đó trong cơ sở dữ liệu để khi tôi hiển thị các đối tượng, chúng sẽ theo đúng thứ tự.Trình bày thứ tự trong một cơ sở dữ liệu quan hệ

Ví dụ: giả sử tôi đang viết một cuốn sách và mỗi chương là một đối tượng. Tôi viết cuốn sách của tôi, và đặt các chương theo thứ tự sau:

Giới thiệu, tiếp cận, Mẫu vs Chức năng, lỗi, nhất quán, Kết luận, Index

Nó đi vào trình biên tập, và đi kèm trở lại với trình tự gợi ý sau:

Giới thiệu, Form, Chức năng, tiếp cận, nhất quán, lỗi, Kết luận, Index

Làm thế nào tôi có thể lưu trữ thứ tự này trong cơ sở dữ liệu một cách mạnh mẽ, hiệu quả?

Tôi đã có ý tưởng sau đây, nhưng tôi không vui mừng với ai trong số họ:

  1. Array. Mỗi hàng có một ID đặt hàng, khi thứ tự được thay đổi (thông qua việc loại bỏ theo sau là chèn), các ID đơn đặt hàng được cập nhật. Điều này làm cho việc truy xuất trở nên dễ dàng, vì nó chỉ là ORDER BY, nhưng có vẻ dễ bị phá vỡ.

    // REMOVAL
    UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
    UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
    // INSERTION
    UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
    UPDATE ... SET orderID=insertionID WHERE ID=addedID

  2. danh sách liên kết. Mỗi hàng có một cột cho id của hàng tiếp theo trong thứ tự. Traversal có vẻ tốn kém ở đây, mặc dù có thể bằng cách nào đó để sử dụng ORDER BY mà tôi không nghĩ đến.

  3. Mảng cách nhau. Đặt orderID (như được sử dụng trong # 1) là lớn, vì vậy đối tượng đầu tiên là 100, thứ hai là 200, vv Sau đó, khi chèn xảy ra, bạn chỉ cần đặt nó tại (objectBefore + objectAfter)/2. Tất nhiên, điều này sẽ cần phải được cân bằng đôi khi, vì vậy bạn không có những thứ quá gần nhau (ngay cả với phao, bạn cuối cùng sẽ chạy vào làm tròn lỗi).

Không có thứ nào trong số này đặc biệt thanh lịch với tôi. Có ai có cách nào tốt hơn để làm điều đó không?

Trả lời

1

Vì tôi chủ yếu chạy vào điều này với Django, tôi đã tìm thấy this solution để có thể hoạt động tốt nhất. Dường như không có bất kỳ "đúng cách" nào để làm điều này trong một cơ sở dữ liệu quan hệ.

3

Kết hợp actions_as_list trong Rails xử lý về cơ bản cách bạn đã nêu trong # 1. Nó tìm kiếm một cột INTEGER được gọi là vị trí (trong đó bạn có thể ghi đè lên tên của khóa học) và sử dụng nó để làm một ORDER BY. Khi bạn muốn sắp xếp lại thứ bạn cập nhật vị trí. Nó đã phục vụ tôi tốt mỗi khi tôi đã sử dụng nó.

Như một lưu ý phụ, bạn có thể loại bỏ sự cần thiết phải luôn định vị lại trên INSERTS/DELETES bằng cách sử dụng đánh số thưa thớt - giống như cơ bản trong ngày ... bạn có thể số vị trí của bạn 10, 20, 30, v.v.và nếu bạn cần phải chèn một cái gì đó ở giữa 10 và 20 bạn chỉ cần chèn nó với một vị trí của 15. Tương tự như vậy khi xóa bạn chỉ có thể xóa các hàng và để lại khoảng cách. Bạn chỉ cần đánh số lại khi bạn thực sự thay đổi thứ tự hoặc nếu bạn cố gắng chèn và không có khoảng trống thích hợp để chèn vào.

Tất nhiên tùy thuộc vào tình huống cụ thể của bạn (ví dụ: nếu bạn có các hàng khác đã được tải vào bộ nhớ hay không) có thể hoặc không có ý nghĩa khi sử dụng phương pháp khoảng cách.

+1

+1 để đề cập đến đánh số thưa thớt. Tôi đã sử dụng đá quý [xếp hạng-model] (https://github.com/mixonic/ranked-model) cho điều này trong quá khứ. –

2

Tôi sẽ thực hiện một số liên tiếp, với trình kích hoạt trên bảng "ưu tiên phòng" nếu mức độ ưu tiên đã tồn tại.

+4

Điều này yêu cầu cấu trúc lại O (n) trên mỗi lần chèn! – cdleary

2

Nếu các đối tượng không bị khóa nặng bởi các bảng khác và danh sách ngắn, việc xóa mọi thứ trong miền và chỉ cần chèn lại danh sách chính xác là dễ nhất. Nhưng điều đó không thực tế nếu các danh sách lớn và bạn có rất nhiều hạn chế để làm chậm quá trình xóa. Tôi nghĩ phương pháp đầu tiên của bạn thực sự là sạch nhất. Nếu bạn chạy nó trong một giao dịch, bạn có thể chắc chắn không có gì lạ xảy ra trong khi bạn đang ở giữa của bản cập nhật để vít lên thứ tự.

1

Tôi đã làm điều này trong dự án cuối cùng của mình, nhưng đó là một bảng chỉ thỉnh thoảng cần phải được đặt hàng cụ thể và không được truy cập quá thường xuyên. Tôi nghĩ rằng các mảng khoảng cách sẽ là lựa chọn tốt nhất, bởi vì nó sắp xếp lại sẽ rẻ nhất trong trường hợp trung bình, chỉ liên quan đến một thay đổi cho một giá trị và một truy vấn trên hai).

Ngoài ra, tôi sẽ tưởng tượng ORDER BY sẽ được tối ưu hóa khá nhiều bởi các nhà cung cấp cơ sở dữ liệu, do đó tận dụng chức năng đó sẽ thuận lợi cho hiệu suất thay vì thực hiện danh sách liên kết.

5

Một giải pháp thay thế khác sẽ là (nếu RDBMS của bạn hỗ trợ nó) để sử dụng các cột của mảng kiểu. Trong khi điều này phá vỡ các quy tắc bình thường hóa, nó có thể hữu ích trong các tình huống như thế này. Một cơ sở dữ liệu mà tôi biết về điều đó có mảng là PostgreSQL.

+0

Tôi không hiểu giải pháp này rõ ràng là câu trả lời tốt hơn. Bạn có thể xây dựng một chút về cách sử dụng mảng cho mỗi hàng không? Cảm ơn – Pierre

3

Chỉ cần suy nghĩ xem xét tùy chọn # 1 vs # 3: không phải tùy chọn mảng cách nhau (# 3) chỉ trì hoãn sự cố của mảng bình thường (# 1)? Bất kỳ thuật toán nào bạn chọn, hoặc là nó bị hỏng, và bạn sẽ gặp phải vấn đề với # 3 sau, hoặc nó hoạt động, và sau đó # 1 cũng hoạt động tốt.

2

Sử dụng một số dấu chấm động để đại diện cho vị trí của từng hạng mục:

khoản 1 -> 0.0

khoản 2 -> 1,0

Khoản 3 -> 2,0

Khoản 4 -> 3.0

Bạn có thể đặt bất kỳ mục nào giữa hai mục khác bằng cách chia đôi đơn giản:

khoản 1 -> 0.0

Khoản 4 -> 0,5

khoản 2 -> 1,0

Khoản 3 -> 2,0

(Đã chuyển mục 4 giữa các mục 1 và 2).

Quá trình chia đôi có thể tiếp tục gần như vô thời hạn do cách các số dấu phẩy động được mã hóa trong hệ thống máy tính.

Mục 4 -> 0.5

khoản 1 -> 0,75

khoản 2 -> 1,0

Khoản 3 -> 2,0

(Di chuyển mục từ 1 tới vị trí ngay sau khi mục 4)

+5

Điều này/sẽ không/tiếp tục vô thời hạn. Đối với các số dấu chấm động (gấp đôi) sẽ hội tụ sau 53 vòng, trong trường hợp bệnh lý. Ngay cả khi DBMS của bạn sử dụng số thập phân chính xác tùy ý, bạn sẽ có rất nhiều cấu trúc dữ liệu sưng lên. – cdleary

1

tôi đã vấn đề này là tốt. Tôi đã chịu áp lực nặng nề (không phải tất cả chúng ta) và tôi đã đi với tùy chọn # 1 và chỉ những hàng được cập nhật đã thay đổi.

Nếu bạn hoán đổi mục 1 với mục 10, chỉ cần thực hiện hai cập nhật để cập nhật số thứ tự của mục 1 và mục 10. Tôi biết nó đơn giản về mặt thuật toán, và đó là trường hợp xấu nhất O (n). là khi bạn có tổng hoán vị của danh sách. Bao lâu thì điều đó sẽ xảy ra? Đó là để bạn trả lời.

0

Tôi đã gặp vấn đề tương tự và có thể đã dành ít nhất một tuần liên quan đến bản thân mình về mô hình dữ liệu thích hợp, nhưng tôi nghĩ cuối cùng tôi cũng đã có nó. Sử dụng kiểu dữ liệu mảng trong PostgreSQL, bạn có thể lưu trữ khóa chính của mỗi mục được sắp xếp và cập nhật mảng đó cho phù hợp bằng cách sử dụng chèn hoặc xóa khi đặt hàng của bạn thay đổi. Việc tham chiếu một hàng sẽ cho phép bạn ánh xạ tất cả các đối tượng của bạn dựa trên thứ tự trong cột mảng.

Nó vẫn là một chút lộn xộn của một giải pháp nhưng nó sẽ hoạt động tốt hơn tùy chọn # 1, vì tùy chọn 1 yêu cầu cập nhật số thứ tự của tất cả các hàng khác khi đặt hàng thay đổi.