Что такое быстрое, компактное представление древовидных структур, предотвращающее промахи кеша?

Question

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

dimensional_array = [[1,2],[3,4],[4,5]] 
four = dimensional_array[1,1] 

flat_array = [1,2,3,4,5,6] 
four = flat_array[1 + 2*1] 

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

free_form_tree = [[1,2,3],4,5,[[6,7],8]] 

Answer 1

Вы можете прочитать на B-trees.

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

Вы можете посмотреть больше на Google, используя этот вопрос: «Cache не обращая внимания дерево», чтобы получить больше ссылок, таких как this

Answer 2

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

• корень имеет индекс 0
• Дети всегда с индексами (2 * я + 1) и (2 * я + 2), где я это текущий индекс.
• Их родителем является пол ((i - 1)/2), где i - индекс ребенка.

Storing binary tree as an array.

Также см. Подробности кучи here.

Answer 3

Вы можете использовать представление постображения или perorder для дерева вместе с представлением в виде рамки, но затем, если есть изменение в дереве, тогда вы перепродаете тогда в O (n), который является дорогостоящим для небольшой скорости. Другие реализации, такие как B-tree или предварительная гибридная структура данных, сложны для реализации и не достойны вашего времени для относительно небольшой скорости. Поскольку все операции в дереве - это O (logn) для сбалансированного дерева, поэтому кеш может только ускорить некоторый постоянный коэффициент, который незначителен по сравнению с O (logN)