A field guide to the structures behind databases, distributed systems, geometry, graphics, search, runtimes, and machine learning systems. Read the finished chapters now; the rest mark the path of the handbook.
Vol. I
Foundations
The small structures that show up everywhere else.
Sets, Queues, And Membership
Bloom Filter
Probabilistic membership: probably yes, definitely no.
Read chapterUnion-Find
Merge sets, compress paths, answer connectivity fast.
Read chapterRing Buffer
Fixed-size queues for streams, logs, and low-latency systems.
Read chapterPriority Queue
Always pull the highest-priority item next.
Read chapterDeque
Push and pop efficiently from both ends.
Read chapterOrdered Search Structures
Skip List
Ordered search with coin-flip express lanes.
Read chapterTreap
A randomized binary search tree with heap priorities.
Coming soonSplay Tree
A tree that moves hot keys close to the root.
Coming soonVan Emde Boas Tree
Integer-key operations in tiny logarithmic time.
Coming soonRed-Black Tree
Balanced search with strict coloring invariants.
Coming soonAVL Tree
Height-balanced search with aggressive rotations.
Coming soonScapegoat Tree
Rebuild unbalanced subtrees instead of storing balance metadata.
Coming soonHeaps And Merge Structures
Binary Heap
The compact array-backed priority queue.
Coming soonBinomial Heap
A forest of power-of-two heaps built for merging.
Coming soonFibonacci Heap
Lazy merging with excellent amortized graph operations.
Coming soonPairing Heap
A practical meldable heap with simple pointer structure.
Coming soonTournament Tree
Keep winners visible while merging many sorted streams.
Coming soonText And Functional Structures
Trie
Prefix search, autocomplete, routing tables, and dictionaries.
Coming soonRope
A text buffer structure for large editable documents.
Coming soonZipper
Navigate and edit immutable trees with local focus.
Coming soonPersistent Data Structures
Keep old versions without copying the whole world.
Coming soonFinger Tree
A functional sequence structure for fast access near fingers.
Coming soonHAMT
Hash-array mapped tries for persistent maps and sets.
Coming soonVol. II
Databases
Indexes, logs, filters, and storage layouts behind real engines.
Write-Heavy Storage
LSM Tree
Append now, sort in memory, merge the debt later.
Read chapterWrite-Ahead Log
Durability before mutation: the recovery backbone.
Coming soonBitcask / Hash Index
Append-only files with an in-memory key directory.
Coming soonAdvanced Write-Heavy Indexes
Cuckoo Filter
A deletable membership filter for storage engines.
Coming soonBloom Filter Cascade
Layered filters for multi-level LSM lookups.
Coming soonMasstree
A cache-conscious trie of B+ trees for modern hardware.
Coming soonLog-Structured Merge Forest
Many LSMs working together instead of one tree.
Coming soonFractal Tree Index
Buffer updates inside a tree to reduce random writes.
Coming soonBw-Tree
A latch-free B-tree variant built from delta records.
Coming soonRead-Heavy Storage
B+ Tree
The classic page-oriented index for range scans.
Coming soonB-tree vs LSM Tree
Why reads, writes, and compaction trade places.
Coming soonRoaring Bitmap
Compressed posting lists and fast set operations.
Coming soonSegment Tree
Range queries with logarithmic updates.
Coming soonFenwick Tree
Compact prefix sums for mutable numeric data.
Coming soonZone Map
Skip blocks by storing min/max summaries per chunk.
Coming soonSparse Index
Index representative keys instead of every row.
Coming soonColumnar And Analytical Layouts
Column Store
Store each field separately for scans and compression.
Coming soonDictionary Encoding
Replace repeated values with compact integer ids.
Coming soonRun-Length Encoding
Compress repeated values as value and count pairs.
Coming soonBitmap Index
Use bitsets to answer analytical filters quickly.
Coming soonCaches And Memory Indexes
LRU Cache
Evict the least recently touched item.
Coming soonLFU Cache
Evict by access frequency instead of recency.
Coming soonARC Cache
Balance recent and frequent access patterns adaptively.
Coming soonClock Cache
Approximate LRU with a circular reference-bit scan.
Coming soonSlab Allocator
Group fixed-size allocations for predictable memory reuse.
Coming soonSearch And Vector Indexes
TF-IDF / BM25
The scoring model behind practical keyword search.
Coming soonSuffix Array / Suffix Tree
Substring search without scanning every character.
Coming soonAho-Corasick Automaton
Match many patterns in one pass.
Coming soonHNSW Graph
Approximate nearest-neighbor search at scale.
Coming soonLocality-Sensitive Hashing
Put similar vectors into the same buckets.
Coming soonIVF Index
Partition vector space into coarse clusters before search.
Coming soonProduct Quantization
Compress vectors into codebooks for fast approximate search.
Coming soonVol. III
Distributed Systems
Data representations for partitioning, causality, replication state, and distributed logs.
Partitioning And Placement
Hash Ring
Represent key ownership around a circular token space.
Coming soonPartition Map
Map key ranges or shards to replica owners.
Coming soonVirtual Nodes
Smooth load across uneven machines in a hash ring.
Coming soonShard Map
Route keys through an explicit partition ownership table.
Coming soonReplica State
Merkle Tree
Compare replica state by hashing whole subtrees.
Coming soonReplica Set
Represent the nodes responsible for each shard copy.
Coming soonReplication Log
Store ordered state changes for followers to replay.
Coming soonTime, Causality, And Ordering
Vector Clock
Track causal order without one global clock.
Coming soonLamport Clock
Create a partial ordering of events with counters.
Coming soonHybrid Logical Clock
Blend physical time with causal ordering.
Coming soonVersion Vector
Track per-replica versions for conflict detection.
Coming soonConflict-Free Collaboration
CRDT
A family of mergeable replicated data structures.
Coming soonCausal Tree
Represent collaborative text as ordered causally linked inserts.
Coming soonLast-Writer-Wins Register
A simple conflict rule with sharp tradeoffs.
Coming soonObserved-Remove Set
A CRDT set that makes adds and removes mergeable.
Coming soonQueues, Logs, And Streams
Partitioned Commit Log
Scale ordered event storage across independent partitions.
Coming soonConsumer Offset Index
Track per-reader progress through an append-only log.
Coming soonDelay Queue
Release work only after its scheduled time arrives.
Coming soonDead Letter Queue
Preserve failed messages for diagnosis and replay.
Coming soonVol. IV
Spatial And Geometry
Indexes and representations for points, polygons, maps, and collision worlds.
Point And Region Indexes
KD-tree
Split space by alternating coordinate axes.
Coming soonQuadtree / R-tree
Partition or bound space for map and region queries.
Coming soonInterval Tree
Find overlapping ranges efficiently.
Coming soonGeohash
Encode nearby coordinates with shared prefixes.
Coming soonS2 Cell
Index the globe with hierarchical cells on a projected cube.
Coming soonH3 Hex Index
Represent Earth with hierarchical hexagonal cells.
Coming soonCollision And Acceleration Structures
Bounding Volume Hierarchy
Nested boxes for fast intersection tests.
Coming soonBSP Tree
Recursively split space with planes for visibility and collision.
Coming soonAABB Tree
Maintain axis-aligned boxes for dynamic collision worlds.
Coming soonSpatial Hash Grid
Bucket nearby objects by grid cell for broad-phase queries.
Coming soonPlanar Geometry Structures
Voronoi Diagram
Divide space by nearest site.
Coming soonDelaunay Triangulation
Connect points into well-shaped triangles.
Coming soonArrangement
Store vertices, edges, and faces induced by curves or segments.
Coming soonQuad-Edge
Represent primal and dual planar subdivisions together.
Coming soonMesh And Polygon Representation
Half-Edge Data Structure
Store mesh adjacency for traversal and editing.
Coming soonDCEL
A planar subdivision structure for faces, edges, and vertices.
Coming soonWinged-Edge Mesh
Store rich edge adjacency for manifold surfaces.
Coming soonFace-Vertex Mesh
Store geometry as vertex arrays plus indexed faces.
Coming soonVol. V
Graphics Programming
The rendering pipeline from pixels to scenes.
Rasterization Pipeline
Z-buffer
Depth testing so nearer fragments win.
Coming soonBarycentric Coordinates
Interpolate values across triangles.
Coming soonAnti-Aliasing
MSAA, FXAA, and TAA for smoother edges.
Coming soonG-buffer
Store per-pixel material and geometry data for deferred rendering.
Coming soonGPU Programs And Surfaces
Shader
Vertex and fragment programs in the GPU pipeline.
Coming soonTexture Mapping / UVs
Wrap images onto mesh surfaces.
Coming soonNormal Mapping
Fake surface detail by perturbing normals.
Coming soonSigned Distance Field
Represent shapes by distance to the nearest surface.
Coming soonScene Organization And Visibility
Scene Graph
Represent transforms and hierarchy in a world.
Coming soonLevel-of-Detail Hierarchy
Store alternate mesh resolutions for distance-based rendering.
Coming soonPortal Graph
Represent visible room-to-room connections in indoor scenes.
Coming soonLighting And Render Architecture
Ambient Occlusion
Darken creases where nearby geometry blocks light.
Coming soonDeferred vs Forward Rendering
Choose where lighting work happens.
Coming soonGlobal Illumination
Model indirect light bouncing through a scene.
Coming soonLightmap
Store baked lighting in texture space.
Coming soonCurves, Volumes, And Transforms
Bezier Curves / B-splines
Smooth curves for paths, fonts, and animation.
Coming soonQuaternion
Represent 3D rotation without Euler angle traps.
Coming soonSkeletal Animation
Drive meshes with bone hierarchies and skin weights.
Coming soonDual Quaternion Skinning
Blend rigid transforms with fewer collapsing artifacts.
Coming soonVol. VI
Sketches And Approximation
Tiny summaries for huge streams and uncertain answers.
Probabilistic Summaries
HyperLogLog
Estimate distinct counts in a tiny amount of memory.
Coming soonCount-Min Sketch
Approximate frequencies in streaming data.
Coming soonCuckoo Filter vs Bloom Filter
Membership tests when deletion matters.
Coming soonQuotient Filter
A compact deletable approximate membership structure.
Coming soonXor Filter
Fast static membership filters with low memory overhead.
Coming soonT-Digest
Approximate quantiles accurately at distribution tails.
Coming soonKLL Sketch
A compact quantile sketch with strong error bounds.
Coming soonTime-Series Structures
Time-Series Chunk
Store ordered samples in compressed time-window blocks.
Coming soonDelta-of-Delta Series Block
Store timestamps as changes in spacing inside compressed blocks.
Coming soonGorilla Block
A time-series block layout for timestamp and float compression.
Coming soonDownsampling Rollup
Precompute coarser windows for long-range queries.
Coming soonRetention Tier Index
Organize hot, warm, and cold series by age.
Coming soonTime-Partitioned B+ Tree
Route recent and historical samples through time ranges.
Coming soonTSM File
Influx-style immutable time-series blocks and indexes.
Coming soonLSM Time-Series Layout
Use sorted runs optimized for append-heavy metrics.
Coming soonStream Windows And Heavy Hitters
Sliding Window Counter
Track recent activity without storing every event.
Coming soonExponential Histogram
Approximate counts over a moving time window.
Coming soonHeavy-Hitter Summary
Track dominant keys in high-volume streams with bounded memory.
Coming soonReservoir Sample
Store a representative sample from an unknown stream.
Coming soonMisra-Gries Summary
Track frequent items with bounded counters.
Coming soonLossy Counting Summary
Store approximate frequent items over stream buckets.
Coming soonVol. VII
Graph Structures
Representations for relationships, dependencies, control flow, and graph-shaped data.
Graph Representations
Adjacency List
Store sparse graph neighbors compactly.
Coming soonAdjacency Matrix
Constant-time edge checks for dense graphs.
Coming soonCompressed Sparse Row
Pack graph edges into arrays for fast traversal.
Coming soonEdge List
Represent graphs as sortable relationship records.
Coming soonProperty Graph
Attach labels and attributes to nodes and edges.
Coming soonGraph Families And Components
Directed Graph
Store relationships where edges have orientation.
Coming soonUndirected Graph
Store symmetric relationships between vertices.
Coming soonDirected Acyclic Graph
Represent dependencies with no directed cycles.
Coming soonMultigraph
Allow multiple edges between the same pair of vertices.
Coming soonHypergraph
Represent edges that can connect more than two vertices.
Coming soonSpecialized Graph Structures
Dominator Tree
Represent dominance relationships in a control-flow graph.
Coming soonSPQR Tree
Decompose a graph by its triconnected components.
Coming soonLink-Cut Tree
Maintain a changing forest with path queries.
Coming soonGraph-Structured Stack
Share parser stack prefixes across ambiguous parses.
Coming soonFlow And Constraint Graphs
Residual Graph
Track remaining capacity and reverse corrections in flow.
Coming soonBipartite Matching Graph
Pair two sets under compatibility constraints.
Coming soonFactor Graph
Represent variables and constraints as a bipartite graph.
Coming soonDecision Diagram
Compactly represent boolean functions as a directed graph.
Coming soonVol. VIII
Compilers And Runtimes
Structures that turn source code into execution.
Parsing And Syntax
Token Stream
The linear structure produced by lexical analysis.
Coming soonParse Tree
Represent grammar derivations before semantic cleanup.
Coming soonAbstract Syntax Tree
The program shape compilers actually transform.
Coming soonPratt Parser Table
Encode expression precedence with binding powers.
Coming soonConcrete Syntax Tree
Preserve source-level syntax details for tooling.
Coming soonIntermediate Representation
Control-Flow Graph
Represent basic blocks and jumps between them.
Coming soonStatic Single Assignment
Give every value one definition for easier optimization.
Coming soonUse-Def Chain
Link variable definitions to the places that use them.
Coming soonSymbol Table
Map names to scopes, types, and declarations.
Coming soonType Environment
Track inferred and declared types across scopes.
Coming soonRuntime Memory
Call Stack
Store frames, locals, returns, and control flow.
Coming soonHeap Arena
Allocate many objects from large memory regions.
Coming soonFree List
Track reusable memory blocks after deallocation.
Coming soonHeap Object Graph
Represent object references for tracing and garbage collection.
Coming soonGenerational Heap
Separate young and old objects for faster collection.
Coming soonVol. IX
Networking And Security
Packet paths, identity, integrity, and authenticated storage.
Network Lookup And Routing
Radix Tree
Compress prefixes for routing tables and string maps.
Coming soonPatricia Trie
Bitwise compressed trie for IP prefix lookup.
Coming soonRouting Table
Choose next hops by destination prefix.
Coming soonConnection Table
Track active flows by five-tuple keys.
Coming soonToken Bucket
Rate-limit bursts with refillable capacity.
Coming soonCryptographic Structures
Merkle Tree
Authenticate large sets through recursive hashes.
Coming soonMerkle Patricia Trie
Authenticated key-value storage for blockchain state.
Coming soonSparse Merkle Tree
Prove membership in a huge mostly-empty key space.
Coming soonHash Chain
Link records so tampering changes every later hash.
Coming soonAccumulator
Compactly prove set membership with cryptographic witnesses.
Coming soonVol. X
Machine Learning And IR
Structures for retrieval, ranking, tensors, and learned representations.
Retrieval Indexes
Inverted Index
Map terms to documents and positions.
Coming soonPosting List
Store document ids, positions, and term payloads.
Coming soonSkip Pointer
Jump across long posting lists during intersection.
Coming soonFST Term Dictionary
Compress sorted terms into a finite-state transducer.
Coming soonWAND Index
Skip low-scoring documents during top-k retrieval.
Coming soonVector And Tensor Layouts
Embedding Matrix
Store learned vector rows for tokens or entities.
Coming soonTensor Strides
Map multidimensional indexes onto flat memory.
Coming soonSparse Tensor
Store only non-zero coordinates and values.
Coming soonQuantized Tensor
Pack approximate numeric values into smaller types.
Coming soonKV Cache
Reuse transformer attention keys and values during generation.
Coming soon