Cấu trúc dữ liệu để lưu trữ trường sắp xếp có hiệu quả cho phép sửa đổi

Question

Tôi đang sử dụng Django và PostgreSQL, nhưng tôi không hoàn toàn ràng buộc với ORM Django nếu có cách tốt hơn để làm điều này với SQL thô hoặc các hoạt động cụ thể của cơ sở dữ liệu.

Tôi có một mô hình cần đặt hàng tuần tự. Các hoạt động tra cứu thường sẽ lấy toàn bộ danh sách theo thứ tự. Các hoạt động phổ biến nhất trên dữ liệu này là để di chuyển một hàng để dưới cùng của danh sách, với một tập hợp con của các mục can thiệp bọt lên để thay thế cho mục trước như thế này:

 
(operation on A, with subset B, C, E) 

A -> B 
B -> C 
C -> E 
D -> D 
E -> A 

Notice how D does not move. 

Nói chung, các tập hợp con của các mặt hàng sẽ không nhiều hơn 50 mục, nhưng danh sách cơ sở có thể tăng lên đến hàng chục nghìn mục.

Cách rõ ràng nhất để thực hiện điều này là với trường đơn hàng số nguyên đơn giản. Điều này có vẻ tối ưu. Nó đòi hỏi sự thỏa hiệp làm cho cột sắp xếp vị trí không phải là duy nhất, trong đó tính không duy nhất chỉ được yêu cầu trong suốt thời gian hoạt động sửa đổi. Để thấy điều này, hãy tưởng tượng hoạt động tối thiểu bằng cách sử dụng A có tập con B:

oldpos = B.pos 
B.pos = A.pos 
A.pos = oldpos 

Mặc dù bạn đã lưu trữ vị trí, dòng thứ hai bạn đã vi phạm ràng buộc duy nhất. Ngoài ra, phương pháp này làm cho vấn đề atomicity - hoạt động đọc của bạn phải xảy ra trước khi ghi, trong thời gian đó các bản ghi của bạn có thể thay đổi. Tài liệu xử lý giao dịch mặc định của Django không giải quyết vấn đề này, mặc dù tôi biết có thể có trong SQL bằng cách sử dụng khóa giao dịch "REPEATABLE READ".

Tôi đang tìm các cấu trúc dữ liệu thay thế phù hợp với mô hình sử dụng này chặt chẽ hơn. Tôi đã xem xét this question để biết các ý tưởng.

Một đề nghị đó là Dewey giải pháp phong cách thập phân, mà làm cho các hoạt động chèn xảy ra bằng số giữa các giá trị hiện có, do đó chèn Một giữa kết quả B và C trong:

 
A=1 -> B=2 
B=2 -> A=2.5 
C=3 -> C=3 

này giải quyết vấn đề cột độc đáo, nhưng đưa ra vấn đề là cột phải là phao của một số thập phân được chỉ định. Hoặc tôi ước tính quá mức và lưu trữ nhiều dữ liệu hơn mức cần thiết hoặc hệ thống bị giới hạn bởi bất kỳ độ dài thập phân tùy ý nào mà tôi áp đặt. Hơn nữa, tôi không mong đợi sử dụng thậm chí trên cơ sở dữ liệu - một số phím sẽ được di chuyển nhiều hơn so với những người khác, làm cho giải pháp này đạt đến giới hạn sớm hơn. Tôi có thể giải quyết vấn đề này bằng cách định kỳ đánh số lại cơ sở dữ liệu, nhưng có vẻ như một cấu trúc dữ liệu tốt nên tránh việc này.

Cấu trúc khác mà tôi đã xem là danh sách được liên kết (và các biến thể). Điều này có lợi thế của việc sửa đổi đơn giản, nhưng tôi không chắc chắn về các thuộc tính của nó đối với SQL - thứ tự như một danh sách trong truy vấn SQL có vẻ như nó sẽ gây đau đớn, và giải nén một tập con không tuần tự của danh sách đặc tính truy xuất.

Ngoài ra, có B-Cây, nhiều cây nhị phân, v.v. Bạn đề xuất gì cho cấu trúc dữ liệu này? Có cấu trúc dữ liệu chuẩn cho giải pháp này trong SQL không? Ý tưởng ban đầu về việc đi với các số nguyên tuần tự thực sự có vấn đề mở rộng quy mô hay tôi gặp phải sự cố khi không có vấn đề gì?

Answer 1

giải pháp Ưa thích:

Một linked list sẽ là cách thông thường để đạt được điều này. Truy vấn trả về các mục theo thứ tự là trivial in Oracle, nhưng tôi không biết chắc bạn sẽ làm như thế nào trong PostreSQL.

Một lựa chọn khác sẽ được thực hiện điều này bằng cách sử dụng ltree module for postgresql.

Ít duyên dáng (và viết nặng) giải pháp: giao dịch Start. "chọn để cập nhật" trong phạm vi cho khóa cấp hàng. Di chuyển bản ghi đích đến vị trí 0, cập nhật các mục tiêu thành công trong tương lai thành +1 vị trí của chúng cao hơn vị trí ban đầu của mục tiêu (hoặc ngược lại) và sau đó cập nhật mục tiêu tới vị trí mới - một ghi bổ sung cần thiết mà không cần một ràng buộc duy nhất.Cam kết: D

đơn giản (nhưng vẫn viết nặng) giải pháp nếu bạn có thể chờ cho PostgreSQL 8.5 (Alpha có sẵn) :)

Wrap nó trong một giao dịch, chọn để cập nhật trong phạm vi, và sử dụng một ràng buộc hoãn lại (postgresql 8.5 has support for deferred unique constraints như Oracle).

Answer 2

Dường như với tôi rằng vấn đề thực sự của bạn là cần phải khóa bảng trong thời gian giao dịch. Tôi không ngay lập tức nhìn thấy một cách tốt để giải quyết vấn đề này trong một hoạt động duy nhất, do đó cần phải khóa.

Vì vậy, câu hỏi đặt ra là liệu bạn có thể làm điều này theo cách "Django" trái với việc sử dụng SQL thẳng không.Tìm kiếm "bàn khóa django" đã bật lên một số liên kết thú vị, bao gồm cả this snippet, có nhiều người khác thực hiện hành vi tương tự.

Một giải pháp kiểu danh sách liên kết SQL thẳng có thể được tìm thấy trong stack overflow post này, nó xuất hiện logic và ngắn gọn với tôi, nhưng lại là hai thao tác.

Tôi rất tò mò muốn biết điều này sẽ ra sao và giải pháp cuối cùng của bạn là gì, hãy nhớ cập nhật cho chúng tôi!

Answer 3

Bạn có thể giải quyết vấn đề đổi số bằng cách thực hiện cột thứ tự làm số nguyên luôn là số chẵn. Khi bạn đang di chuyển dữ liệu, bạn thay đổi các lĩnh vực để các giá trị kiểu mới + 1 và sau đó làm một cập nhật nhanh chóng để chuyển đổi tất cả các lĩnh vực trật tự lẻ thậm chí:

update table set sort_order = bitand(sort_order, '0xFFFFFFFE') 
where sort_order <> bitand(sort_order, '0xFFFFFFFE') 

Vì vậy bạn có thể giữ sự độc đáo của SORT_ORDER như một ràng buộc

EDIT: Được rồi, nhìn lại câu hỏi, tôi đã bắt đầu một câu trả lời mới.

Answer 4

Tại sao không làm một trường ký tự đơn giản có độ dài nào đó như tối đa 16 (hoặc 255) ban đầu.

Bắt đầu với ghi nhãn từ aaa đến zzz (có 17576 mục nhập). (Bạn cũng có thể thêm vào 0-9 và các chữ hoa và ký hiệu để tối ưu hóa.)

Khi các mục được thêm vào, chúng có thể đi đến mức tối đa bạn cho phép thêm 'thời gian kết thúc' (zzza, zzzaa, zzzaaa, zzzaab, zzzaac, zzzaad, v.v.)

Điều này rất hợp lý để lập trình và nó rất giống với hệ thống thập phân Dewey.

Có, bạn sẽ cần phải cân bằng lại đôi khi, nhưng đó phải là một vở opera đơn giản. Cách tiếp cận đơn giản nhất là hai thẻ, vượt qua 1 sẽ đặt thẻ đặt hàng mới thành '0' (hoặc bất kỳ ký tự nào sớm hơn ký tự đầu tiên) theo sau là thẻ mới có độ dài thích hợp và bước 2 sẽ xóa ' 0 từ phía trước.

Ngạc nhiên, bạn có thể làm điều tương tự với phao nổi và cân bằng lại thường xuyên, đây chỉ là một biến thể về điều đó. Một ưu điểm là hầu hết các cơ sở dữ liệu sẽ cho phép bạn thiết lập kích thước tối đa cực lớn cho trường ký tự, đủ lớn để làm cho nó rất, rất, rất không chắc bạn sẽ hết chữ số để thực hiện thứ tự, và cũng khiến nó khó xảy ra mà bạn sẽ phải sửa đổi lược đồ, trong khi không lãng phí nhiều không gian.

Answer 5

Bảng tạm thời và giao dịch nên duy trì nguyên tử và ràng buộc duy nhất trên thứ tự sắp xếp. Đang giải quyết sự cố, bạn muốn đi từ:

A 10 to B 10 
B 25  C 25 
C 26  E 26 
E 34  A 34 

Trường hợp có thể có số lượng mặt hàng ở giữa mỗi hàng. Vì vậy, trước tiên bạn đọc trong hồ sơ và tạo một danh sách [['A',10],['B',25],['C',26],['E',34]]. Thông qua một số kỳ diệu pythonic bạn chuyển các định danh xung quanh và chèn chúng vào một bảng temp:

create temporary table reorder (
    id varchar(20), -- whatever 
    sort_order number, 
    primary key (id)); 

Bây giờ cho các cập nhật:

update table XYZ 
set sort_order = (select sort_order from reorder where xyz.id = reorder.id) 
where id in (select id from reorder) 

Tôi chỉ giả pgsql có thể xử lý truy vấn đó. Nếu nó có thể, nó sẽ là nguyên tử.

Tùy chọn, tạo bảng REORDER làm bảng vĩnh viễn và giao dịch sẽ đảm bảo rằng các lần thử sắp xếp lại cùng một bản ghi hai lần sẽ được tuần tự hóa.

---

EDIT: Có một số vấn đề về giao dịch. Bạn có thể cần phải thực hiện cả hai ý tưởng của tôi. Nếu hai tiến trình muốn cập nhật mục B (ví dụ) có thể có vấn đề. Vì vậy, giả sử tất cả các giá trị đặt hàng thậm chí còn:

1. Bắt đầu giao dịch
2. Tăng tất cả các đơn đặt hàng được sử dụng bởi 1. Điều này khiến cấp hàng ghi ổ khóa trên tất cả các hàng bạn chuẩn bị cập nhật.
3. Chọn dữ liệu bạn vừa cập nhật, nếu bất kỳ trường nào sort_order thậm chí một số quy trình khác đã thêm bản ghi khớp với tiêu chí của bạn. Bạn có thể hủy bỏ giao dịch và khởi động lại hoặc bạn chỉ có thể hủy bỏ bản ghi và hoàn thành thao tác chỉ bằng các bản ghi đã được cập nhật ở bước 2. Điều "phải" phụ thuộc vào những gì bạn cần mã này để thực hiện.
4. Điền vào bảng sắp xếp lại tạm thời của bạn như trên bằng cách sử dụng đúng sort_orders.
5. Cập nhật bảng chính như trên.
6. Thả bảng tạm thời.
7. Cam kết giao dịch

Bước 2 đảm bảo rằng nếu hai danh sách chồng chéo lên nhau, chỉ có người đầu tiên sẽ được tiếp cận với hàng trong câu hỏi đến khi giao dịch hoàn thành:

update XYZ set sort_order = sort_order + 1 
where -- whatever your select criteria are 

select * from XYZ 
where -- same select criteria 
order by sort_order 

Ngoài ra, bạn có thể thêm một trường điều khiển vào bảng để có được cùng một ảnh hưởng và sau đó bạn không cần phải chơi với trường sort_order. Lợi ích của việc sử dụng trường sort_order được lập chỉ mục bởi trường BIT hoặc trường LOCK_BY_USERID khi trường thường null có xu hướng kém hiệu quả vì chỉ số 99% thời gian là vô nghĩa. Các công cụ SQL không thích các chỉ mục dành phần lớn thời gian của chúng.