правильная структура данных для вложенных хэшей

Question

Какова правильная структура данных для представления отношений, как показано ниже? Я лучше представляю это как дерево вместо, например? Если да, то как будут выглядеть эти три? Моя цель состоит в том, чтобы иметь экземпляры класса A в памяти с наилучшей печатью стопы памяти, а также быстрые вставки на любой уровень гнезда.

Каждое облако вложенных словарей имеет несколько миллионов элементов, а размер класса E может составлять около 10 МБ на класс.

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 
    } 

Answer 1

Есть много алгоритмов и datastructures на внешней памяти, которые могут содержать то, что вы хотите, так как ваш размер данных очень велик.

Мы обычно используем операции ввода/вывода для каждой операции для оценки эффективности структуры данных, когда мы имеем дело с проблемами внешней памяти.

Вы думаете о представляя это как дерево, которое, я думаю, является перспективным решением. В принципе, нам нужно дерево поиска, что-то вроде B-дерева. Более конкретно, сбалансированное B-дерево во внешней памяти.

Я думаю, вы можете использовать сбалансированное по весу B-дерево, которое представляет собой комбинацию B-дерева и BB [α] -tree, для решения этой проблемы.

Вес сбалансированный В-дерева с параметрами б и к (б> 8, k≥8) имеет следующие ограничения:

1. Все листья на одном уровне и содержат от 4 к/к и элементы.

2. Внутренний узел v на уровне l имеет w (v) < b^l * k.

3. За исключением корня, внутренний узел v на уровне l имеет w (v)> 1/4 * b^l * k.

4. Корень имеет более одного ребенка.

Мы можем сделать вывод, что степень внутреннего узла находятся между (1/4 * б^л * к)/(б^л * к) = 1/4b и (б^л * к)/(1/4 * b^l-1 * k) = 4b.

Тяжесть сбалансированный В-дерева с разветвлением параметра б и параметр листа к = Ω (В) имеет следующие свойства:

1. Площадь: O (N/B)
2. Высота: O (журнал (б, п/к))
3. O (журнал (B, N)) Перебалансирование операции после обновления

доказательство не очень сложно и можно увидеть в External Memory Geometric Data Structures, написанном Lars Arge. Замечания по внешним файлам данных внешней памяти очень хорошие, и я настоятельно рекомендую вам прочитать. Вы можете начать с чтения некоторых из lecture notes L.Arge, которые могут быстро помочь вам понять эту структуру данных и принять ваше решение.