Cấu trúc cây trong cơ sở dữ liệu nosql

Question

Tôi đang phát triển một ứng dụng cho Google App Engine sử dụng BigTable cho kho dữ liệu của nó.

Đây là một ứng dụng về cách viết truyện một cách cộng tác. Đó là một dự án sở thích rất đơn giản mà tôi đang làm việc chỉ để giải trí. Đó là mã nguồn mở và bạn có thể thấy nó ở đây: http://story.multifarce.com/

Ý tưởng là bất cứ ai cũng có thể viết một đoạn văn, sau đó cần được xác thực bởi hai người khác. Một câu chuyện cũng có thể được phân nhánh tại bất kỳ đoạn văn nào, để một phiên bản khác của câu chuyện có thể tiếp tục theo một hướng khác.

Hãy tưởng tượng cấu trúc cây sau:

Mỗi số sẽ là một đoạn văn. Tôi muốn có thể chọn tất cả các đoạn trong mỗi câu chuyện độc đáo. Về cơ bản, những câu chuyện độc đáo đó là (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) và (2, 5, 9, 4). Bỏ qua rằng nút "2" xuất hiện hai lần, tôi chỉ lấy một sơ đồ cấu trúc cây từ Wikipedia.

Tôi cũng làm một sơ đồ của một giải pháp đề xuất: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

Làm thế nào tôi có thể thiết lập một cấu trúc là hiệu suất hiệu quả cho cả văn bản, nhưng quan trọng nhất cho việc đọc?

Answer 1

Có một số cách nổi tiếng để thể hiện cây trong cơ sở dữ liệu; mỗi người trong số họ có ưu và khuyết điểm của họ. Dưới đây là thông dụng phổ biến nhất:

• Adjacency list, trong đó mỗi nút lưu ID của cha mẹ.
• Materialized path, đó là chiến lược Keyur mô tả. Đây cũng là cách tiếp cận được sử dụng bởi các nhóm thực thể (ví dụ: các thực thể cha mẹ) trong App Engine. Nó cũng nhiều hơn hoặc ít hơn những gì bạn đang mô tả trong bản cập nhật của bạn.
• Nested sets, trong đó mỗi nút có ID 'trái' và 'phải', sao cho tất cả các nút con được chứa trong phạm vi đó.
• Danh sách liền kề được ghi lại bằng ID gốc.

Mỗi loại này đều có những ưu điểm và nhược điểm riêng. Danh sách adjacency rất đơn giản và giá rẻ để cập nhật, nhưng yêu cầu nhiều truy vấn để truy xuất một cây con (một cho mỗi nút cha). Danh sách kề được tăng cường giúp có thể lấy toàn bộ cây bằng cách lưu trữ ID của nút gốc trong mỗi bản ghi.

Đường dẫn vật liệu dễ triển khai và giá rẻ để cập nhật và cho phép truy vấn các subtrees tùy ý, nhưng áp đặt chi phí gia tăng cho cây sâu.

Bộ lồng nhau khó thực hiện hơn và yêu cầu cập nhật, trung bình, một nửa số nút mỗi khi bạn thực hiện chèn. Chúng cho phép bạn truy vấn các subtrees tùy ý, mà không có đường dẫn vật liệu có độ dài khóa phát sinh.

Trong trường hợp cụ thể của bạn, có vẻ như bạn không thực sự cần một cấu trúc cây: tất cả các câu chuyện, phân nhánh ra một bản gốc mặc dù nó có thể được, đứng một mình.Những gì tôi sẽ đề nghị là có một mô hình 'Story', trong đó có một danh sách các phím của các đoạn văn của nó (Ví dụ, trong Python một db.ListProperty (db.Key)). Để hiển thị câu chuyện, bạn tìm nạp Câu chuyện, sau đó thực hiện tìm nạp hàng loạt cho tất cả các Đoạn. Để phân nhánh một câu chuyện, chỉ cần sao chép mục nhập câu chuyện - để nguyên tham chiếu đến các đoạn văn không thay đổi.

Answer 2

Một giải pháp mà tôi có thể nghĩ đến là - đường dẫn đến nút cũng là chìa khóa của nút đó. Vì vậy, chìa khóa của nút 11 là "2/7/6/11". Bạn có thể đi qua đường dẫn bằng cách tra cứu khóa đơn giản của tất cả các phím trong đường dẫn - "2/7/6/11", "2/7/6", "2/7", "2"