c# - 一棵树如何存储在数据库中？

Question

如果要使用 C# 之类的 4GL 实现一棵树，并将其存储在 SQL Server 2008 等数据库中，架构/设计会是什么样子？

换句话说，数据库在这样的实现中扮演什么角色？

Answer 1

存储树

有几个选项:

1. 毕竟它只是一棵树，所以您可以像存储任何其他树一样存储它(主要是通过递归 FOREIGN KEY)。
2. 或者，将后缀树转换成suffix array并将那个存储到数据库中。
3. 或者，您可以将其序列化为(比如)XML，然后将其存储到单个 CLOB。
4. 或者，由于后缀树大约是其索引的“目标”字符串的 20 倍，您可以简单地存储字符串并根据需要计算后缀树(例如使用 Ukkonen 算法)。

注意:对于后缀数组，您不会存储任何字符，您只需存储描述每个元素的索引，如下所示:

CREATE TABLE SUFFIX_ARRAY (
    ORDER INT PRIMARY KEY, -- Position in the suffix array.
    START INT NOT NULL, -- Position of the starting character of the suffix within the target string.
    LONGEST_COMMON_PREFIX INT NOT NULL -- If useful for your application.
)

您还必须单独存储“目标”字符串(例如，在另一个表的 CLOB 中)。

使用树

1. 如果直接存储后缀树，应该可以直接用SQL搜索。
2. 如果您将它存储为后缀数组，您将不得不花点时间通过 SQL 实现二进制搜索，但应该是可能的。
3. (和 4)如果你将它存储在 CLOB 中(或者根本不存储它而只存储目标字符串)，那么显然你将无法直接在数据库中访问它(无论如何效率不高) - 你唯一的选择是在内存中加载(或重新创建)它。