Tôi nên sử dụng mô hình Phân cấp nào? Adjacency, Nested, hoặc Enumerated?

Question

Tôi có một bảng chứa vị trí của tất cả các vị trí địa lý trên thế giới và mối quan hệ của chúng.

Dưới đây là ví dụ hiển thị cấu trúc phân cấp. Bạn sẽ thấy rằng các dữ liệu được thực sự được lưu trữ như cả ba

• liệt kê Đường dẫn
• danh sách kề
• Nested Set

Các dữ liệu rõ ràng là không bao giờ thay đổi một trong hai. Dưới đây là một ví dụ về tổ tiên trực tiếp của địa điểm Brighton ở Anh trong đó có một woeid của 13911.

Bảng: geoplanet_places (đã 5.6million hàng) hình ảnh lớn: http://tinyurl.com/68q4ndx

tôi sau đó đã bàn nhau gọi entities. Bảng này lưu trữ các mục của tôi mà tôi muốn ánh xạ tới một vị trí địa lý. Tôi lưu trữ một số thông tin cơ bản nhưng quan trọng nhất là tôi lưu trữ woeid là khóa ngoại từ geoplanet_places.

Cuối cùng, bảng entities sẽ chứa vài nghìn thực thể. Và tôi muốn một cách để có thể trả lại một cây đầy đủ của tất cả các nút có chứa các thực thể.

Tôi dự định tạo thứ gì đó để tạo điều kiện lọc và tìm kiếm các thực thể dựa trên vị trí địa lý của họ và có thể khám phá số lượng thực thể có thể tìm thấy trên nút cụ thể đó.

Vì vậy, nếu tôi chỉ có một thực thể trong bảng entities của tôi, tôi có thể có một cái gì đó như thế này

'Trái Đất (1)

Vương Quốc Anh (1)

Anh (1)

Đông Sussex (1)

Brighton và Hove City (1)

Brighton (1) `

Lets sau đó nói rằng tôi có một thực thể mà nằm ở Devon, sau đó nó sẽ hiển thị một cái gì đó như:

Trái đất (2)

United Kingom (2)

Anh (2)

Devon (1)

Đông Sussex (1) ...v.v.

(Đếm) sẽ cho biết có bao nhiêu thực thể là "bên trong" của từng vị trí địa lý không cần phải phát trực tiếp. Tôi có thể sống với việc tạo ra đối tượng của tôi mỗi giờ và bộ nhớ đệm nó.

Mục đích là để có thể tạo ra một giao diện mà có thể bắt đầu hiển thị chỉ các nước có tổ chức ..

Vì vậy, như

Argentina (1021), Chile (291), ..., United States (32,103), United Kingdom (12,338)

Sau đó, người dùng sẽ nhấp vào một vị trí, chẳng hạn như United Kindom, và sau đó sẽ được cung cấp tất cả các nút con ngay lập tức là hậu duệ của Vương quốc Anh VÀ có một thực thể trong đó.

Nếu có 32 hạt trong United Kindgdom, nhưng chỉ có 23 trong số đó cuối cùng khi bạn đi sâu xuống có các thực thể được lưu trữ trong chúng, thì tôi không muốn hiển thị khác 9. Đó chỉ là vị trí.

Trang web này aptly thể hiện các chức năng mà tôi muốn đạt được: http://www.homeaway.com/vacation-rentals/europe/r5

Làm thế nào để bạn khuyên tôi quản lý một cấu trúc dữ liệu như vậy?

Những điều tôi đang sử dụng.

• PHP
• MySQL
• Solr

tôi có kế hoạch trên có trầm khoan càng nhanh càng tốt. Tôi muốn tạo một giao diện AJAX sẽ không có vẻ gì để tìm kiếm.

Tôi cũng muốn biết bạn sẽ khuyên bạn nên lập chỉ mục cột nào.

Answer 1

Thông thường, có ba loại truy vấn trong hệ thống phân cấp gây rắc rối:

1. Return tất cả tổ tiên
2. Return tất cả hậu duệ
3. Return tất cả trẻ em (hậu duệ trực tiếp).

Dưới đây là một bảng nhỏ trong đó cho thấy việc thực hiện các phương pháp khác nhau trong MySQL:

     Ancestors Descendants Children  Maintainability InnoDB 
Adjacency list   Good  Decent  Excellent  Easy   Yes 
Nested sets (classic) Poor  Excellent Poor/Excellent Very hard  Yes 
Nested sets (spatial) Excellent Very good Poor/Excellent Very hard  No 
Materialized path  Excellent Very good Poor/Excellent Hard   Yes 

Trong children, poor/excellent nghĩa rằng câu trả lời phụ thuộc vào việc bạn đang trộn phương pháp này với danh sách kề, i. e. lưu trữ parentID trong mỗi bản ghi.

Đối với nhiệm vụ của bạn, bạn cần cả ba câu hỏi:

1. Tất cả tổ tiên để hiển thị các điều Trái Đất/UK/Devon
2. Tất cả trẻ em để hiển thị "điểm đến ở châu Âu" (các mục)
3. Tất cả các hậu duệ đều hiển thị "Các điểm đến ở châu Âu" (số lượng)

Tôi sẽ tìm các đường dẫn vật chất, vì loại phân cấp này hiếm khi thay đổi (chỉ trong trường hợp chiến tranh, nổi dậy vv).

Tạo một cột VARCHAR gọi path, chỉ số nó và điền nó với giá trị như thế này:

1:234:6345:45454: 

nơi con số này là khóa chính của cha mẹ phù hợp, theo đúng thứ tự (1 cho châu Âu, 234 cho UK vv)

Bạn cũng sẽ cần một bảng gọi là levels để giữ số từ 1 đến 20 (hoặc bất kỳ mức lồng tối đa nào bạn muốn).

Để chọn tất cả tổ tiên:

SELECT pa.* 
FROM  places p 
JOIN  levels l 
ON  SUBSTRING_INDEX(p.path, ':', l.level) <> p.path 
JOIN  places pa 
ON  pa.path = CONCAT(SUBSTRING_INDEX(p.path, ':', l.level), ':') 
WHERE p.id = @id_of_place_in_devon 

Để chọn tất cả trẻ em và tội danh nơi trong phạm vi họ:

SELECT pc.*, COUNT(pp.id) 
FROM places p 
JOIN places pc 
ON  pc.parentId = p.id 
JOIN places pp 
ON  pp.path BETWEEN pc.path AND CONCAT(pc.path, ':') 
     AND pp.id NOT IN 
     (
     SELECT parentId 
     FROM places 
     ) 
WHERE p.id = @id_of_europe 
GROUP BY 
     pc.id 

Answer 2

Đây là câu hỏi mà tôi đã đưa ra. Nó là một sự thích ứng với những gì bạn đề nghị Quassnoi.

SELECT pa.*, level, SUBSTRING_INDEX(p.ancestry, '/', l.level), p.* 
FROM  geoplanet_places p 
JOIN  levels l 
ON  SUBSTRING_INDEX(p.ancestry, '/', l.level) <> p.ancestry 
JOIN  geoplanet_places pa 
ON  pa.woeid = SUBSTRING_INDEX(SUBSTRING_INDEX(p.ancestry, '/', l.level),'/',-1) 
WHERE p.woeid = "13911" 

Điều này trả về tất cả phụ huynh của Brighton.

Vấn đề với truy vấn của bạn là nó không trả lại đường dẫn cho cha mẹ, mà thay vào đó bất kỳ nút nào chia sẻ cùng một đường dẫn.

SELECT  pa.*, GROUP_CONCAT(pa.name ORDER BY pa.lft asc),group_concat(pa.lft ), pa.ancestry 
              FROM  geo_places p 
              JOIN  levels l 
              ON  SUBSTRING_INDEX(CONCAT(p.ancestry, p.woeid,'/'), '/', l.level) <> p.ancestry 
              JOIN  geo_places pa 
              ON  pa.woeid = SUBSTRING_INDEX(SUBSTRING_INDEX(CONCAT(p.ancestry, p.woeid,'/'), '/', l.level),'/',-1) 
              WHERE p.woeid IN ("12767488","12832668","12844837","131390","131391","12846428","24534461") 
              GROUP BY p.woeid