Зачем хранить дерево как непрерывный кусок памяти?

Хранение структур данных в непрерывной памяти — это метод, используемый в системах с ограниченным объемом памяти, таких как встроенные системы. Техника также может использоваться в системах, важных для безопасности и производительности.

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

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

Процесс распределения быстрее с использованием смежной системы. Вы знаете, где находятся блоки. Кроме того, вместо хранения указателей для ссылки, значения индекса могут быть сохранены. Это также позволяет хранить дерево в файле и легко извлекать его.

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

Помните, что единственный способ узнать о проблемах производительности — это профиль.

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

Одна очень простая версия состоит в том, чтобы просто выделить блоки из трех, родительского и двух дочерних блоков, и этот блок имеет четыре «дочерних» блока, по два для каждого дочернего элемента. Это сокращает ваши ассигнования на треть. Это не так уж много для оптимизации, пока вы не увеличите ее, выделив 7, 15, 31, 63 … если вы сможете получить так, чтобы как можно больше ключей помещалось на одной странице системы памяти, то вы минимизируете время, проведенное в ожидании жесткого диска. Если каждый из ваших ключей занимает 32 байта, а страница имеет размер 4 КБ, то вы можете сохранить до 125 ключей, что означает, что вам нужно всего лишь загрузить одну страницу с жесткого диска для каждых 7 строк дерева. В этот момент вы загружаете «дочернюю» страницу, а затем следуете еще 7 строк. Обычное двоичное дерево может иметь только один узел на страницу, что означает, что вы тратите в 7 раз больше времени, просто ожидая жесткого диска, чем итерируете дерево. Довольно медленно Повороты немного сложнее, так как вам нужно поменять местами данные, а не указатели, как это обычно бывает в древовидных реализациях. Кроме того, у него есть пустая трата использовать много места, когда дерево становится больше.

               ---------
|   O   |
|  / \  |
| O   O |
_---------_
__/    \ /    \__
/       | |       \
--------- --------- --------- ---------
|   O   | |   O   | |   O   | |   O   |
|  / \  | |  / \  | |  / \  | |  / \  |
| O   O | | O   O | | O   O | | O   O |
--------- --------- --------- ---------

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

Другой очень простой вариант — поместить все дерево в массив, доступ к которому осуществляется через индексы, что экономит общую память, но только верхняя часть является дружественной к кешу, более низкие уровни хуже кешировать мудрее обычного двоичного дерева. По сути, корень имеет индекс i = 0, а левый потомок — (n*2+1 = 1), и правильный ребенок находится в (n*2+2 = 2). Если мы находимся в узле с индексом 24, его родитель ((n-1)/2 = 12), и это левый и правый дети 49 и 50 соответственно. Это прекрасно работает для небольших деревьев, поскольку не требует никаких дополнительных затрат для указателей. Данные хранятся в виде непрерывного массива значений, а отношения выводятся индексом. Кроме того, добавление и удаление дочерних элементов всегда происходит рядом с правым концом, и применяется обычная вставка / вращение / стирание двоичного дерева. У них также есть интересная математическая новинка: если вы конвертируете индекс плюс один в двоичный, это соответствует местоположению в дереве. Если мы думаем об узле с индексом 24, 24 + 1 в двоичном виде — это 11001 -> Первая 1 всегда означает корень, и оттуда каждая 1 означает «идти направо», а каждый 0 означает «идти налево», что означает чтобы добраться до индекса 24 от корня, вы идете направо, налево, налево, направо, и вы там. Кроме того, поскольку есть 5 двоичных цифр, вы знаете, что это в пятой строке. Ни одно из этих наблюдений не особенно полезно, за исключением того, что они как бы подразумевают, что корневой узел является правильным потомком, что является неопределенно интересным. (Если вы расширяетесь на другие базы, корень всегда самый правый дочерний элемент). Тем не менее, по-прежнему часто полезно реализовать корень как левый узел, если вы работаете с двунаправленными итераторами.

     0
/ \
/   \
1     2
/ \   / \
3   4 5   6

[0][1][2][3][4][5][6]

как вы убедитесь, что вы реорганизуете ветви и листья
значимым образом, что помогает производительности?

Если у вас уже запущена программа (с несмежным деревом), вы всегда можете просто настроить свою программу, чтобы сообщить, как обычно выглядят ее фактические шаблоны доступа к узлам. Как только вы получите представление о том, как осуществляется доступ к узлам, вы можете настроить распределитель узлов таким образом, чтобы он размещал узлы в памяти в том же порядке.

«… попробуйте« линеаризовать »дерево, чтобы сохранить его в виде вектора / массива, чтобы убедиться, что вы реорганизуете ветви и листья осмысленным образом, который помогает производительности …»

Я верю, что ты слишком много думаешь.

В обычном дереве вы используете ‘new’, чтобы запросить свободное место, в котором можно создать узел.

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

Затем подключите узлы с помощью указателей.

Для «дерева в векторе» вы могли бы просто заново реализовать новое и удалить, чтобы найти пространство в векторе.

Я думаю, что вместо указателей (для родительского или левого или правого узла) вы используете индекс (для родительского или левого или правого узла).

Я считаю, что индекс n-го элемента в векторе (как до, так и после перераспределения для роста) остается неизменным.

Другой проблемой является удаление узла … но это может быть так же просто, как любой узел (или индекс) больше, чем стертый узел, уменьшается на 1.

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

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

Важно различать дерево и AVL дерево. В своем вопросе вы говорите о балансируя дерево так что ваш вопрос, вероятно, о представлении дерева AVL в массиве.

Все остальные ответы говорят о дереве, а не о дереве AVL. Насколько я знаю, этот вид дерева может быть представлен в массиве, но не может быть эффективно обновлен, так как вам нужно переупорядочить многие элементы массива вместо того, чтобы играть с указателями памяти.

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

Мой вывод будет:

• доступное только для чтения дерево с большим доступом => в массиве
• обновляемое дерево с большим количеством изменений => в памяти