EVOPEDIA

← 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 at1945 (von Neumann's array-sorting program for EDVAC)
born precisionyear; older human orderings contested (C-2262)
boundaryInside: 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 levelBuilt 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.
scaletechnological

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 insertionO(1) splits per insertion (amortized)
amortized B-tree splits per insertionconstant splits
RAM against disk access timeRAM > 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 costindependent of the number of elements (average, well-dimensioned table) time
linear-probing table at most half fullt.length >= 2q slots
open addressing maximum load factor0.6 to 0.75 elements per slot
wasted space lower bound for a growing listabout the square root of n words, at some moment during n insertions
doubly linked list: data fields per node1 of 3 fields
possible two-node data-structure designsat least 10^32 (10^48 three-node) designs
data-structure designs publisheda couple of thousand in sixty years designs
learned index speed over B-treeup to 70% faster, an order of magnitude less memory ratio
Bloom filter space against lower boundwithin a factor of about 1.44 ratio
Bloom filter bits per element for 1% false positivesfewer than 10 bits
DRAM access energy against an additionabout 800 times
share of system energy spent on data movement62.7% percent (consumer workloads)
suffix-array construction space for the human genome12 GB bytes
BVI learners in the Arboretum evaluation8 people
cell-probe lower bound for partial sums and dynamic connectivityOmega(lg n) cell reads/writes per operation (amortized)

Open contentions (4) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (6)

Sits inside / holds (3)

Trades with (valence) (12)

expressed by (15)

floor filled by (19)

represents (1)

Kinds (19)

Notes published science

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)

  1. L1: Data in the world and requests for it: contacts, files, web pages, accounts, genomes; the program's calls to add, find and remove
  2. L2: Memory: words in cells reached by address (RAM), blocks on disk, caches; costs counted per cell read or written
  3. L3: Layout: contiguous cells (arrays, records) or linked nodes holding addresses (lists, trees, graphs); hash slots
  4. L4: Operations and their invariants: insert, delete, find, traverse; B-tree splits, heap order, probing to the next free slot
  5. L5: Costs: time and space, worst-case, amortized and expected; read, update and memory overheads traded against one another
  6. L6: The interface (abstract data type): list, stack, queue, set, map, priority queue; what the structure does for its user
  7. 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)

  1. L3: The layout in memory: contiguous arrays and records, or linked nodes holding addresses; hash slots; the shape the designer chose
  2. L4: The operations and the invariants they keep (balance, order, fill bounds): insert, delete, find, traverse
  3. L5: The costs: time and space (worst-case, amortized, expected), cells read and written, read/update/memory overheads, energy of data movement
  4. L6: The interface or abstract data type: what operations are offered and what they mean
  5. L7: Uses back on the world: databases, compilers, file systems, search engines, aligners, phones

way in: Operation calls: the program's requests

  1. L1: A request from the program (and behind it a person typing or a query arriving): add x, find x, remove x
  2. L2: The arguments as words: a key, an index i, a value
  3. 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

  1. L1: Several computing threads reaching one instance simultaneously

way in: Random choices

  1. L1: A source of random integers
  2. L2: Random integers in a set range (hash multipliers, skiplist heights)

way in: The data itself: keys and their distribution

  1. L1: The data to be stored: records, strings, a reference genome
  2. L2: Keys as w-bit words, or strings of symbols

way in: The designer's choices

  1. L1: The problem, the workload and the hardware as designers understand them
  2. L2: First principles of layout combined into a design

way in: The memory hierarchy: cells, caches, blocks

  1. L1: Storage devices: RAM, solid-state and hard disks, with access times from under 0.000113 ms to 19 ms
  2. 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

  1. L1: The stream of operations and its changes: more reads, more writes, new applications
  2. L2: The read, update and memory overheads it imposes

way out: Energy spent moving data, leaving as heat

  1. L1: Most of a device's energy spent on data movement through the memory hierarchy
  2. L5: Cost of each cell or block touched: a DRAM access about 800 times an addition

way out: The answer returned to the caller

  1. L1: To the program, and through it to a screen (a contact shown before typing ends)
  2. L2: One word returned (a value or a reference)
  3. L6: The result the interface promises (the value for a key, the next item, membership)

way out: The structure shown to a person

  1. L1: Seen on a screen, felt as tactile graphics, heard through a screen reader
  2. L6: The structure's relationships rendered: nodes and arrows, tables, navigable trees

way out: Writes into memory: the layout changed

  1. L1: Cells and disk blocks written
  2. L3: A new array of size 2n, a split node, a key moved to the next slot
  3. L4: An insert, a split, a resize

Sources (25) published science

Data structure (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01)
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)
Wimer BL, Kanchi R, Frierson K, et al. Nonvisual Support for Understanding and Reasoning about Data Structures. CHI '26, arXiv:2601.19168 (CC BY 4.0), doi:10.1145/3772318.3791656 (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)
Li H, Durbin R. Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14):1754-1760 (2009), PMC2705234, doi:10.1093/bioinformatics/btp324 (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)
Heap (data structure) (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Linked list (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Recursive data type (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-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)
Array (data structure) (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Stack (abstract data type) (encyclopedia, Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Peer M, Brunec IK, Newcombe NS, Epstein RA. Structuring Knowledge with Cognitive Maps and Cognitive Graphs. Trends Cogn Sci 25(1):37-54 (2021), PMC7746605 (author manuscript) (behind its links)
Fang C, Lindsey JW, Abbott LF, Aronov D, Chettih SN. Barcode activity in a recurrent network model of the hippocampus enables efficient memory binding. eLife (2026), PMC12782553 (behind its links)