乐趣区

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

树状结构的数据,就是符合“每个上级节点可以有多个子节点,而每个子节点都只有一个上级节点”这一模型的数据。比如一个 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;。注意 zoneid 30 是全局的标识,而不是指 region 3 下面的第 30 个 zone,因为 zone 表是唯一的。(不考虑按 regionid 来分表的情况)
如果要获取 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 的 zonesfield 里面。假设 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 暴露了一些问题:

虽然我们可以用 jsonb_array_length 代替 COUNT,但如果要用到 SUM,MAX 或其他更为复杂的聚合操作,就只能通过不那么直接了当的类型转换把数组里面的值挖出来。不那么直接了当通常意味着低效和难以理解。
这种情况下不存在 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 了。

退出移动版