On: Finger Trees: A Simple General-Purpose Data Struct...

[detrino]

I would expect B-trees to outperform binary trees even in a persistent data structure. The necessity of binary trees comes when you need stable iterators/references.