Какую иерархическую модель мне использовать? Смежность, вложенная или перечисляемая?

Question

У меня есть таблица, которая содержит местоположение всех географических местоположений в мире и их взаимосвязи.

Вот пример, показывающий иерархию.Вы увидите, что данные на самом деле хранятся как все три

• Перечислимый путь
• Список смежностей
• Вложенный набор

Данныеочевидно, никогда не меняется.Ниже приведен пример прямых предков локации Брайтон в Англии, у которой горе составляет 13911.

Таблица: geoplanet_places (5,6 миллионов строк) Большое изображение: http://tinyurl.com/68q4ndx

У меня есть еще одна таблица с именем entities.В этой таблице хранятся мои предметы, которые я хотел бы привязать к географическому местоположению.Я храню некоторую основную информацию, но самое главное, я храню woeid, который является внешним ключом от geoplanet_places.

В итоге таблица entities будет содержать несколько тысяч объектов.И я хотел бы иметь возможность вернуть полное дерево всех узлов, которые содержат сущности.

Я планирую создать что-то, что упростит фильтрацию и поиск объектов на основе их географического местоположения и сможет обнаружить, сколько объектов можно найти на этом конкретном узле.

Итак, если у меня в таблице entities есть только одна сущность, у меня может быть что-то вроде этого

`Земля (1)

Великобритания (1))

Англия (1)

Восточный Суссекс (1)

Брайтон и Хоув Сити (1)

Брайтон (1) `

Давайте тогда скажем, что у меня есть другая сущность, которая находится в Девоне, тогда она показала бы что-то вроде:

Земля (2)

United Kingom (2)

Англия (2)

Девон (1)

Восточный Суссекс (1) ... и т. Д.

(Счет), который будетСкажите, сколько сущностей находится «внутри» каждого географического местоположения, не нужно жить.Я могу жить, генерируя свой объект каждый час и кэшируя его.

Цель состоит в том, чтобы иметь возможность создать интерфейс, который может начать отображать только страны, в которых есть объекты ..

Так как

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

Затем пользователь нажимает на местоположение, такое как United Kindom, и затем получает все непосредственные дочерние узлы, которые являются потомками Соединенного Королевства.И в них есть сущность.

Если в Соединенном Королевстве есть 32 округа, но в конечном итоге только 23 из них, когда вы развернетесь, сохранят сущности в них, я не хочу отображать остальные 9.Это только места.

Этот сайт удачно демонстрирует функциональность, которую я хочу достичь: http://www.homeaway.com/vacation-rentals/europe/r5

Как вы рекомендуете управлять такой структурой данных?

Вещи, которые я использую.

• PHP
• MySQL
• Solr

Я планирую провести тренировкуспады должны быть максимально быстрыми.Я хочу создать интерфейс AJAX, который, кажется, будет бесполезным для поиска.

Мне также было бы интересно узнать, по каким столбцам вы бы порекомендовали индексировать.

Answer 1

Как правило, в иерархиях существует три вида запросов, которые вызывают проблемы:

1. Возврат всех предков
2. Возврат всех потомков
3. Возврат всех потомков (немедленныйпотомки).

Вот небольшая таблица, которая показывает эффективность различных методов в 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

В children, poor/excellent означает, что ответ зависито том, смешиваете ли вы метод со списком смежности, т. е. сохраняете parentID в каждой записи.

Для вашей задачи вам понадобятся все три запроса:

1. Все предки, чтобы показатьЗемля / Великобритания / Девон вещь
2. Все дети, чтобы показать "Направления в Европе" (предметы)
3. Все потомки, чтобы показать "Направления в Европе" (количество)

Я бы пошел по материализованным путям, поскольку этот вид иерархии редко изменяется (только в случае войны, восстания и т. Д.).

Создайте столбец varchar с именем path, индексируйте его и заполните егозначение как это:

1:234:6345:45454:

, где числа являются первичными ключами соответствующих родителей, в правильном порядке (1 для Европы, 234 для Великобритании и т. Д.)

Вам также понадобится таблица с именем levels, чтобы сохранитьчисла от 1 до 20 (или любой другой максимальный уровень вложенности).

Чтобы выбрать всех предков:

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

Чтобы выбрать всех детей и количество мест в них:

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

Это запрос, который я задал.Это адаптация того, что вы предлагаете 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"

Это возвращает всех родителей Брайтона.

Проблема с вашим запросом заключалась в том, что он не возвращал путь к родителям, а вместо этого любой узел, который разделял тот же путь.

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