Структура даних (Data Structure)
Спеціалізований формат для організації, обробки, пошуку та зберігання даних у пам'яті комп'ютера.
У Web3 критично важливими є спеціалізовані структури, такі як дерева Меркла (Merkle Trees) та Patricia Tries. Вони дозволяють вузлам імовірнісно перевіряти наявність транзакції в блоці за час O(log N) без завантаження всього блокчейну.
graph LR
Center["Структура даних (Data Structure)"]:::main
Rel_tree["tree"]:::related -.-> Center
click Rel_tree "/terms/tree"
Rel_data_type["data-type"]:::related -.-> Center
click Rel_data_type "/terms/data-type"
Rel_merkle_patricia_trie["merkle-patricia-trie"]:::related -.-> Center
click Rel_merkle_patricia_trie "/terms/merkle-patricia-trie"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧠 Перевірка знань
🧒 Простими словами
Уявіть, що у вас є 100 інструментів. Якщо кинути їх у мішок, пошук викрутки займе багато часу. Але якщо розкласти їх у ящик з відділеннями для молотків, викруток та ключів — ви знайдете потрібне миттєво. Структура даних — це такий 'ящик' у пам'яті комп'ютера, який тримає дані в порядку, щоб знаходити їх якомога швидше.
🤓 Expert Deep Dive
ADT (Абстрактні типи даних) проти Структур даних: ADT — це математична модель (наприклад, Стек — LIFO), а структура даних — це її реалізація (Стек на базі Масиву або Зв'язаного списку). Розподіл пам'яті: Масиви використовують безперервну (contiguous) пам'ять, що дає O(1) для доступу через арифметику вказівників, але O(N) для вставки. Зв'язані списки використовують вказівники на розкидані вузли, що дає O(1) для вставки, але O(N) для доступу через промахи кешу (cache misses).
❓ Часті питання
Why are there so many different data structures?
Because different tasks require different optimizations. If you need to search data quickly, you might use a Hash Table. If you need to keep data in a sorted hierarchy, you use a Tree. There is no single 'best' structure for everything.
What is the difference between an Array and a Linked List?
An array stores items next to each other in memory, making it very fast to jump to a specific item. A linked list stores items wherever there is free space, and each item points to the next one, making it fast to add or remove items without shifting everything else.
What is a Merkle Tree in crypto?
A Merkle Tree is a cryptographic data structure used in blockchains. It allows computers to quickly verify that a specific transaction exists in a block without having to download all the data in the block.