0

表示如下关系的正确数据结构是什么？例如，我是否更好地将其表示为一棵树？如果是这样，那三个人会是什么样子？我的目标是让 A 类的实例在内存中具有最佳的内存足迹，并快速插入到任何级别的嵌套。

每个嵌套字典云都有数百万个项目，E 类的大小可以约为每个类 10MB。

    public class A
    {
        private Dictionary<int, B> someName;
    }

    public class B
    {
        private Dictionary<int, C> someName;
    }

    public class C
    {
        private Dictionary<int, D> someName;
    }

    public class D
    {
        private Dictionary<int, E> someName;
    }

    public class E
    {
           //10 Mb worth of properties
    }
4

1 回答 1

1

外部存储器上有许多算法和数据结构，由于您的数据量非常大，因此可能包含您想要的内容。

当我们处理外部内存问题时，我们通常使用每个操作的 I/O 来评估数据结构的有效性。

输入输出模型

您正在考虑将其表示为一棵树，我认为这是一个有前途的解决方案。基本上，我们需要一个搜索树，类似于 B 树。更具体地说，外部存储器上的平衡 B 树。

我认为你可以使用权重平衡的 B-tree，它是 B-tree 和 BB[α]-tree 的组合，来解决这个问题。

具有参数 b 和 k(b>8,k≥8) 的权重平衡 B-tree 具有以下约束：

  1. 所有叶子都在同一级别，并且包含 k/4 到 k 个元素。

  2. 级别 l 的内部节点 v 具有 w(v) < b^l * k。

  3. 除根外，第 l 层的内部节点 v 的 w(v)> 1/4 * b^l * k。

  4. 根有多个孩子。

我们可以推断内部节点度在 (1/4 * b^l * k) / (b^l*k) = 1/4b 和 (b^l * k) / (1/4 * b^l- 1 * k) = 4b。

具有分支参数 b 和叶参数 k=Ω(B) 的权重平衡 B 树具有以下属性：

权重平衡的 B 树

  1. 空格：O(N/B)
  2. 高度：O(log(b, N/k))
  3. O(log(b, N)) 更新后的重新平衡操作

证明不是很复杂，可以在Lars Arge编写的External Memory Geometric Data Structures中看到。关于外部存储器数据结构的笔记非常好，我强烈推荐你阅读。您可以从阅读 L.Arge 的一些讲义开始，它可以快速帮助您理解这种数据结构并做出决定。

于 2013-02-14T10:42:49.053 回答