Ключові висновки

Асимптотика описує, як зростає вартість, а не з чого вона складається. Однаковий 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%?

Якщо на ці питання немає відповіді, суперечка «масив чи дерево» ще не почалася — не вистачає вхідних даних. Якщо відповіді є, вибір зазвичай звужується до однієї-двох структур, і лишається виміряти, а не вгадати.

Карта економік структур даних

Кожна структура робить інвестиції в різні ресурси. Це зручно тримати як портфель:

Порівняльна карта нижче — концептуальна, не таблиця істини для всіх реалізацій. Точні значення залежать від мови, розподільника пам'яті, коефіцієнта заповнення і середовища виконання.

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

Часті питання

Чи є найшвидша структура даних?

Ні. Є структура, найдешевша для цього профілю навантаження і цього набору ресурсів. Без розподілу операцій питання не має відповіді.

Чому масив часто швидший за зв'язаний список при тій самій асимптотиці вставки «в середину»?

Бо «в середину за константу» у списку вимагає вже знайденого вузла, а обхід списку б'є по кешу. Масив зсуває байти, але робить це послідовно, і процесор це любить. На реальних розмірах локальність часто переважує число теоретичних кроків.

Коли геш-таблиця гірша за дерево?

Коли потрібен порядок, діапазони, найближчий ключ або передбачуваний найгірший випадок. Також коли пам'ять тісна: порожні кошики і перегешування можуть коштувати дорожче за спуски по щільному дереву. Для крихітних словників часто виграє відсортований масив.

Чому B-дерево не використовують скрізь замість двійкового дерева?

В оперативній пам'яті великий вузол і складне галуження не дають того виграшу, що на диску: порівняння дешеві, поїздка до «сторінки» майже безкоштовна. B-дерево окупається, коли одиниця переміщення — блок сховища. Всередині процесу зазвичай вигідніші структури, дружні до рядка кешу.

Що таке амортизована вартість простими словами?

Це середня ціна операції, якщо дорогий випадок трапляється рідко і його можна розмазати по множині дешевих. Збільшення масиву вдвічі — класика. Не плутайте зі «завжди швидко»: хвіст розподілу може порушувати бюджет затримки, навіть якщо середнє красиве.

Як обрати структуру за п'ятнадцять хвилин?

Виписати профіль: частки операцій, розмір N, розмір елемента, обмеження пам'яті, бюджет затримки. Прогнати сім питань шаблону. Відсікти структури, які роблять гарячий шлях дорогим. Виміряти двох фіналістів на типових даних. Не починати з «як у підручнику на співбесіді».

Чи пов'язана економіка структур із вибором бази даних?

Так, це один контур. Індекс, денормалізація, реплікація — ті самі інвестиції на іншому масштабі. Якщо ви вже думаєте про структури як про портфель, перехід до схеми сховища не потребує нової релігії — лише нових цін на переміщення.

Чим ця рамка відрізняється від «просто подивіться асимптотику»?

Асимптотика лишається фільтром від катастроф на зростанні N. Економіка додає склад ціни, ієрархію пам'яті і профіль навантаження. Разом вони відповідають і «чи не вибухне», і «чи не розорить на вашому залізі й вашому трафіку».

Читати далі

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

• Чому дешеве тестування обходиться дорого — та сама рамка інвестицій і ціни відмови, лише для якості
• JavaScript: 8 оптимізацій продуктивності — спочатку вимірювання, потім правка; та сама відмова від суперечки без вихідного рівня
• Оптимізація БД: шість стратегій — індекс, матеріалізовані представлення і кеш як купівля дешевого запиту
• Чому гнучка схема атрибутів ламає продуктивність обліку — гнучкість схеми як дорога структура доступу
• Як влаштований сучасний веб: від браузера до бази — де в ланцюжку запиту сидить дороге переміщення
• Векторні бази даних — індекс як портфель пам'яті і пошуку на іншому типі ключа
• Як прибрати лавину запитів до кешу — кеш як купівля затримки зі своїм податком узгодженості

Висновок

Питання «яку структуру даних мені обрати?» варто замінити на інше: які ресурси система готова витрачати і які операції мають стати дешевими?

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

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

Можливе продовження серії «Економіка обчислень»: економіка алгоритмів; економіка пам'яті і процесорного кешу; економіка баз і індексів; економіка розподілених систем; економіка затримки; економіка масштабування; і окремий розбір, чому оптимізація одного ресурсу часто збільшує вартість іншого. Ця стаття закриває перший шар — структуру як портфель, а не як рядок довідника.