树如何存储在数据库中？

Question

如果要使用像C#这样的4GL实现树,并将其存储在数据库(如SQL Server 2008)中,那么架构/设计会是什么样子？

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

Answer 1

储存树

有几种选择：

1. 毕竟，它只是一棵树，因此您可以像存储其他任何树一样来存储它（基本上是通过递归FOREIGN KEY）。
2. 或者，转换后缀树为后缀阵列和存储即到数据库中。
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中（或根本不存储它而仅存储目标字符串），那么显然您将无法直接在数据库中访问它（无论如何效率不高）-您唯一的选项是将其加载（或重新创建）到内存中。