种树的人,
种下希望。
种一棵树露西·拉科姆(Lucy Larcom)?
在这篇文章中,我将向您展示一些用于管理表示为 树 数据结构的分层数据的选项。当您需要实现以下内容时,这是自然的方法:
如果您已经知道图是什么,那么树基本上就是一个没有任何循环的图。您可以像这样直观地代表一个人。
在关系数据库中存储树有多种选择。在下面的部分中,我将向您展示其中三个:
这篇博文将分为两个部分。在第一个中,介绍了替代方案,您将了解如何加载和存储数据 - 基础知识。排除这一点,在第二部分中,重点更多地放在它们的比较和权衡上,例如,我想看看数据量增加时会发生什么以及适当的索引策略是什么。
如果您有兴趣查看,您将在下面的部分中看到的所有代码都可以在这里找到。
正在运行的用例将是员工及其经理的用例,每个用例的ID将与您在上面显示的树可视化中看到的完全相同。
我正在使用最近发布的 Postgres 17 和 Testcontainers。这为我提供了可重复的设置。例如,我们可以使用初始化 SQL 脚本自动创建包含必要表的 Postgres 数据库,并填充一些测试数据。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
让我们开始看看第一种方法。
这是管理分层数据的第一个解决方案,因此我们可以预期它仍然广泛存在于代码库中,因此您有时可能会遇到它。我们的想法是,我们将经理的 ID(或更一般地说,父 ID)存储在同一行中。一旦我们查看表结构,很快就会清楚。
邻接列表选项对应的表格如下所示:
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
除了上述之外,为了确保数据完整性,我们还应该编写约束检查,至少确保以下几点:
特别是对于本系列的第 2 部分,我们需要一种方法来生成填充架构所需的尽可能多的数据。为了清楚起见,让我们首先一步一步地进行,然后递归地进行。
我们首先简单地在层次结构中显式插入三个级别的员工。
您可能已经了解 Postgres 中的 CTE - 它们是在主查询上下文中执行的辅助命名查询。下面,你可以看到我是如何在之前的关卡的基础上构建每个关卡的。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
让我们验证到目前为止它是否按预期工作,并为此目的进行计数以查看已插入了多少个元素。您可以将其与我在本文开头展示的树可视化中的节点数进行比较。
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
看起来还不错!三个级别,总共有 15 个节点。
是时候转向递归方法了。
编写递归查询遵循标准程序。我们定义一个基本步骤和一个递归步骤,然后使用 union all 将它们“连接”到彼此。在运行时,Postgres 将遵循这个配方并生成我们所有的结果。看看吧。
with root as ( insert into employees(manager_id, name) select null, 'root' || md5(random()::text) from generate_series(1, 1) g returning employees.id ), first_level as ( insert into employees(manager_id, name) select root.id, 'first_level' || md5(random()::text) from generate_series(1, 2) g, root returning employees.id ), second_level as ( insert into employees(manager_id, name) select first_level.id, 'second_level' || md5(random()::text) from generate_series(1, 2) g, first_level returning employees.id ) insert into employees(manager_id, name) select second_level.id, 'third_level' || md5(random()::text) from generate_series(1, 2) g, second_level;
运行后,我们再统计一下,看看是否插入了相同数量的元素。
postgres=# select count(*) from employees; count ------- 15 (1 row)
酷!我们正在做生意。我们现在可以用我们想要的任意数量的级别和元素填充模式,从而完全控制插入的体积。不用担心,如果现在递归查询看起来仍然有点困难,我们稍后会在编写查询来检索数据时重新审视它们。
现在,让我们继续看一下可用于将表映射到 Java 类的 Hibernate 实体。
create temporary sequence employees_id_seq; insert into employees (id, manager_id, name) with recursive t(id, parent_id, level, name) AS ( select nextval('employees_id_seq')::bigint, null::bigint, 1, 'root' from generate_series(1,1) g union all select nextval('employees_id_seq')::bigint, t.id, level+1, 'level' || level || '-' || md5(random()::text) from t, generate_series(1,2) g where level < 4 ) select id, parent_id, name from t; drop sequence employees_id_seq;
没什么特别的,只是经理和员工之间的一对多关系。你看到了这一切的到来。我们开始查询吧。
经理的所有下属
为了检索 ID 引用的特定经理的下属的所有员工,我们将再次编写一个递归查询。您将再次看到基本步骤和与基本步骤链接的递归步骤。然后 Postgres 将重复此操作并检索查询的所有相关行。我们以 ID = 2 的员工为例。这是一种视觉表示,希望可以更容易地理解我刚才描述的内容。我没有包含所有结果,仅包含前几个结果。
这是用于查询后代的 JPQL 查询:
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
在诸如上述查询之类的查询中,为了使它们更清晰并避免需要写入我们将写入结果的记录的完全限定名称,我们可以使用 hypersistence-utils 库编写一个 ClassImportIntegratorProvider:
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
它可以工作,但是让我们更深入地了解一下 Hibernate 生成的内容。了解幕后发生的事情总是好的,否则我们可能会因每个用户请求而导致效率低下,这会增加。
我们必须使用以下设置启动 Spring Boot 应用程序:
with root as ( insert into employees(manager_id, name) select null, 'root' || md5(random()::text) from generate_series(1, 1) g returning employees.id ), first_level as ( insert into employees(manager_id, name) select root.id, 'first_level' || md5(random()::text) from generate_series(1, 2) g, root returning employees.id ), second_level as ( insert into employees(manager_id, name) select first_level.id, 'second_level' || md5(random()::text) from generate_series(1, 2) g, first_level returning employees.id ) insert into employees(manager_id, name) select second_level.id, 'third_level' || md5(random()::text) from generate_series(1, 2) g, second_level;
好啦,我们来看看吧。这是 Hibernate 生成的后代的查询。
postgres=# select count(*) from employees; count ------- 15 (1 row)
嗯 - 看起来比预期的要复杂一些!让我们看看是否可以稍微简化一下,记住我之前向您展示的有关基本步骤以及与基本步骤相关的递归步骤的图片。我们不需要做更多的事情。看看你对以下的看法。
create temporary sequence employees_id_seq; insert into employees (id, manager_id, name) with recursive t(id, parent_id, level, name) AS ( select nextval('employees_id_seq')::bigint, null::bigint, 1, 'root' from generate_series(1,1) g union all select nextval('employees_id_seq')::bigint, t.id, level+1, 'level' || level || '-' || md5(random()::text) from t, generate_series(1,2) g where level < 4 ) select id, parent_id, name from t; drop sequence employees_id_seq;
好多了!我们删除了一些不必要的连接。这预计会使查询速度更快,因为要做的工作更少。
最后一步,让我们清理查询并将 Hibernate 添加的表名称替换为更易于人类阅读的名称。
postgres=# select count(*) from employees; count ------- 15 (1 row)
好吧,是时候看看我们如何“爬上”树了。
链条上的所有经理
我们首先尝试写下获取 ID = 14 的员工的经理的概念步骤。
看起来非常像后代的,只是基础步骤和递归步骤之间的连接是另一种方式。
我们可以编写如下所示的 JPQL 查询:
@Entity @Table(name = "employees") @Getter @Setter public class Employee { @Id private Long id; private String name; @ManyToOne(fetch = FetchType.LAZY) @JoinColumn(name = "manager_id") private Employee manager; @OneToMany( mappedBy = "parent", cascade = CascadeType.ALL, orphanRemoval = true ) private List<Employee> employees = new ArrayList<>(); }
就是这样!我查看了生成的 SQL 查询,但找不到任何可以删除的额外命令。是时候继续方法 2了。
ltree 是一个 Postgres 扩展,我们可以使用分层树结构作为物化路径(从树的顶部开始)。例如,我们将这样记录叶节点 8 的路径:1.2.4.8。它附带了几个有用的功能。我们可以将它用作表格列:
return entityManager.createQuery(""" with employeeRoot as ( select employee.employees employee from Employee employee where employee.id = :employeeId union all select employee.employees employee from Employee employee join employeeRoot root ON employee = root.employee order by employee.id ) select new Employee( root.employee.id ) from employeeRoot root """, Employee.class ) .setParameter("employeeId", employeeId) .getResultList();
为了用测试数据填充上表,我采取的方法基本上是使用以下 SQL 命令从用于您之前看到的邻接列表的表中迁移生成的数据。这又是一个递归查询,每一步都会将元素收集到累加器中。
public class ClassImportIntegratorProvider implements IntegratorProvider { @Override public List<Integrator> getIntegrators() { return List.of( new ClassImportIntegrator( singletonList( Employee.class ) ) ); } }
这是上述命令生成的条目。
@TestConfiguration(proxyBeanMethods = false) class TestcontainersConfiguration { private static final String POSTGRES = "postgres"; @Bean @ServiceConnection PostgreSQLContainer<?> postgresContainer() { return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest")) .withUsername(POSTGRES) .withPassword(POSTGRES) .withDatabaseName(POSTGRES) .withInitScript("init-script.sql"); } }
我们可以继续编写 Hibernate 实体。为了映射 ltree 类型的列,我实现了 UserType。然后我可以使用 @Type(LTreeType.class) 映射路径字段:
create table employees ( id bigserial primary key, manager_id bigint references employees name text, );
我们已准备好编写一些查询。在本机 SQL 中,它看起来如下所示:
with root as ( insert into employees(manager_id, name) select null, 'root' || md5(random()::text) from generate_series(1, 1) g returning employees.id ), first_level as ( insert into employees(manager_id, name) select root.id, 'first_level' || md5(random()::text) from generate_series(1, 2) g, root returning employees.id ), second_level as ( insert into employees(manager_id, name) select first_level.id, 'second_level' || md5(random()::text) from generate_series(1, 2) g, first_level returning employees.id ) insert into employees(manager_id, name) select second_level.id, 'third_level' || md5(random()::text) from generate_series(1, 2) g, second_level;
但是让我们用 JPQL 编写查询。为此,我们必须首先编写自定义的 StandardSQLFunction。这将允许我们定义 Postgres 本机运算符的替换。
postgres=# select count(*) from employees; count ------- 15 (1 row)
然后我们必须将其注册为 FunctionContributor,如下所示:
create temporary sequence employees_id_seq; insert into employees (id, manager_id, name) with recursive t(id, parent_id, level, name) AS ( select nextval('employees_id_seq')::bigint, null::bigint, 1, 'root' from generate_series(1,1) g union all select nextval('employees_id_seq')::bigint, t.id, level+1, 'level' || level || '-' || md5(random()::text) from t, generate_series(1,2) g where level < 4 ) select id, parent_id, name from t; drop sequence employees_id_seq;
最后一步是在 META-INF/services 文件夹中创建一个名为 org.hibernate.boot.model.FunctionContributor 的资源文件,我们将在其中添加一行包含上面类的完全限定名称。
好吧,酷!我们终于可以编写以下查询:
postgres=# select count(*) from employees; count ------- 15 (1 row)
例如,我们可以这样调用该方法来检索所有包含 ID = 2 的路径:
@Entity @Table(name = "employees") @Getter @Setter public class Employee { @Id private Long id; private String name; @ManyToOne(fetch = FetchType.LAZY) @JoinColumn(name = "manager_id") private Employee manager; @OneToMany( mappedBy = "parent", cascade = CascadeType.ALL, orphanRemoval = true ) private List<Employee> employees = new ArrayList<>(); }
Postgres 提供了一系列用于处理 ltree 的函数。您可以在官方文档页面中找到它们。此外,还有一个有用的备忘单。
为我们的模式添加约束以确保数据一致性非常重要 - 这是我在这个主题上找到的一个很好的资源。
最容易理解的是使用显示直觉的图像。在树的每个节点上,除了其 ID 之外,我们还有一个额外的“左”列和一个“右”列。规则是所有孩子的左值和右值都位于父母的左值和右值之间。
这是代表上面树的表结构。
return entityManager.createQuery(""" with employeeRoot as ( select employee.employees employee from Employee employee where employee.id = :employeeId union all select employee.employees employee from Employee employee join employeeRoot root ON employee = root.employee order by employee.id ) select new Employee( root.employee.id ) from employeeRoot root """, Employee.class ) .setParameter("employeeId", employeeId) .getResultList();
为了填充该表,我已将 Joe Celko 的“聪明人的 SQL”书中的脚本转换为 Postgres 语法。这是:
public class ClassImportIntegratorProvider implements IntegratorProvider { @Override public List<Integrator> getIntegrators() { return List.of( new ClassImportIntegrator( singletonList( Employee.class ) ) ); } }
好的,我准备好做一些查询了。这是找回祖先的方法。
@DynamicPropertySource static void registerPgProperties(DynamicPropertyRegistry registry) { registry.add("spring.jpa.show_sql", () -> true); }
对于后代,我们首先必须检索左和右,然后我们可以使用以下查询。
with recursive employeeRoot (employee_id) as ( select e1_0.id from employees eal1_0 join employees e1_0 on eal1_0.id = e1_0.manager_id where eal1_0.id=? union all ( select e2_0.id from employees eal2_0 join employeeRoot root1_0 on eal2_0.id = root1_0.employee_id join employees e2_0 on eal2_0.id = e2_0.manager_id order by eal2_0.id ) ) select root2_0.employee_id from employeeRoot root2_0
就是这样!您已经了解了如何通过所有三种方法在树上向上或向下移动。我希望您喜欢这次旅程并且发现它很有用。
我们在上面的示例中使用的数据库是PostgreSQL。它不是唯一的选择,例如,您可能想知道为什么不选择像 MongoDB 这样的文档数据库,或者像 Neo4j 这样的图形数据库,因为它们实际上是在考虑到这种类型的工作负载的情况下构建的。
很可能,您已经在 Postgres 中利用事务保证的关系模型中获得了真实数据源。在这种情况下,您应该首先检查 Postgres 本身处理辅助用例的情况,以便将所有内容都放在一个地方。这样,您将避免启动和维护/升级新的单独的专用数据存储所需的成本和操作复杂性增加,以及需要熟悉它。
有几个有趣的选项可用于在数据库应用程序中对分层数据进行建模。在这篇文章中,我向您展示了三种方法。请继续关注第 2 部分,我们将比较它们,并看看更大数据量会发生什么。
https://dev.to/yugabyte/learn-how-to-write-sql-recursive-cte-in-5-steps-3n88
https://vladmihalcea.com/hibernate-with-recursive-query/
https://vladmihalcea.com/dto-projection-jpa-query/
https://tudborg.com/posts/2022-02-04-postgres-hierarchical-data-with-ltree/
https://aregall.tech/hibernate-6-custom-functions#heading-implementing-a-custom-function
https://www.amazon.co.uk/Joe-Celkos-SQL-Smarties-Programming/dp/0128007613
https://madecurious.com/curiosities/trees-in-postgresql/
https://schinckel.net/2014/11/27/postgres-tree-shootout-part-2:-adjacency-list-using-ctes/
以上是使用 PostgreSQL 和 Spring Data JPA 的分层数据的详细内容。更多信息请关注PHP中文网其他相关文章!