В чем разница по памяти между бинарным поиском и поиском по деревьям

Что проверяют

Интервьюер хочет услышать не только асимптотику, но и то, как данные лежат в памяти и что с ними делает рантайм Go. Следом обычно спрашивают, что выбрать для набора, который часто меняется.

Как отвечать

Сравнивайте по четырём осям:

• хранение: бинарный поиск работает по отсортированному слайсу, это O(n) без накладных расходов, для []int64 ровно 8 байт на элемент. Узел struct{ key int64; left, right *Node } занимает 24 байта, втрое больше, а у красно-чёрного или AVL-дерева добавляется цвет или высота. К тому же каждый узел это отдельная аллокация в куче;
• память на поиск: итеративный бинарный поиск и итеративный спуск по дереву требуют O(1). Рекурсивные версии тратят O(log n) и O(h) стека, а у вырожденного дерева h равно n. Хвостовую рекурсию компилятор Go не оптимизирует;
• локальность: слайс лежит одним куском, и на поздних итерациях шаги поиска попадают в одни кеш-линии. В дереве каждый шаг это переход по указателю в случайное место памяти и почти гарантированный промах кеша;
• GC: массив без указателей сборщик мусора не сканирует. Дерево из миллиона узлов это миллион объектов с указателями, которые GC обходит на каждом цикле, и это видно по загрузке CPU.

В коде это slices.BinarySearch или sort.Search. Цена слайса в изменениях: вставка в середину сдвигает хвост, O(n). Дерево вставляет за O(log n), поэтому для часто меняющегося упорядоченного набора берут дерево. Сбалансированного дерева в стандартной библиотеке нет, а компромиссом служит B-дерево, например github.com/google/btree: много ключей в узле, меньше указателей, лучше работа с кешем.

Где спотыкаются

Отвечают «оба O(log n)» и останавливаются, хотя вопрос про память, а не про время.

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

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