Persistence, functional structures, succinct and compressed encodings, geometric indexing, concurrent and lock-free designs, external-memory structures, and probabilistic data 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 StructuresPath copying, fat nodes, persistent arrays, segment trees, treaps, heaps, union-find, functional queues, and distributed persistence models.
3.2 Functional Data StructuresImmutable lists, stacks, queues, heaps, HAMTs, functional BSTs, lazy evaluation, structural sharing, and deforestation.
3.3 Succinct and Compressed StructuresBit vectors, rank-select, succinct trees, FM-index, wavelet trees, Huffman and arithmetic coding, roaring bitmaps, and compressed range queries.
3.4 Geometric Data StructuresKD-trees, R-trees, quadtrees, octrees, Delaunay triangulation, Voronoi diagrams, HNSW, range trees, and sweep line structures.
3.5 Concurrent and Lock-Free StructuresMutex-protected structures, lock-free stacks, queues, hash tables, skip lists, CAS primitives, hazard pointers, epoch reclamation, and RCU.
3.6 External-Memory and Database StructuresB-tree indexes, LSM trees, SSTables, write-ahead logs, compaction strategies, cache-oblivious structures, inverted indexes, and external sort/merge.
3.7 Probabilistic Data StructuresBloom filters, cuckoo filters, count-min sketch, HyperLogLog, MinHash, reservoir sampling, skip lists, and treaps as probabilistic structures.