Ключевые выводы

Асимптотика описывает, как растёт стоимость, а не из чего она состоит. Одинаковый O(1) у обращения по индексу массива и у поиска в распределённой таблице — разные счета: наносекунды против миллисекунд. O(n) по непрерывной памяти часто дешевле O(log n) по разбросанным узлам, пока n невелико.

Каждая структура покупает одни операции за счёт других. Массив инвестирует в локальность и дешёвый доступ. Связный список — в локальные вставки без массового сдвига. Хеш-таблица — в память ради быстрого поиска. Дерево — в порядок. Куча — в быстрый минимум или максимум без полной сортировки.

Единица анализа — не «структура», а профиль нагрузки. Соотношение чтений и записей, размер объектов, последовательность или случайность доступа, ограничения по памяти и допустимая задержка меняют победителя. Вопрос «какая структура быстрее?» почти всегда неполный.

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

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

Структура данных как экономическая система

Привычный взгляд на массив, связный список, хеш-таблицу, дерево и кучу сводится к свойствам и асимптотической сложности. Учебник честно отвечает на вопрос «как растёт число шагов при росте n». Он плохо отвечает на вопрос, который задаёт промышленный код: сколько это будет стоить на этой машине, при этих данных, при этом соотношении операций.

Альтернативная метафора — экономика. Любая структура делает одни операции дешевле, а другие дороже. Память, процессор, кэш, ввод-вывод и сеть — разные ресурсы с разной ценой. Структура данных — механизм перераспределения затрат: вы заранее решаете, за что платить постоянно и какие счета хотите закрыть дёшево в горячем пути.

Это не декоративное сравнение. Инженерный выбор — поиск приемлемого компромисса, а не абсолютного максимума производительности. Тот же взгляд уже работает на уровне качества: в экономике тестирования страховка покупается под размер ущерба, а не под площадь склада. Здесь страховка — лишняя память, служебные поля, балансировка, запас ёмкости.

Что именно мы называем стоимостью

Чтобы сравнивать структуры честно, нужна одна модель. Ниже шесть счетов. Они не заменяют асимптотику — они говорят, какие виды затрат асимптотика прячет в константе.

Стоимость хранения

Объём полезных данных — только часть счёта. Рядом живут служебные поля узла, указатели, заголовки объектов в управляемых языках, выравнивание и незанятая ёмкость динамического массива. Связный список из миллиона целых чисел в куче Java или Python легко занимает в несколько раз больше памяти, чем тот же набор в непрерывном буфере. «Низкая сложность вставки» уже куплена байтами, которых нет в учебниковой картинке из трёх прямоугольников.

Стоимость доступа

Поиск, чтение по индексу, поиск по ключу, последовательный обход и произвольный доступ — разные цены даже при одной записи O(1) или O(n). Последовательный проход по массиву кормит предварительную выборку и векторные инструкции. Произвольный прыжок по указателям кормит промахи кэша. Поиск по ключу в хеш-таблице добавляет вычисление хеша; в дереве — сравнения и спуски.

Стоимость изменения

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

Стоимость обслуживания

Увеличение ёмкости, перехеширование, балансировка, обновление индексов, поддержание инвариантов. Эти работы не видны в «среднем случае» одной операции, но они и есть скрытый налог структуры. Сбалансированное дерево продаёт гарантию O(log n) ценой постоянных вращений. Динамический массив продаёт дешёвый push ценой редкого полного копирования.

Стоимость перемещения

Копирование внутри оперативной памяти, промахи кэша, передача между уровнями иерархии памяти, ввод-вывод, передача по сети. На практике этот счёт чаще решает спор, чем число сравнений. Пока данные помещаются в кэш процессора, вы спорите о наносекундах. Когда они едут с диска или с другого узла, структура, которая экономит поездки, выигрывает у структуры с «лучшей» асимптотикой в оперативной памяти.

Стоимость синхронизации

Блокировки, атомарные операции, конкуренция за одну строку кэша, распределённые протоколы согласия. Структура, идеальная в одном потоке, может стать дорогой, как только к ней одновременно тянутся восемь ядер. Здесь экономика уже не про узлы и указатели, а про то, сколько потоков могут работать, не мешая друг другу.

Почему асимптотика — это не цена операции

Запись вида O(1) или O(n) (её часто называют Big-O) описывает рост числа шагов, а не счёт в наносекундах, байтах и поездках по памяти.

Одинаковый O(1), разная реальная стоимость

Обращение к элементу массива по индексу — арифметика адреса и, с высокой вероятностью, попадание в кэш. Поиск в хеш-таблице — хеш, доступ к корзине, возможно несколько сравнений при коллизии. Разыменование указателя — один переход, который может уехать в другую страницу. Поиск по ключу в базе на другом хосте тоже часто записывают как «константу с точки зрения клиента», хотя внутри — сеть, буферы, страницы. Все четыре сценария легко назвать O(1). Счета различаются на порядки.

O(n) не обязательно означает «плохо»

Линейный проход по непрерывной памяти — один из самых дешёвых способов обработать данные на современной машине. Локальность, предварительная выборка, векторные инструкции. Алгоритм, который «тупо» проходит миллион целых, часто обгоняет «умный» алгоритм с логарифмическим числом случайных прыжков. Это не отмена теории сложности. Это напоминание, что константа и характер доступа входят в цену.

Связанный практический слой — измерение, а не спор о буквах: в оптимизациях JavaScript сначала фиксируют исходный уровень, потом меняют код. Со структурами то же самое: спор «массив или дерево» без профиля нагрузки — спор о модели, а не о счёте.

O(log n) не всегда быстрее O(n)

Пока n — сотни или тысячи, логарифм от случайных переходов по указателям легко проигрывает линейному проходу. Каждый внутренний узел дерева — отдельный объект, часто в другой строке кэша. Сравнений меньше, поездок по памяти больше. Для маленьких словарей отсортированный массив с двоичным поиском нередко дешевле красно-чёрного дерева: меньше служебных данных, лучше локальность, предсказуемый обход.

Сложность как модель роста, экономика как модель цены

Асимптотика отвечает: как растёт стоимость. Экономика отвечает: из чего она складывается. Обе модели нужны. Первая спасает от структуры, которая взрывается на миллионах элементов. Вторая объясняет, почему на ваших десяти тысячах «худшая» структура быстрее и почему после переезда на диск победитель сменился.

Массив, связный список и хеш-таблица

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

Массив: платим за перемещение, покупаем локальность

Модель простая: непрерывный кусок памяти, индекс превращается в адрес. Дёшево — доступ по индексу, последовательный обход, итерация, обработка, дружественная к кэшу. Дорого — вставка и удаление в начале или середине, увеличение ёмкости, требование непрерывного блока.

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

Динамический массив добавляет ёмкость. Большинство добавлений в конец — запись в уже выделенное место. Иногда случается увеличение: выделить больший блок, скопировать всё, отдать старый. Средняя цена добавления остаётся низкой, разовая — высокой. Это не трюк учебника, а тот же принцип, что у пакетной записи на диск и у сборки мусора: редкий большой расход размазывается по множеству дешёвых шагов.

Связный список: платим за память и локальность, экономим сдвиг

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

Парадокс списка: теоретически дешёвая вставка, практически дорогая работа процессорного кэша. Локальная стоимость операции («два указателя») не равна системной стоимости («промах, промах, промах»). На машине 2020-х годов список редко выигрывает у массива в задачах, где учебник обещал победу, — именно потому, что учебник считал сравнения, а не поездки по иерархии памяти.

Хеш-таблица: инвестируем в память, чтобы удешевить поиск

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

Коэффициент заполнения — явный экономический регулятор. Слишком плотная таблица: больше коллизий, длиннее цепочки или пробы, выше ожидаемая цена поиска. Слишком редкая: больше пустых слотов, выше счёт за память и хуже плотность в кэше. Формула простая: больше памяти — меньше ожидаемая стоимость поиска, пока не начнёте вытеснять полезные данные из кэша и не упрётесь в перехеширование.

Дерево, куча, стек и очередь

Не все структуры оптимизируют «доступ к произвольному элементу». Часть из них покупает порядок, часть — одну дорогую операцию, часть — дешевизну за счёт запрета лишних действий.

Дерево: платим за структуру, покупаем порядок

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

Служебные данные узла и случайный доступ по указателям делают дерево дороже массива на единицу элемента. Локальность хуже: соседние в порядке ключей узлы редко лежат рядом в памяти. Сбалансированные деревья добавляют стоимость обслуживания — вращения и перекраски — чтобы держать гарантию O(log n). Гарантия не бесплатна: вы платите на каждой вставке, чтобы худший случай не превратился в линейный список.

Запросы по диапазону — момент, когда дополнительная структура становится экономически оправданной. Если нагрузка — точечный поиск по ключу, хеш-таблица обычно дешевле. Если нагрузка — «все события за час» или «все ключи от A до B», порядок окупает служебные поля и балансировку.

Куча: структура под одну дорогую операцию

Куча быстро отдаёт минимум или максимум. Вы жертвуете полным порядком и простотой произвольного доступа. Очередь с приоритетом — экономическая задача: незачем платить за полную сортировку, если системе регулярно нужен только следующий приоритетный элемент. Планировщик задач, обработка событий, алгоритм Дейкстры — типичные покупатели этой сделки.

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

Стек и очередь: дешёвая структура благодаря ограничению поведения

Стек разрешает узкий набор действий и дисциплину «последним пришёл — первым ушёл». Очередь — «первым пришёл — первым ушёл», дешёвое добавление с одного конца и извлечение с другого. Главная идея: ограничение возможностей уменьшает стоимость обслуживания. Чем меньше вариантов поведения нужно поддерживать, тем дешевле может быть структура.

Это звучит как трюизм из учебника, а на практике это архитектурный рычаг. Очередь задач дешевле универсального списка с вставками в середину. Стек вызовов дешевле произвольного графа активаций. Как только вы разрешаете «ещё одну удобную операцию», вы часто покупаете новый класс инвариантов и новый налог на каждое изменение.

Когда оперативная память уже не главный ресурс

B-дерево и внешний мир

Пока всё живёт в оперативной памяти, спорят о промахах кэша. Как только появляются диск, файловая система, база и сеть, единица стоимости меняется. Обращение к странице диска дороже сравнения ключей на порядки. Структура, которая минимизирует число таких обращений, побеждает структуру с «изящным» двоичным ветвлением.

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

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

Скрытая экономика памяти: кэш

Иерархия известна: регистры, кэш L1/L2/L3, оперативная память, накопитель, сеть. Временная локальность — повторно трогать недавно использованное. Пространственная — трогать соседей. Массив часто выигрывает у списка не из-за асимптотики, а из-за стоимости перемещения между уровнями этой лестницы.

Проектирование, ориентированное на данные, — практический вывод той же экономики: раскладка в памяти есть часть алгоритма. Структура из учебника, размазанная по мелким объектам в куче, может сохранить «правильную» сложность и потерять порядок по цене. Инженер, который меняет массив структур на структуру массивов, не занимается микрооптимизацией ради спорта — он меняет счёт за перемещение.

Практический сосед этой темы — кэш как отдельный слой системы: в разборе лавины запросов к кэшу в Node.js видно, как дешёвое чтение из кэша превращается в лавину, если не учесть стоимость согласованности и одновременных промахов. Экономика кэша — не «положили байты ближе», а покупка задержки ценой согласованности и памяти.

Нагрузка как настоящая единица анализа

Одна и та же структура — разные экономики. Набор из 99% чтений и 1% записей любит индекс, запас ёмкости, денормализацию. Соотношение 50/50 наказывает каждую структуру с дорогим обслуживанием. Частые вставки в начало уничтожают массив и делают осмысленным дек. Последовательный поток любит массив и кольцевой буфер. Случайный поиск по ключу любит хеш-таблицу.

Поэтому вопрос должен звучать не «какая структура быстрее?», а «какая структура дешевле для данного профиля нагрузки?».

Профиль нагрузки — экономический паспорт задачи. Его стоит выписать явно:

• частота операций каждого вида;
• размер набора и размер одного объекта;
• распределение запросов: равномерное, с горячим хвостом, с диапазонами;
• доля чтений и записей;
• требования к задержке (среднее против хвоста);
• потолок памяти.

Без этого паспорта выбор структуры — эстетика. С ним — расчёт. Тот же урок на уровне схемы базы: схема «сущность — атрибут — значение» кажется гибкой, пока профиль — редкие точечные поля; на отчётах и массовых чтениях экономика ломается, потому что вы купили гибкость записи ценой доступа.

Амортизированная стоимость и скрытая цена памяти

Почему увеличение ёмкости — хороший учебный пример

Большинство операций дешёвые. Иногда происходит дорогое копирование. Средняя цена низкая, худший случай высокий. Если ваш договор с системой — «почти всегда быстро, иногда можно подождать», амортизация работает. Если договор — «каждая операция укладывается в бюджет задержки», редкий пик — нарушение контракта, а не статистическая мелочь.

Амортизация — распределение крупного редкого расхода по множеству мелких регулярных платежей. В реальных системах тот же рисунок у пакетной обработки, буферизации, сборки мусора и уплотнения файлов журнала. Вы сознательно копите дешёвую грязь, чтобы один раз заплатить за порядок. Это выгодно, пока пауза обслуживания влезает в бюджет и пока объём «грязи» не начинает душить горячий путь.

Стоимость памяти — это не только количество байтов

Накладные расходы: указатели, заголовки объектов, выравнивание, фрагментация. Два миллиона мелких объектов могут «весить» больше, чем те же данные в двух крупных буферах, даже если сумма полезных полей одинакова.

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

Объём, который структура занимает в кэше: сколько полезной информации помещается в L1 и L2. Плотная таблица маленьких ключей вытесняет меньше полезного кода и данных, чем разреженная сетка объектов.

Сборка мусора — отдельный налог на обслуживание объектов. Структура, которая плодит короткоживущие узлы, платит не только выделением, но и работой сборщика. Иногда «неизменяемая» структура красива в коде и дорога в экономике пауз.

От структур данных к базам и распределённым системам

Экономические принципы не заканчиваются на массиве. Они поднимаются на уровень хранилища и кластера.

Индекс, денормализация, кэш, материализованное представление

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

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

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

Векторный индекс в промышленном поиске — ещё один портфель той же природы: память и обслуживание ради дешёвого приближённого поиска, см. векторные базы данных.

Когда появляется стоимость сети

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

Распределённая хеш-таблица, журнал на лидере, кэш на краю сети — всё это ответы на вопрос «какой ресурс мы готовы тратить, чтобы сделать дешёвой конкретную операцию». Принцип не меняется, меняется цена единицы перемещения.

Универсальная модель анализа

Перед выбором структуры полезно пройти один и тот же шаблон. Он одинаков для массива в процессе, индекса в PostgreSQL и шарда в кластере.

Хранение. Сколько памяти? Какой налог на служебные данные? Насколько эффективно используется ёмкость?

Доступ. Какие операции дешёвые? Какие дорогие? Какова локальность?

Изменение. Что происходит при вставке, удалении, обновлении? Нужен ли сдвиг, расщепление страницы, перехеширование?

Обслуживание. Что нужно постоянно поддерживать: баланс, коэффициент заполнения, актуальность индекса, компактность журнала?

Перемещение. Сколько данных реально едет между уровнями памяти, на диск, по сети?

Масштаб. Как меняется каждый счёт при росте N? Где кончается комфорт амортизации и начинается нарушение бюджета задержки?

Нагрузка. Для какого распределения операций структура выгодна? Что случится, если завтра доля записей вырастет с 1% до 30%?

Если на эти вопросы нет ответа, спор «массив или дерево» ещё не начался — не хватает входных данных. Если ответы есть, выбор обычно сужается до одной-двух структур, и остаётся измерить, а не угадать.

Карта экономик структур данных

Каждая структура делает инвестиции в разные ресурсы. Это удобно держать как портфель:

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

Читать таблицу стоит вместе с профилем нагрузки, а не вместо него. «Высокое хранение» у хеш-таблицы может быть лучшей сделкой в сервисе с миллионами точечных чтений. «Низкая локальность» списка может быть приемлема, если узлов мало и вставки в известную позицию — весь горячий путь.

Частые вопросы

Читать дальше

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

• Почему дешёвое тестирование обходится дорого — та же рамка инвестиций и цены отказа, только для качества
• JavaScript: 8 оптимизаций производительности — сначала измерение, потом правка; тот же отказ от спора без исходного уровня
• Оптимизация БД: шесть стратегий — индекс, материализованные представления и кэш как покупка дешёвого запроса
• Почему гибкая схема атрибутов ломает производительность учёта — гибкость схемы как дорогая структура доступа
• Как устроен современный веб: от браузера до базы — где в цепочке запроса сидит дорогое перемещение
• Векторные базы данных — индекс как портфель памяти и поиска на другом типе ключа
• Как убрать лавину запросов к кэшу — кэш как покупка задержки со своим налогом согласованности

Заключение

Вопрос «какую структуру данных мне выбрать?» стоит заменить на другой: какие ресурсы система готова тратить и какие операции должны стать дешёвыми?

Массив, список, таблица, дерево, куча, B-дерево — не персонажи рейтинга. Это разные ответы на один и тот же экономический запрос. Проектирование структуры данных — управление стоимостью движения и преобразования информации. Сначала паспорт нагрузки и шесть счетов, потом учебниковая буква O, потом измерение на своих данных.

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

Возможное продолжение серии «Экономика вычислений»: экономика алгоритмов; экономика памяти и процессорного кэша; экономика баз и индексов; экономика распределённых систем; экономика задержки; экономика масштабирования; и отдельный разбор, почему оптимизация одного ресурса часто увеличивает стоимость другого. Эта статья закрывает первый слой — структуру как портфель, а не как строку справочника.