查找嵌套位置标签的最佳数据结构 [英] Best data structure for finding tags of nested locations

问题描述

有人指出，我的数据结构体系很烂。

Somebody pointed out that my data structure architecture sucks.

我有个位置表存储位置的名称。然后，我有一个标记表，该表存储有关那些位置的信息。 位置具有一个层次结构，我想使用该层次结构来获取所有标记。

I have a locations table which stores the name of a location. Then I have a tags table which stores information about those locations. The locations have a hierarchie which I want to use to get all tags.

位置：

USA <- California <- San Francisco <- Mission St

标签：

USA: English
California: Sunny
California: West coast
San Francisco: Sea side
Mission St: Cable car station 

如果有人要求提供有关 Mission St的信息我想提供它的所有标记及其祖先（ [英语，晴天，西海岸， 海边，缆车站] 。如果我要求获取加利福尼亚的所有标签 c>答案应为 [英语，晴天，西海岸] 。

If somebody requests information about the Mission St I want to deliver all tags of it and it's ancestors (["English", "Sunny", "West coast", "Sea side", "Cable car station"]. If I request all tags of California the answer would be ["English", "Sunny", "West coast"].

我正在寻找最佳的读取性能！我不在乎写入性能。该数据不会经常更改。我也不在乎表的大小。要么。

I'm looking for the best read performance! I don't care about write performance. This data is not changed very often. And I don't care about table sizes either. If I need more or larger tables to solve this quicker so be it.

所以我目前我正在考虑设置以下表格：

So currently I'm thinking about setting up these tables:

位置

id | name
---|--------------
1  | USA
2  | California
3  | San Francisco
4  | Mission St

标签

id | location_id | name
---|-------------|------------------
1  | 1           | English
2  | 2           | Sunny
3  | 2           | West coast
4  | 3           | Sea side
5  | 4           | Cable car station

祖先

我添加了位置字段来存储层次结构。

I added a position field to store the hierarchy.

| id | location_id | ancestor_id | position |
|----|-------------|-------------|----------|
| 1  | 2           | 1           | 1        |
| 2  | 3           | 2           | 1        |
| 3  | 3           | 1           | 2        |
| 4  | 4           | 3           | 1        |
| 5  | 4           | 2           | 2        |
| 6  | 4           | 1           | 3        |

问题

这是一个好的解决方案吗解决问题还是有更好的解决方案？我想尽快选择任何给定位置的所有标签，包括其祖先的所有标签。我正在使用PostgreSQL数据库，但我认为这是一个纯SQL体系结构问题。

Question

Is this a good solution to solve the problem or is there a better one? I want to select as fast as possible all tags of any given location including all the tags of it's ancestors. I'm using a PostgreSQL database but I think this is a pure SQL architecture problem.

推荐答案

您的问题似乎由两个组成挑战。最有趣的是如何在关系数据库中存储层次结构。有很多答案-您提出的答案是最常见的。

Your problem seems to consist of two challenges. The most interesting is "how do I store hierarchies in a relational database". There are lots of answers to that - the one you've proposed is the most common.

还有一个名为 嵌套集的替代方案（阅读速度更快（在您的示例中，查找特定层次结构中的所有位置将在 x和y之间）。

There's an alternative called "nested set" which is faster for reading (in your example, finding all locations within a particular hierarchy would be "between x and y".

Postgres具有专门为阶层提供支持；我认为这也将提供出色的性能。

Postgres has dedicated support for hierachies; I'd assume this would also provide great performance.

问题的第二部分是给我层次结构中的路径，检索所有匹配的标签。最简单的选择是按照您的建议加入标签表。

The second part of your question is "given a path in my hierarchy, retrieve all matching tags". The easiest option is to join to the tags table as you suggest.

最后一个方面是您应该对非规范化/预先计算。我通常建议构建和优化规范化解决方案，并且仅在需要时进行非规范化。

The final aspect is "should you denormalize/precalculate". I usually recommend building and optimizing the "normalized" solution and only denormalize when you need to.

这篇关于查找嵌套位置标签的最佳数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！