1. Trang chủ
  2. Câu hỏi và trả lời
  3. Phân loại cây với đường dẫn vật chất?

Phân loại cây với đường dẫn vật chất?

2010-05-09 33 views
14

Tôi có một cấu trúc cây trong một bảng và nó sử dụng đường dẫn vật chất để cho phép tôi tìm thấy trẻ em một cách nhanh chóng. Tuy nhiên, tôi cũng cần phải sắp xếp các kết quả theo chiều sâu đầu tiên, như một trong những mong đợi với các trả lời của diễn đàn luồng.Phân loại cây với đường dẫn vật chất?

id | parent_id | matpath |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695

Vì vậy, kết quả cuối cùng thực sự nên được sắp xếp như thế này:

id | parent_id | matpath |   created 
----+-----------+---------+---------------------------- 
    2 |   1 | 1  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1  | 2010-05-08 18:18:11.849735

Làm thế nào tôi có thể làm việc mà ra? Tôi có thể làm điều đó trong SQL thẳng (đây là PostgreSQL 8.4) hoặc nên thêm thông tin bổ sung vào bảng này?

Cập nhật: cố gắng giải thích tiêu chí sắp xếp tốt hơn.

Hãy tưởng tượng id '1' là bài đăng gốc vào diễn đàn và mọi thứ có 'matpath' bắt đầu bằng '1' là con của bài đăng đó. Vì vậy, các id từ 2 đến 5 là các câu trả lời trực tiếp cho 1 và nhận được các đường dẫn của '1'. Tuy nhiên, id 6 là một câu trả lời 2, không trực tiếp đến 1, vì vậy nó nhận được một matpath 1.2. Điều này có nghĩa rằng đối với một diễn đàn ren với tổ hợp, với tất cả id thể hiện trong các bảng, cấu trúc của diễn đàn sẽ trông như thế này, vì vậy yêu cầu đặt hàng:

* id 1 (root post) 
    * id 2 
     * id 6 
      * id 8 
    * id 3 
    * id 4 
    * id 5 
     * id 9 
    * id 7

Nguồn

2010-05-09 Ovid

Trả lời

8

tôi thường tạo ra một columnn thêm cho điều này, được gọi là một cái gì đó như SortPath. Nó sẽ chứa dữ liệu mà bạn cần sắp xếp theo, nối với nhau. Cột đó sẽ thuộc loại varchar và được sắp xếp dưới dạng chuỗi. Một cái gì đó như thế này:

id | parent_id | matpath |   created   |     sortpath 
---+-----------+---------+-----------------------------+-------------------------------------------------------------------------------------- 
2 |   1 | 1  | 2010-05-08 15:18:37.987544 | 2010-05-08 15:18:37.987544-2 
6 |   2 | 1.2  | 2010-05-08 17:50:43.288759 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6 
8 |   6 | 1.2.6 | 2010-05-09 14:01:17.632695 | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8 
3 |   1 | 1  | 2010-05-08 17:38:14.125377 | 2010-05-08 17:38:14.125377-3 
4 |   1 | 1  | 2010-05-08 17:38:57.26743 | 2010-05-08 17:38:57.267430-4 
5 |   1 | 1  | 2010-05-08 17:43:28.211708 | 2010-05-08 17:43:28.211708-5 
9 |   5 | 1.5  | 2010-05-09 14:02:43.818646 | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9 
7 |   1 | 1  | 2010-05-08 18:18:11.849735 | 2010-05-08 18:18:11.849735-7

Một vài điều cần lưu ý ở đây:

  • sortpath sẽ được sắp xếp như là một chuỗi, vì vậy điều quan trọng là tất cả các ngày có chiều dài tương tự cho nó một cách chính xác loại. Ví dụ: quan sát cách 2010-05-08 17:38:57.26743 có thêm 0 số không trong cột sortpath.
  • Tôi đã nối thêm PK của mỗi nút vào cuối ngày của nó. Điều này là để nếu bạn tình cờ có hai hàng có cùng ngày chính xác, chúng sẽ luôn được trả lại theo cùng một thứ tự do dữ liệu bổ sung mà chúng tôi đang thêm vào.
  • Với tôi, dữ liệu trông không đối xứng theo cách tôi đã viết, bởi vì chúng tôi đang hiển thị ngày của nút hiện tại theo số sortpath, nhưng không nằm trong số matpath. Tôi muốn nhìn thấy nó trong cả hai.
  • Bạn cũng có thể muốn đặt ngày ID nút 1 ở đầu mỗi sortcolumn. Điều này là để nếu bạn muốn truy vấn nhiều hơn một diễn đàn tại một thời điểm (có thể bạn sẽ không), thì nó sẽ vẫn sắp xếp chính xác.

Nguồn

2010-05-09 13:19:34 RedFilter

+0

Tôi đã mở rộng bài đăng gốc để giải thích yêu cầu sắp xếp. Xin lỗi vì sự nhầm lẫn. – Ovid

+0

@Ovid: Ok, có ý nghĩa. Tôi sẽ giải thích làm thế nào để làm điều đó. – RedFilter

+0

Chỉ cần thêm điều đó. Làm việc như một say mê. Cảm ơn bạn. – Ovid

13

Tôi tin rằng con đường vật chất hóa của bạn là không đúng.

Logic gì bạn có thể sắp xếp mọi thứ như thế này

1 
1.2 
1 
1.5

Tại sao là lần thứ hai 1 không cùng với người đầu tiên?

Nếu bạn có

1 
1.2 
2 
2.5

Đây sẽ là tầm thường.

EDIT: Tôi đã xem ví dụ của bạn và bạn không lưu trữ đường dẫn vật chất của một hàng, nhưng bạn đang lưu trữ đường dẫn vật chất của hàng chính. Đây là cách đường dẫn vật chất của hàng thực sự trông như thế nào. Sắp xếp trực tiếp trên matpath sẽ làm việc nếu bạn không có nhiều hơn 9 chi nhánh nếu bạn lưu trữ nó như:

id | parent_id | matpath |   created 
----+-----------+-----------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735

khác (> 9), bạn sẽ phải xoay matpath vào một cái gì đó giống như

001.002.006 
001.002.006.008

có thể hỗ trợ tới 999 chi nhánh.

Xin lưu ý

  • ngay cả những cách tiếp cận với 4 chữ số cố định, chẳng hạn như 0001.0002.0006 sẽ cung cấp cho bạn một lĩnh vực đó là ngắn sau đó trong câu trả lời chấp nhận
  • bạn có thể phân tích matpath một sản phẩm giá trị sắp xếp một cách nhanh chóng với một chức năng sử dụng
  • bạn trực tiếp có thể lưu trữ matpath ở định dạng này (nó có một số đặc tính tuyệt vời khác, quá)

Nguồn

2010-05-09 13:21:32 Unreason

+0

Tôi khá chắc chắn đường dẫn vật chất là chính xác. Tôi đã chỉnh sửa bài đăng của mình để giải thích đầy đủ hơn về yêu cầu sắp xếp. – Ovid

3

tôi không thể nghĩ ra một cách đơn giản để làm điều này trong SQL thẳng. Thay vì matpath, tôi sẽ sử dụng node_path ở đây. node_path là matpath || '' || id

id | parent_id | node_path |   created   
----+-----------+---------+---------------------------- 
    2 |   1 | 1.2  | 2010-05-08 15:18:37.987544 
    3 |   1 | 1.3  | 2010-05-08 17:38:14.125377 
    4 |   1 | 1.4  | 2010-05-08 17:38:57.26743 
    5 |   1 | 1.5  | 2010-05-08 17:43:28.211708 
    7 |   1 | 1.7  | 2010-05-08 18:18:11.849735 
    6 |   2 | 1.2.6  | 2010-05-08 17:50:43.288759 
    9 |   5 | 1.5.9  | 2010-05-09 14:02:43.818646 
    8 |   6 | 1.2.6.8 | 2010-05-09 14:01:17.632695

Bây giờ bạn muốn đặt hàng cây dựa trên node_path, với lĩnh vực phân loại xác định bởi số lần bạn đã chạy các loại.

Chức năng đệ quy tùy chỉnh trong phân loại plpgsql trên split_part (node_path, '.', Recursion_depth) sẽ hoạt động. Bạn sẽ phải kiểm tra các giá trị NULL từ split_part (và bỏ qua chúng).

Nguồn

2010-05-09 14:46:19 Devdas

6

Tôi không chắc mình hiểu tại sao giải pháp được chấp nhận có ý nghĩa gì cả. Nó hoạt động, nhưng nó thậm chí còn ít chuẩn hóa và kém hiệu quả (nhiều không gian đĩa hơn, nhiều chỉ mục hơn, vv) so với giải pháp của @ Unreason (chỉ cần pad ID trong đường dẫn vật chất hóa).

Toàn bộ kịch bản mà các khuôn mặt OP dường như xuất phát từ thực tế rằng, như @Unreason chỉ ra chính xác, việc thực hiện đường dẫn vật chất (MP) là không chính xác. OP đã cung cấp MP cho phụ huynh, không phải cho nút hiện tại. Trong giải pháp được chấp nhận, cột SortPath sửa lỗi này bằng cách cung cấp đường dẫn vật chất cho nút hiện tại (lần này sử dụng ngày - tại sao? - thay vì khóa chính).

Để tham khảo xem xét sau excerpt:

Materialized Đường dẫn

Trong phương pháp này mỗi bản ghi lưu trữ toàn bộ đường dẫn đến thư mục gốc. Trong ví dụ trước của chúng tôi, giả sử rằng KING là nút gốc. Sau đó, bản ghi với ename = 'SCOTT' được kết nối với thư mục gốc qua đường dẫn SCOTT-> JONES-> KING. Cơ sở dữ liệu hiện đại cho phép đại diện cho một danh sách các nút dưới dạng một giá trị duy nhất, nhưng vì đường dẫn vật chất đã là được phát minh từ lâu trước đó, quy ước được gắn với ký tự đơn giản chuỗi nối với một số dấu tách; thường xuyên nhất '.' hoặc '/'.

Nguồn

2012-07-14 19:17:01 DrFriedParts

6

Trong khi câu trả lời của @ Unreason về công việc đệm, tôi muốn cung cấp một giải pháp khác mà tôi tin là phát minh của riêng tôi về vấn đề này.

Bạn đang tìm kiếm hàm tạo ra một dòng tối ưu, f(x)=b_1b_2..b_i (xin lỗi không có MatJax trên SO) trong đó b_i là một byte. Chúng ta biết hai bytestream so sánh giống như byte khác nhau đầu tiên. Chúng tôi muốn có một chức năng như vậy f(x)<f(y) iff x<y.

Đệm với cùng độ dài bằng 0 chắc chắn có được mục tiêu này, dễ dàng. Bạn lấy hai số, nhìn vào byte nonzero đầu tiên và ở đó bạn đang có.

Steven Wittens (acko.net) giới thiệu một mẹo khác với lõi Drupal cách đây tám năm: đặt số chữ số ở phía trước của chuỗi như một chữ số khác. Vì vậy, số 97685 trở thành các ký tự 5 9 7 6 8 5. Điều này cũng hoạt động: nhìn vào byte dài đầu tiên, nếu chúng không giống nhau thì lớn hơn chắc chắn sẽ lớn hơn. Ngoài ra, bạn biết hai con số có chiều dài bằng nhau. Ông cũng sử dụng số 36 cơ bản với 0-9a-z là các chữ số, giống như hex chỉ cho mỗi chữ cái. Mã hóa này cần hai byte cho 36 nút đầu tiên, ba cho 1260 tiếp theo ...

Lưu ý rằng không phải đệm cũng không mã hóa độ dài biến này cần phân tách cho đường dẫn vật chất mặc dù chúng thường được bao gồm.

numconv hỗ trợ mã hóa base85 nhưng yêu cầu phải đối chiếu phân biệt chữ hoa chữ thường. Có 94 ký tự ASCII nếu bạn loại bỏ chữ thường thì bạn vẫn có base68. Nhưng nếu bạn sử dụng trường 'nhị phân' thì bạn có thể làm base256: thay vì mã hóa xảo quyệt, hãy viết số dưới dạng một chuỗi byte và sau đó thêm tiền tố toàn bộ chiều dài của byte gần như là một byte đơn. Điều này sẽ cho phép bạn mã hóa bất kỳ cây nào nhỏ hơn 2^2048 hoặc hơn. Đối với 256 nút đầu tiên, bạn đang sử dụng hai byte, cho 65280 tiếp theo bạn đang xem ba byte. Điều này đã khá hiệu quả.

Tôi chỉ định hàm utf8encode(x). Xem xét điều đó! Bạn cần phải đi sâu vào bitorting thay vì byteorting nhưng điều đó không thay đổi kết quả: tìm bit ngoài cùng bên trái. Nếu chuỗi kia có 1 ở đó, nó sẽ là mã hóa UTF-8 dài hơn nên chắc chắn nó lớn hơn. Nếu chúng có số 0 đầu tiên ở cùng một vị trí thì chúng ta có các chuỗi bit có chiều dài giống nhau so với chúng ta.

Điều đó thật tuyệt nhưng những gì về dấu tách. Thuật toán UTF-8 khi nhìn vào nó như là một thuật toán hoàn toàn tạo bitstream có thể xử lý 31 bit số - vì vậy nó sẽ làm việc cho cây có chứa ít hơn hai tỷ nút. Con đường vật chất của bạn sẽ là một bitstream của các số được mã hóa UTF-8 so sánh tốt: Loại bỏ các số được mã hóa UTF-8 giống hệt nhất bên trái và chúng ta quay lại đoạn trước. Q.

Vì chúng ta không cần dấu tách hoặc byte tiền tố, chúng ta có thể mã hóa 128 nút đầu tiên thành một byte, sau đó là 1920 tiếp theo thành hai byte và lên đến 65535, ba byte. Đối với bốn byte, base256 sẽ giành chiến thắng. Đối với cây thực sự lớn, bạn có thể coi UTF-8 là bộ mã hóa 0-2147483647 thành luồng byte. Vì vậy, bạn có thể sử dụng nó làm mã hóa base2147483647: D

Để tóm tắt: UTF-8 là tốt nhất cho cây nhỏ và không tệ hơn nhiều so với base256 dưới hai tỷ nút. Ngoài ra cho đến khi 2^2048 hoặc nhiều tiền tố-với-length-base256 thắng. Bên cạnh đó chiến thắng có giá trị tiền tố là 2147483647 và không có gì ngoài đó.

Nguồn

2014-02-10 05:15:17 chx

Các vấn đề liên quan

 Các vấn đề liên quan