如何在关系数据库中存储子项的链接树？

Question

我有一个带有子节点(节点)的自定义LinkedTree,节点具有邻接关系,即每个节点与上一个节点和下一个节点链接.这个LinkedTree非常重,很大,可能包含数百万个节点.

这是一个代码示例:

package tree;

import java.io.Serializable;

public class LinkedTree<E> implements Serializable {

    private int size = 0;
    private Node<E> first;
    private Node<E> last;
    private LinkedTree<E> children;

    public LinkedTree() {
        children = new LinkedTree<>();
    }

    public LinkedTree(LinkedTree<E> children) {
        this.children = children;
    }

    public void add(E element) {

        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, element, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
    }

    public void remove(E element) {

        ...
    }

    public int size() {

         return size;
    }

    public static class Node<E> implements Serializable {

        E item;
        Node<E> next;
        Node<E> prev;

        public Node(Node<E> prev, E item, Node<E> next) {

            this.item = item;
            this.next = next;
            this.prev = prev;
        }

        public E item() {

            return item;
        }

        public boolean hasPrevious() {

            return prev != null;
        }

        public Node<E> previous() {

            return prev;
        }

        public Node<E> previous(int target) {

            Node<E> n = this;
            int i = target;
            while (i-- > 0 && n != null)
                n = n.prev;
            return n;
        }

        public boolean hasNext() {

            return next != null;
        }

        public Node<E> next() {

            return next;
        }

        public E nextItem() {

            return next.item;
        }

        public E nextItem(int target) {

            return next(target).item();
        }

        public Node<E> next(int target) {

            Node<E> n = this;
            int i = 0;
            while (i++ < target && n != null)
                n = n.next;
            return n;
        }

        @Override
        public int hashCode() {

            return item != null ? item.hashCode() : 0;
        }

        @Override
        public boolean equals(Object o) {

            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;

            Node<?> node = (Node<?>) o;

            return item != null ? item.equals(node.item) : node.item == null;
        }

        @Override
        public String toString() {

            return item.toString();
        }
    }
}

我想序列化它并将其保存在文件中以使其持久化,但加载和写入一些数据可能成本太高.所以我决定把它保存在MySQL中,以便我可以从任何我想要的地方加载数据.我的意思是从这个层次结构的结尾,中间或开始.

我想这行的关系应该是相邻的和亲子关系.但我不知道该怎么做.

Answer 1

我会评论要求更多信息（特别是示例数据和层次结构的规则），所以请原谅这第一次剪辑过于笼统

我做了以下假设：

• 你的结构深度超过三层 - 如果不是这种情况那么我不会这样做，因为它不值得

• 您的负载是读取繁重的，并且对树的各个部分的写入是并发的但不冲突，而冲突的写入很少或不存在

• 你不需要对树进行并行、部分和无共享或无锁访问来构建或处理它（在这种情况下，你需要发信号deletes，你可以通过指向你替换的节点来完成，即取代）

我提出的数据模型看起来像：

create table treemodel (
 `node` int not null 
 , `parent` int not null 
 , `principal` int not null 
 , `state` smallint unsigned not null 
 , ...
 , `supersedes` int    /*version instead of lossy update or delete*/
 , `supersededby` int
) engine = innodb;
alter table treemodel add primary key (`principal`, `node`) using btree; 

1. 树模型表仅保存结构标识符：我将节点数据保存在一个单独的表中，但我不会加入来获取它，相反，我会执行第二个select ... where node in (...)- 这基本上是说“我的数据的结构独立于我的数据'

2. 该模型旨在限制到数据库的往返次数，可能看起来违反直觉，但允许您在单个数据库指令中读取或锁定树的部分内容，而无需连接

3. 这将与您的数据模型相反，因为您不会将额外的“主要”节点与嵌套子节点一起存储 - 但如果您可以更改此结构，那么您可以利用此建议来避免循环内的查询，即。多重selects或可重入查询或自/一元连接

4. ...但是您的业务逻辑需要支持我所说的“主要”节点的概念

5. 主要节点中放入的内容取决于您的用例 - 我已使用此模型来存储观察记录及其派生之间的因果关系，而不管此点以下的父子关系如何 - 另一个示例可能是：1）客户提出支持案例，或 2) 发送新消息，或 3) 创建新文件，...

6. 将主体存储为树结构中的实际根节点（即节点 id '1' 或 '数据目录' 或其他）是没有意义的 - 相反，为了论证，您将存储 '下一级' ， IE。“用户根目录”或“用户根目录下的第一级” - 这是了解您的用例和业务规则将有所帮助的地方

7. insert...并且您的java代码将需要更新以查找或复制并存储这个概念 - 它将始终是树的给定分支内任何父节点的副本- 如果您正在移动分支并且您的逻辑需要改变这个数字，它是一个update ... set principal=y where principal=x和update ... set parent=newid where node=current_principal

8. ...话虽如此，我不会更新行本身，只会insert在更改和重新创建整个树枝时（这解释了该state字段，即CURRENT，，，DELETED...其中已删除分支的根节点仍然指向其当前的父节点，例如“已删除的项目”）

9. 您仍然保留指向 prev 和 next 中每个相邻节点的指针 - 在最坏的情况下，将节点有序插入到树的分支中将需要 a select ... where principal=x for update，但可能只需要 aselect ... where (node=x or prev=x or next=x) for update

编辑：

• 主键/聚集索引必须是唯一的 - 您也可以分区principal以确保快速并行访问

• 重新创建而不是更新分支