Which Hierarchical model should I use? Adjacency, Nested, or Enumerated?

Question

I have a table which contains a location of all geographical locations in the world and their relationships.

Here is a example that shows the hierarchy. You will see that the data is actually stored as all three

• Enumerated Path
• Adjacency list
• Nested Set

The data obviously never changes either. Below is an example of direct ancestors of the location Brighton in England which has a woeid of 13911.

Table: geoplanet_places (Has 5.6million rows) Large Image: http://tinyurl.com/68q4ndx

I then have another table called entities. This table stores my items which I would like to map to a geographical location. I store some basic information but most important I store the woeid which is a foreign key from geoplanet_places.

Eventually the entities table will contain several thousand entities. And I would like a way to be able to return a full tree of all of the nodes which contain entities.

I plan on creating something to facilitate the filtering and searching of entities based on their geographical location and be able to discover how many entities can be found on that particular node.

So if I only have one entity in my entities table, I might have something like this

`Earth (1)

United Kingdom (1)

England (1)

East Sussex (1)

Brighton and Hove City (1)

Brighton (1)`

Lets then say that I have another entity which is located in Devon, then it would show something like:

Earth (2)

United Kingom (2)

England (2)

Devon (1)

East Sussex (1) ... etc

The (Counts) which will say how many entities are "inside" of each geographical location do not need to be live. I can live with generating my object every hour and caching it.

The aim, is to be able to create an interface which might start out showing only the Countries which have entities..

So like

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

Then the user will click on a location, such as United Kindom, and will then be given all of the immediate child nodes which are descendants of United Kingdom AND have an entity in them.

If there are 32 Counties in United Kindgdom, but only 23 of them eventually when you drill down have entities stored in them, then I don't want to display the other 9. It is only locations.

This site aptly demonstrates the functionality that I wish to achieve: http://www.homeaway.com/vacation-rentals/europe/r5

How do you recommend that I manage such a data structure?

Things I am using.

• PHP
• MySQL
• Solr

I plan on having the Drill downs be as rapid as possible. I want to create an AJAX interface that will be seemless for searching.

I would also be interested to know which columns you would recommend indexing on.

Answer 1

Typically, there are three kinds of queries in the hierarchies which cause troubles:

1. Return all ancestors
2. Return all descendants
3. Return all children (immediate descendants).

Here's a little table which shows the performance of different methods in 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

In children, poor/excellent means that the answer depends on whether you are mixing the method with adjacency list, i. e. storing the parentID in each record.

For your task, you need all three queries:

1. All ancestors to show the Earth / UK / Devon thing
2. All children to show "Destinations in Europe" (the items)
3. All descendants to show "Destinations in Europe" (the counts)

I would go for materialized paths, since this kind of hierarchy rarely changes (only in case of war, revolt etc).

Create a varchar column called path, index it and fill it with the value like this:

1:234:6345:45454:

where the numbers are primary keys of the appropriate parents, in correct order (1 for Europe, 234 for UK etc.)

You will also need a table called levels to keep numbers from 1 to 20 (or whatever maximum nesting level you want).

To select all ancestors:

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

To select all children and counts of places within them:

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