Radix Trees: How IntMap Works
summary
Haskell's IntMap is a radix tree (Patricia trie) that stores integer keys bitwise with path compression so lookups cost key-length, not map-size; worst case for 64-bit keys can be ~64 pointer hops. IntMap enables fast persistent merges and prefix queries and is used in GHC containers and Scala’s standard library. The Adaptive Radix Tree (ART) replaces 2-way branching with byte-at-a-time nodes and four node representations to shorten trees; C/Java ART benchmarks beat Java HashMap, but a Haskell ART prototype performed poorly while a Java persistent wrapper did well.
AI-written summary · about
chapters (7)
- 0:00Introduction to radix trees
- 4:17Benefits of the data structure
- 7:43How tries and trees work
- 13:02Implementing an int map
- 17:03Scaling and trade-offs
- 20:36Adaptive radix trees
- 24:50Summary and Q&A
related talks
31mDESIGNING DATA STRUCTURES FOR THE TYPELEVEL ECOSYSTEM
46mImmutable Sequential Maps – Keeping order while hashed
39mExtreme Cleverness: Functional Data Structures in Scala
51mFast Immutable Interval Sets
40mADTs For The Win!
32mLIFTING DATA STRUCTURES TO THE TYPE-LEVEL
20mWhat does the functor do on the tree?
28mRust and Scala, Sitting in a Tree….