Thực hiện cấu trúc dữ liệu phân cấp trong cơ sở dữ liệu

Question

Tôi biết có hai cách tiếp cận: danh sách kề và cây lồng nhau. Người ta nói rằng danh sách kề nhau có thể trở nên chậm chạp để sử dụng trên truyền tải vì có nhiều truy vấn. Nhưng tôi không biết bất kỳ con số thực tế nào cho việc này. Trang web tôi đang tạo sẽ có trong 200 trang. Đang truyền tải để tạo (ví dụ) một sơ đồ trang web sẽ mất nhiều thời gian hơn khoảng 0,3 giây?

Chạy trên MySQL (innoDB) với ngăn xếp LAMP.

Tôi muốn thực hiện tính kề nếu có thể do thiết kế đơn giản hơn.

Cảm ơn.

Answer 1

Dưới đây là một vài câu hỏi có thể giúp bạn:

SQL how to store and navigate hierarchies

Which is the best database schema for my navigation

Answer 2

Cách tiếp cận khác được gọi là "lồng nhau set", tôi nghĩ, không phải "lồng nhau cây".

Dù sao, một điều tốt về bản đồ trang web là bạn có thể biết độ sâu tối đa của nó. Tôi nghĩ rằng vấn đề với mô hình kề là SQL tương ứng hoạt động trên một cấp tại một thời điểm, vì vậy nếu bạn có các cấp 'n' thì bạn cần một vòng lặp của câu lệnh SQL 'n' ... nhưng tôi nghĩ (tôi ' m không chắc chắn) nếu bạn biết trước tối đa 'n' thì bạn có thể mã SQL tương ứng với số lượng cố định nhiều cấp.

0,3 giây âm thanh với tôi như một thời gian rất dài để tìm 200 trang, vì vậy có thể là OK.

Ngoài ra, bản đồ trang web không được cập nhật thường xuyên; Vì vậy, ngay cả khi nó mất một thời gian dài để lấy từ SQL, bạn có thể có thể cache cây lấy/tính toán trong RAM. Bên cạnh đó, thay vì lo lắng về SQL để xây dựng một cây, bạn chỉ có thể lưu trữ nó càng đơn giản càng tốt (như danh sách kề), lấy nó từ cơ sở dữ liệu như một tập hợp các hàng đơn giản và xây dựng cây trong RAM. (sử dụng các vòng lặp trong ngôn ngữ lập trình bậc cao của bạn) thay vì sử dụng các vòng lặp trong SQL để xây dựng cây bằng cách sử dụng các câu lệnh SQL.

Answer 3

Bài viết Managing Hierarchical Data in MySQL đọc chi tiết về điều này.

Tôi muốn giới thiệu kỹ thuật "lồng nhau", vì nó cho phép bạn lấy toàn bộ cây (và con của nó) trong một truy vấn. Về cơ bản đọc là giá rẻ nhưng viết là tốn kém bởi vì toàn bộ cây phải được cân bằng lại. Nhưng trong trường hợp bạn có 99% lần đọc thì nó hoàn toàn chính đáng.

Answer 4

Để hoàn thành: Oracle có các toán tử START_WITH và CONNECT_BY: xem tài liệu Hierarchical Queries này.

Answer 5

Có nhiều tùy chọn hơn chỉ hai tùy chọn bạn đề cập.Có:

• host ở Danh sách (các "PARENT_ID" một gần như tất cả mọi người sử dụng)
• Nested Thiết
• Đường dẫn Enumeration
• Đóng Table (aka host ở xa Relation)

Xem câu trả lời của tôi thành "What is the most efficient/elegant way to parse a flat table into a tree?"

Hoặc một vài cuốn sách:

• "Trees and Hierarchies in SQL for Smarties" của Joe Celko.
• "SQL Design Patterns" của Vadim Tropashko.

Answer 6

Cách tiếp cận ngây thơ để phân tích danh sách kề cần nhiều truy vấn và danh sách lớn có thể mất một khoảng thời gian đáng kể để xây dựng trong bộ nhớ. Để tham khảo, cách tiếp cận ngây thơ tôi đề cập đến có thể được tóm tắt là: Chọn tất cả các mục không có cha mẹ, Sau đó cho mỗi mục đệ quy nhận được đó là trẻ em. Cách tiếp cận này yêu cầu truy vấn cơ sở dữ liệu n + 1.

Tôi đã sử dụng phương pháp sau đây để xây dựng danh sách kề với 1 truy vấn. Chọn tất cả các mục tạo thành cơ sở dữ liệu. Chuyển tất cả các mục vào một mảng được lập chỉ mục bằng khóa của chúng. Traverse mảng và gán một tham chiếu từ đối tượng cha mẹ cho mỗi đối tượng là con của nó. Traverse mảng lần thứ hai và loại bỏ tất cả các đối tượng con để lại chỉ các đối tượng cấp cơ sở.

Vì bạn đề cập LAMP, mã PHP để làm điều này là xấp xỉ như sau:

<?php 
// Assumes $src is the array if items from the database. 
$tmp = array(); 

// Traverse the array and index it by id, ensuing each item has an empty array of children. 
foreach ($src as $item) { 
    $item['children'] = array(); 
    $tmp[$item['id']] = $item; 
} 

// Now traverse the array a second time and link children to their parents. 
foreach ($tmp as $id => $item) { 
    if ($item['parent_id'] != 0 || $item['parent_id'] !== NULL) { 
    $tmp[$item['parent_id']]['children'][$id] = &$tmp[$id]; 
    } 
} 

// Finally create an array with just root level items. 
$tree = array(); 
foreach ($tmp as $id => $item) { 
    if ($item['parent_id'] == 0 || $item['parent_id'] === NULL) { 
    $tree[$id] = $item; 
    } 
} 

// $tree now contains our adjacency list in tree form. 
?> 

Xin lưu ý mã này là nhằm minh họa cho một kỹ thuật để xây dựng một danh sách kề từ một truy vấn cơ sở dữ liệu duy nhất. Nó có thể có thể được tối ưu hóa cho tiêu thụ bộ nhớ ít hơn, vv Nó cũng chưa được thử nghiệm.

Jim,