← all systems · see it in The System
Data structure
In computer science, a data structure is a way to organize and store data that is usually chosen for efficient access to data; more precisely, the physical implementation of a data type: the data's organization and storage format together with the operations for working with it.
Properties published scienceour proposal
Sourced fields, and our own readings.
| born at | 1945 (von Neumann's array-sorting program for EDVAC) |
| born precision | year; older human orderings contested (C-2262) |
| boundary | Inside: the layout of data in memory (contiguous cells or linked nodes holding addresses), the invariants the layout keeps (sorted order, balance, the heap property, a load-factor bound) and the operations that maintain them (insert, delete, find, traverse). Outside: the program that calls it, the abstract data type it implements (the user's view), the memory hardware it lives on, and the people and systems that use the answers. |
| nested level | Built from memory words and addresses (the word-RAM's cells); a part of every program and of software libraries; implements abstract data types; studied by computer science; underlies databases, file systems, compilers, search engines and genome aligners. |
| scale | technological |
Measures (18) published science
| characteristic clock: one operation (find, add, remove) in O(1) to O(log n) word steps; an amortized constant number of B-tree splits per insertion | O(1) splits per insertion (amortized) |
| amortized B-tree splits per insertion | constant splits |
| RAM against disk access time | RAM > 2,500x faster than SSD, > 160,000x faster than hard disk (19 ms HDD, 0.3 ms SSD, < 0.000113 ms RAM) ratio |
| hash-table lookup cost | independent of the number of elements (average, well-dimensioned table) time |
| linear-probing table at most half full | t.length >= 2q slots |
| open addressing maximum load factor | 0.6 to 0.75 elements per slot |
| wasted space lower bound for a growing list | about the square root of n words, at some moment during n insertions |
| doubly linked list: data fields per node | 1 of 3 fields |
| possible two-node data-structure designs | at least 10^32 (10^48 three-node) designs |
| data-structure designs published | a couple of thousand in sixty years designs |
| learned index speed over B-tree | up to 70% faster, an order of magnitude less memory ratio |
| Bloom filter space against lower bound | within a factor of about 1.44 ratio |
| Bloom filter bits per element for 1% false positives | fewer than 10 bits |
| DRAM access energy against an addition | about 800 times |
| share of system energy spent on data movement | 62.7% percent (consumer workloads) |
| suffix-array construction space for the human genome | 12 GB bytes |
| BVI learners in the Arboretum evaluation | 8 people |
| cell-probe lower bound for partial sums and dynamic connectivity | Omega(lg n) cell reads/writes per operation (amortized) |
Open contentions (4) open contention
Where sources or readings disagree. Both stay on the map.
- C-2257 Does the brain store a map or a graph of places?
booked: The map keeps both readings.
the other reading: a Euclidean cognitive map only (the classical view); graph-like codes only; whether cognitive graphs carry local metric information is itself open - C-2262 When did data structures begin?
booked: The map books the first computer ones and keeps older orderings as a contention.
the other reading: older human orderings are data structures too: catchwords linking scrolls 'no later than the Homeric era', printers' catchwords, Eytzinger's tree-as-array numbering 'over four hundred years old'; brains build them: hippocampal indexes and barcodes, cognitive graphs (rung 9 or earlier) - C-2287 Can learned models replace classic indexes?
booked: The map keeps it contested.
the other reading: classic indexes kept as the better general choice (not read here); indexes are models already, so the line between them is a reading, not a kind - C-2302 Must every data structure trade reads, updates and memory?
booked: The map books the conjecture as unproven.
the other reading: a proven law (the paper calls proving it future work); only an empirical regularity of current hardware
Partners and parts published science
Built from / builds (6)
- Computer science (the field: the practice and the computation it studies)
- Algorithm (the practice of step-by-step procedures and the structure they compute)
- Hash function (non-cryptographic)
- Memory word (cell)
- Pointer (memory address held as data)
- Sorting algorithm
Sits inside / holds (3)
Trades with (valence) (12)
- Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature via sys:computer-memory · Data structure gain
- Computer science (the field: the practice and the computation it studies) via sys:written-record · Data structure gain
- Sequential information (the order of units along a linear polymer) via sys:sequential-information · Data structure gain
- Human (Homo sapiens) via sys:sensory-environment · Data structure gain
- Software via sys:electromagnetic-field · Data structure gain
- Algorithm (the practice of step-by-step procedures and the structure they compute) via sys:written-record · Data structure gain
- Programming language via sys:written-record · Data structure gain
- Cryptographic hash function via sys:written-record · Data structure gain
- Hash function (non-cryptographic) via sys:written-record · Data structure gain
- Computer hardware via sys:electromagnetic-field · Data structure gain
- Database via sys:computer-hardware · Data structure gain
- Sorting algorithm via sys:written-record · Data structure even
expressed by (15)
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Quality Improvement/Refinement
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Evolvability/Plasticity Engineering (Design for Future Variation)
- Internal Coordination/Regulation
- Search/Foraging
- Mapping/Modeling
- Navigation/Pathfinding
- Speed
- Prepositioning & Latency
- Triage & Prioritized Allocation
- Positional Identity (Body Map)
floor filled by (19)
- Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature
- Compiler
- Computer science (the field: the practice and the computation it studies)
- Sequential information (the order of units along a linear polymer)
- Human (Homo sapiens)
- Algorithm (the practice of step-by-step procedures and the structure they compute)
- Programming language
- Hash function (non-cryptographic)
- File system
- Computer hardware
- Database
- DNA sequencing
- Memory word (cell)
- Pointer (memory address held as data)
- Array
- Linked list
- Abstract data type
- Search engine (paid search platform)
- Sorting algorithm
represents (1)
Kinds (19)
- Array
- Record (tuple, struct)
- Linked list
- Hash table
- Tree
- B-tree
- Heap (binary heap)
- Trie (prefix tree)
- Graph
- Stack
- Queue
- Skiplist
- Bloom filter
- Persistent data structure
- Concurrent data structure
- Learned index
- FM-index / Burrows-Wheeler index
- Log-structured merge tree (differential structure)
- Data structure in a vector symbolic architecture
Notes published science
- Linked lists are older than computers by more than two thousand years: scribes copying papyrus scrolls wrote the first word of the next scroll at the end of each one (the 'reclamans', 'shouting back'), and printers later put the next page's first word at the foot of every page (src:wp:linked-list).
- Researchers who counted the ways to combine data-structure building blocks found at least 10^32 possible two-node designs, more than the stars in the sky, while computer scientists have published only a couple of thousand in sixty years; like Mendeleev's table, the empty cells point to designs nobody has built yet (src:idreos-2018-periodic-table).
- Fetching one number from main memory costs about 800 times the energy of adding two numbers, and on phones about 63% of all energy goes to moving data around, which is why the choice of data structure (how far data must travel) matters so much (src:mutlu-2020-pim-primer). And a food-caching bird's hippocampus seems to stamp each hidden seed with its own sparse 'barcode', an index kept apart from the memory's contents, much like a key in a hash table (src:fang-2026-barcodes).
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
a data structure as computer scientists describe it: data in the world, held in memory, laid out, operated on at a cost, behind an interface, put to use (reader's view)
- L1: Data in the world and requests for it: contacts, files, web pages, accounts, genomes; the program's calls to add, find and remove
- L2: Memory: words in cells reached by address (RAM), blocks on disk, caches; costs counted per cell read or written
- L3: Layout: contiguous cells (arrays, records) or linked nodes holding addresses (lists, trees, graphs); hash slots
- L4: Operations and their invariants: insert, delete, find, traverse; B-tree splits, heap order, probing to the next free slot
- L5: Costs: time and space, worst-case, amortized and expected; read, update and memory overheads traded against one another
- L6: The interface (abstract data type): list, stack, queue, set, map, priority queue; what the structure does for its user
- L7: Uses back on the world: database indexes, compilers' symbol tables, file systems, search engines, genome aligners, a phone's contact list
the boardroom (shared floors)
- L3: The layout in memory: contiguous arrays and records, or linked nodes holding addresses; hash slots; the shape the designer chose
- L4: The operations and the invariants they keep (balance, order, fill bounds): insert, delete, find, traverse
- L5: The costs: time and space (worst-case, amortized, expected), cells read and written, read/update/memory overheads, energy of data movement
- L6: The interface or abstract data type: what operations are offered and what they mean
- L7: Uses back on the world: databases, compilers, file systems, search engines, aligners, phones
way in: Operation calls: the program's requests
- L1: A request from the program (and behind it a person typing or a query arriving): add x, find x, remove x
- L2: The arguments as words: a key, an index i, a value
- L3: The key located in the layout: hashed to a slot, compared down a tree, an address computed
way in: Other threads using the structure at the same time
- L1: Several computing threads reaching one instance simultaneously
way in: Random choices
- L1: A source of random integers
- L2: Random integers in a set range (hash multipliers, skiplist heights)
way in: The data itself: keys and their distribution
- L1: The data to be stored: records, strings, a reference genome
- L2: Keys as w-bit words, or strings of symbols
way in: The designer's choices
- L1: The problem, the workload and the hardware as designers understand them
- L2: First principles of layout combined into a design
way in: The memory hierarchy: cells, caches, blocks
- L1: Storage devices: RAM, solid-state and hard disks, with access times from under 0.000113 ms to 19 ms
- L2: Cells, words and disk blocks reached by address; a whole block read at once
way in: The workload: the mix of reads and updates over time
- L1: The stream of operations and its changes: more reads, more writes, new applications
- L2: The read, update and memory overheads it imposes
way out: Energy spent moving data, leaving as heat
- L1: Most of a device's energy spent on data movement through the memory hierarchy
- L5: Cost of each cell or block touched: a DRAM access about 800 times an addition
way out: The answer returned to the caller
- L1: To the program, and through it to a screen (a contact shown before typing ends)
- L2: One word returned (a value or a reference)
- L6: The result the interface promises (the value for a key, the next item, membership)
way out: The structure shown to a person
- L1: Seen on a screen, felt as tactile graphics, heard through a screen reader
- L6: The structure's relationships rendered: nodes and arrows, tables, navigable trees
way out: Writes into memory: the layout changed
- L1: Cells and disk blocks written
- L3: A new array of size 2n, a split node, a key moved to the next slot
- L4: An insert, a split, a resize
Sources (25) published science
Pat Morin, Open Data Structures (Java edition), open textbook, CC BY (opendatastructures.org) (behind its links)
Athanassoulis M, Kester MS, Maas LM, Stoica R, Idreos S, Ailamaki A, Callaghan M. Designing Access Methods: The RUM Conjecture. EDBT 2016 (OpenProceedings, CC BY-NC-ND) (behind its links)
Mutlu O, Ghose S, Gomez-Luna J, Ausavarungnirun R, Sadrosadati M, Oliveira GF. A Modern Primer on Processing in Memory. arXiv:2012.03112 (behind its links)
Idreos S, Zoumpatianos K, Athanassoulis M, et al. The Periodic Table of Data Structures. IEEE Data Engineering Bulletin 41(3):64-75 (2018) (behind its links)
Hash table (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Computer science (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Sorting algorithm (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Abstract data type (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Kraska T, Beutel A, Chi EH, Dean J, Polyzotis N. The Case for Learned Index Structures. arXiv:1712.01208v3 (2018); SIGMOD 2018 (behind its links)
Broder A, Mitzenmacher M. Network Applications of Bloom Filters: A Survey. Internet Mathematics 1(4):485-509 (2004), author copy (behind its links)
Bloom filter (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Patrascu M, Demaine ED. Logarithmic Lower Bounds in the Cell-Probe Model. arXiv:cs/0502041v2 (2005); SIAM J. Computing 35(4) 2006 (behind its links)
B-tree (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Persistent data structure (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Linked list (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Frady EP, Kent SJ, Olshausen BA, Sommer FT. Resonator networks for factoring distributed representations of data structures. Neural Computation (2020), arXiv:2007.03748 (behind its links)