CTrie

Basic idea

A concurrent, lock-free hash array mapped trie (HAMT) with O(1) snapshots via persistent, copy-on-write generation counters. Supports linearisable read/update plus consistent atomic iteration.

Key formulas

• Lookup/insert/delete: $O(\log_{32} n)$ expected (32-way branching)
• Snapshot: $O(1)$ amortised
• Memory: $O(n)$

Resources

• http://aleksandar-prokopec.com/resources/docs/ctries-snapshot.pdf

Siblings

• Adaptive Radix Tree
• Bloom filter
• Cache Oblivious Algorithms & Datastructures
• Count-min sketch
• Disjoint Set
• Fenwick tree
• Fibonacci heaps
• Finger-Trees
• GeoHash
• Hash Array Mapped Tries
• Hash Tables
• Hilbert-R Tree
• HyperLogLog
• Judy Arrays
• k-d Tree
• Links
• M Tree
• Pairing heaps
• R tree
• RRB-Trees
• Segment Trees
• Sparse Sets
• Succint Datastructures