Ява: очень большие деревья?

Question

Цель - построить очень большие деревья. Под очень большим я подразумеваю сотни миллионов узлов, умещающихся в несколько гигабайт.

Проблема в том, что обычные структуры данных имеют слишком много накладных расходов. Я не могу позволить себе иметь "нодовые" объекты и дочерние "карты". Мне нужно напрямую закодировать его в память очень компактным способом.

Поэтому мне было интересно, существует ли некая эффективная для памяти реализация деревьев, имеющих целые числа в качестве ключа и значения, без внутреннего использования объектов, поэтому требуется (4 байта для ключа + 4 байта для значения + 4 байта для дочернего индекса + несколько байт для свободного пространства хеширования (в среднем 15 байт на запись), что позволило бы мне использовать внешние сопоставления int <-> keys и int <-> значения для поиска в дереве.

Любой

PS: при внутреннем использовании объектов используется как минимум в 5 раз больше места: 8 ссылок + 4 дополнительных хеш-пространства + 16 заголовков объектов + 8 ключей ref + 8 значений ref + 8 родительских ссылок + 8 дочерних ссылок + (16 + x) для дети отображают obj = почти 76 + x байт на запись. (например, нашей реализации по умолчанию требовалось около 100 байт на запись)

Answer 1

Это на самом деле не специфический для Java вопрос, а скорее общая концепция.

Попробуйте это: http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

Ключ будет заключаться в использовании массивов примитивов, чтобы избежать объектанакладные расходы.

Answer 2

Я не знаю какой-либо конкретной реализации дерева, которая делает именно это, но VTD-XML представляет собой дерево XML (DOM) внутри, используя массив токенов с указателями на буфер.Возможно, вас вдохновит их решение?

Answer 3

Я не думаю, что вы найдете что-то уже реализованное для вас, но то, что вы описали, может быть очень легко реализовано с помощью IntBuffer .Вы бы создали класс «обертка», который преобразует индексы в записи в буфере, и создаете / отбрасываете эти обертки по мере необходимости (т. Е. При обходе дерева вас, вероятно, не волнуетсодержит ссылку на родителя).

Существует несколько проблем:

• Сборка мусора экземпляров оболочки: пока они недолговечны, они никогда не получатвне Eden, поэтому GC почти бесплатен.
• Сборка мусора записей в буфере: если у вас есть дерево с однократной записью, это не проблема.В противном случае вам нужно будет поддерживать свободный список.Не сложно, но это занимает некоторое время.
• Общая механика реализации дерева: это уже сделано для вас с такими классами, как TreeMap.Но алгоритмы довольно просты и доступны из Википедии .

Answer 4

Вы можете обнаружить, что эта библиотека помогает вам достичь того, чего вы хотите - она ​​специально разработана для хранения значений в качестве примитивов и выполняет некоторые байт-коды за кулисами, чтобы создать иллюзию хранения объектов.Используйте его, когда ...

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

У него нет определенной коллекции дерева, но он может добиться цели, в зависимости от того, что вам нужно.

http://code.google.com/p/vanilla-java/wiki/HugeCollections

Answer 5

Вместо хранения списка дочерних элементов каждый узел может иметь ссылку на своего родителя.Таким образом, для сериализации узла не потребуется более трех целочисленных значений (родитель, ключ, значение).

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