用关系型数据库处理树状结构的数据的一些想法

树状结构的数据，就是符合“每个上级节点可以有多个子节点，而每个子节点都只有一个上级节点”这一模型的数据。

比如一个 region 可以有多个 zones，而每个 zone 又能有多个 servers；但是每个 server 只位于某个 zone，

每个 zone 又只位于某个 region。

这种模型，如果换用关系型数据库的行话说，便是有着层次关系的一连串一对多关系。于是我们可以把它存储成一

系列的一对多的表，每个表有着若干个上级表 ID 的字段。比如 zone 表里面包含 region_id 列，server 表里面

包含 region_id 和 zone_id 列。

继续沿用 region - zone - server 的例子。在这个例子里，如果我们想知道 region 3 的 zone 30 下面有多

少台 server，可以用 select count(*) from server where region_id = 3 and zone_id = 30; 。注意 zone

id 30 是全局的标识，而不是指 region 3 下面的第 30 个 zone，因为 zone 表是唯一的。（不考虑按 region

id 来分表的情况）

如果要获取 region 3 下面所有的 zone 和 server 的数据，则可以这么做：

select * from region where id = 3;
select * from zone where region_id = 3;
select * from server where region_id = 3;

但如果我们想获取某些 region 下面的所有的 zone 和 server 的数据，该怎么办呢？比如我想查，location 位

于华南的每个 region 下面的所有的 zone 和 server 的数据。

zone 表和 server 表里只记录了 region id，所以没法直接去查。一个选择是做 denormalization，就是在 zone

表和 server 表里冗余一部分 region 的数据。冗余的后果，就是更新数据时需要更新多个表，且容易会有数据不

一致的问题。另一个选择是，先查出顶层 region 的 ids，然后再逐层查下去，像是这样：

select id from region where location = 'South China';
select * from zone where region_id in (...); -- 应用层使用刚刚的  SQL  语句得到的 id 来查询
select * from server where region_id in (...);

当然，如果顶层匹配的 id 有上百个之多，使用 in (...) 效率可能会不够好，可以考虑下用 inner join 的

方式。

这种方式有些小缺陷，就是你需要在应用层里，把三个查询的结果，组装成每一个匹配的 region 的数据。好在

zone 和 server 表返回的数据里面包含了上级表的 id，在应用层里做也不难。

如果你的查询请求里面， from region where location = 这种按条件过滤的所占比例不小，可以考虑下把树状

结构存储成一个 JSON，而不是三张独立的表。只要你用的关系数据库版本不是太陈旧，基本上都支持 JSON 类型

，比如 PostgreSQL 里面就有 jsonb。

现在查询 location 位于华南的 region，只要这么做：

select id, zones from region where location = 'South China';

返回的结果大概是这个样子的：

id |                                zones
----+---------------------------------------------------------------------
  1 | [{"size": 100, "servers": [1, 2, 3]}, {"size": 50, "servers": [1]}]
  2 | [{"size": 100, "servers": [1, 2, 3]}, {"size": 50, "servers": [1]}]
(2 rows)

现在就不用自己去组装结果了。而且性能也比分三个表的好很多，因为存在同一个 JSON 里面，就不用再走 `in

(...) 或者 inner join` 去另外几张表里面筛数据。

但在这种情况下，该怎么查询 region 3 的 zone 30 下面有多少台 server 呢？

此时 zone id 30 是没有意义的，因为并不存在 zone 表，所有的 zones 都分别存在某个 region 的 zones

field 里面。假设 zone 30 是 region 3 的第 10 个 zone，则可以写出如下的 SQL：

select jsonb_array_length(zones#>'{9,servers}') from region where id = 3;

首先我们定位到 region id = 3。

接着从 zones field 中取第 10 个 zone 的 servers，注意算数时要从 0 开始，所以写的是 9 （第 10 个）。

然后由于 servers 是一个 JSON 数组，我们可以调用 jsonb_array_length 方法，轻松获取它的长度。

这个 SQL 暴露了一些问题：

1. 虽然我们可以用 jsonb_array_length 代替 COUNT ，但如果要用到 SUM ， MAX 或其他更为复杂的聚合
   操作，就只能通过不那么直接了当的类型转换把数组里面的值挖出来。不那么直接了当通常意味着低效和难以
   理解。
2. 这种情况下不存在 zone id。如果你只想查某个 zone 下面的内容，只能先定位到 region，再向下查询到
   zone。在有 zone 表的时候，我们可以走 zone id index，而现在只能走 region id index。
   由于 jsonb 会记录数组中每个元素的 offset，也许定位到具体某个 zone 的开销不会多于在 B 树中搜索某个
   zone id。但是你首先要把整个 region 3 从文件系统里读出来。

当然了，比起 select count(*) from server where region_id = 3 and zone_id = 30; ，这个查询并非一无是

处。首先 jsonb_array_length 不需要像 COUNT 那样逐个计数，因为 jsonb 会记录数组的大小；其次，匹配

到的 server row 可能不连续，考虑到 OS 的 page cache，不一定要比把整个 region 3 从文件系统里读出来要好。

不过如果我想要 region 3 的 zone 30 的 server 300 呢？

总而言之，如果你的查询里面，很多是指明某组 id 的，那么分成多个表会更好；如果你的查询里面，很多是根据

高层节点的某个属性做过滤，不怎么涉及低层节点的，那么存成 JSON 会更好。当然，假设你的树状数据是异构的，比

如 region 下面除了 zone，还有其他乱七八糟、不可名状的节点，那么只能存成 JSON 了。