3. Specialized, Persistent, Concurrent, and External Structures
Persistence, functional structures, succinct and compressed encodings, geometric indexing, concurrent and lock-free designs, external-memory structures, and probabilistic data structures.
3. Specialized, persistent, concurrent, and external structures
| section | name |
|---|---|
| 3.1 | Persistent Data Structures |
| 3.2 | Functional Data Structures |
| 3.3 | Succinct and Compressed Structures |
| 3.4 | Geometric Data Structures |
| 3.5 | Concurrent and Lock-Free Structures |
| 3.6 | External-Memory and Database Structures |
| 3.7 | Probabilistic Data Structures |
3.1 Persistent Data Structures
Path copying, fat nodes, persistent arrays, segment trees, treaps, heaps, union-find, functional queues, and distributed persistence models.
3.2 Functional Data Structures
Immutable lists, stacks, queues, heaps, HAMTs, functional BSTs, lazy evaluation, structural sharing, and deforestation.
3.3 Succinct and Compressed Structures
Bit vectors, rank-select, succinct trees, FM-index, wavelet trees, Huffman and arithmetic coding, roaring bitmaps, and compressed range queries.
3.4 Geometric Data Structures
KD-trees, R-trees, quadtrees, octrees, Delaunay triangulation, Voronoi diagrams, HNSW, range trees, and sweep line structures.
3.5 Concurrent and Lock-Free Structures
Mutex-protected structures, lock-free stacks, queues, hash tables, skip lists, CAS primitives, hazard pointers, epoch reclamation, and RCU.
3.6 External-Memory and Database Structures
B-tree indexes, LSM trees, SSTables, write-ahead logs, compaction strategies, cache-oblivious structures, inverted indexes, and external sort/merge.