Дерево, которое эффективно и для памяти, и для дискового пространства?

Question

Я недавно начал читать о структурах данных в деталях. Я наткнулся на деревья. Деревья AVL спроектированы с учетом быстрого доступа к памяти, а деревья B спроектированы с учетом эффективного хранения на диске. Предположим, я хочу создать дерево, которое будет эффективно использовать память и дисковое хранилище. Какое дерево мне следует использовать? Есть ли способ объединить дерево AVL и дерево B? Есть ли другое дерево, которое может сделать и то и другое? Это принципиально возможно в реальном сценарии?

Answer 1

Я хочу спроектировать дерево, которое будет эффективно использовать память и дисковое хранилище (...) Есть ли способ объединить дерево AVL и дерево B?

Краткий ответ нет, нет, если вы не сделаете прорыв в области структур данных. Оба они были разработаны с учетом конкретных c требований к оптимизации, вы не можете иметь лучшее из обоих миров.

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

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