Jakiego modelu hierarchicznego powinienem użyć? Adjacency, zagnieżdżone, czy wyliczone?

Mam tabelę, która zawiera położenie wszystkich lokalizacji geograficznych na świecie i ich zależności.

Oto przykład, który pokazuje hierarchię. Zobaczysz, że dane są faktycznie przechowywane jako wszystkie trzy

  • Wyliczona Ścieżka
  • lista Pomocnicza
  • Zagnieżdżony Zestaw

Dane oczywiście nigdy się nie zmieniają. Poniżej przykład bezpośrednich przodków lokalizacji Brighton w Anglii, która ma 13911.

Tabela: geoplanet_places (mA 5,6 mln wierszy) Przodkowie Duży obraz: http://tinyurl.com/68q4ndx

Następnie mam inną tabelę o nazwie entities. Ta tabela przechowuje moje przedmioty, które chciałbym mapować do lokalizacji geograficznej. Przechowuję kilka podstawowych informacji, ale przede wszystkim przechowuję woeid, który jest obcym kluczem z geoplanet_places. Tutaj wpisz opis obrazka

Ostatecznie tabela entities będzie zawierać kilka tysięcy podmiotów. I chciałbym sposób, aby móc zwrócić pełne drzewo z wszystkie węzły, które zawierają encje.

Planuję stworzyć coś, co ułatwi filtrowanie i wyszukiwanie podmiotów na podstawie ich położenia geograficznego i będzie w stanie odkryć, ile podmiotów można znaleźć na danym węźle.

Więc jeśli mam tylko jeden byt w tabeli entities, Mogę mieć coś takiego

" Ziemia (1)

Wielka Brytania (1)

Anglia (1)

East Sussex (1)

Brighton And Hove City (1)

Brighton (1) "

Powiedzmy, że mam inny byt, który znajduje się w Devon, wtedy pokaże coś w stylu:

Ziemia (2)

United Kingom (2)

Anglia (2)

Devon (1)

East Sussex (1) ... etc

Liczniki, które mówią, ile Bytów znajduje się" w " każdej lokalizacji geograficznej, nie muszą być żywe. I can live generując mój obiekt co godzinę i buforując go.

Celem jest stworzenie interfejsu, który może zacząć pokazywać tylko kraje, które mają podmioty..

Tak jak

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

Następnie użytkownik kliknie na lokalizację, taką jak United Kindom, a następnie otrzyma wszystkie bezpośrednie węzły potomne, które są potomkami Wielkiej Brytanii i mają w nich encję.

Jeśli są 32 powiaty w United Kindgdom, ale tylko 23 z nich w końcu, gdy wywiercić w dół mają podmioty zapisane w nich, to nie chcę wyświetlać pozostałe 9. To tylko miejsca.

Ta strona trafnie demonstruje funkcjonalność, którą chcę osiągnąć: http://www.homeaway.com/vacation-rentals/europe/r5 Tutaj wpisz opis obrazka

Jak zalecić zarządzanie taką strukturą danych?

Things I am używam.

  • PHP
  • MySQL
  • Solr

Planuję, aby wiertła były tak szybkie, jak to możliwe. Chcę stworzyć interfejs AJAX, który będzie zbędny do wyszukiwania.

Chciałbym również wiedzieć, na których kolumnach polecasz indeksowanie.

Author: Layke, 2011-01-28
Source

2 answers

Zazwyczaj w hierarchii występują trzy rodzaje zapytań, które powodują problemy:]}

  1. Return all ancestors
  2. Return all potomkowie
  3. zwróć wszystkie dzieci (bezpośrednich potomków).

Oto mała tabela, która pokazuje wydajność różnych metod w 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

W children, poor/excellent oznacza, że odpowiedź zależy od tego, czy mieszasz metodę z listą przylegającą, tzn. przechowujesz parentID w każdym rekord.

Do zadania potrzebne są wszystkie trzy zapytania:

  1. wszyscy przodkowie, aby pokazać ziemię / UK / Devon thing
  2. wszystkie dzieci, aby pokazać "miejsca docelowe w Europie" (przedmioty)
  3. wszyscy potomkowie, aby pokazać "miejsca w Europie" (liczą)
[14]}poszedłbym po zmaterializowane ścieżki, ponieważ taka hierarchia rzadko się zmienia (tylko w przypadku wojny, buntu itp.).

Utwórz kolumnę varchar o nazwie path, zindeksuj ją i wypełnij wartością tak: 

1:234:6345:45454:

Gdzie liczby są głównymi kluczami odpowiednich rodziców, we właściwej kolejności (1 dla Europy, 234 dla Wielkiej Brytanii itp.)

Będziesz również potrzebował tabeli o nazwie levels, Aby zachować liczby od 1 do 20 (lub dowolny maksymalny poziom zagnieżdżania, jaki chcesz).

Aby wybrać wszystkich przodków: 

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

Aby wybrać wszystkie dzieci i zliczyć w nich miejsca: 

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
 9
Author: Quassnoi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-12 06:21:39

To jest pytanie, które wymyśliłem. Jest to adaptacja tego, co sugerujesz 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"
To zwraca wszystkich rodziców z Brighton.

Problem z Twoim zapytaniem polegał na tym, że nie zwracano ścieżki rodzicom, ale każdy węzeł, który dzielił tę samą ścieżkę. 

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
 0
Author: Layke,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-02-18 11:43:15