[wandermatt]

Compared to a Bitmapped Vector Trie.

If you don't want to watch the video, a version of this talk was also given at Strange Loop, the slides for that one are available online: http://www.infoq.com/presentations/Functional-Data-Structure...

[marssaxman]

Thanks, never heard of a "bitmapped vector trie" before. I'll have to look it up.

[jasonwatkinspdx]

A more common name is Array Mapped Trie. See the papers by Phil Bagwell (RIP). DJB's crit-bit Trie page is good also. Many people forget that it's rather easy to pack tries for locality since there is no rebalancing to fragment nodes.

AMT's are one of clojure's most heavily used container types.