[Haskell-cafe] Looking for an efficient tree in STM

[John Meacham]

On Sat, Mar 18, 2006 at 05:46:30PM -0500, ajb at spamcop.net wrote:
> B-trees are popular for a similar reason.  A node is an obvious unit of
> granularity, since different threads can work in different nodes without
> interfering.  Not only is the page size tunable, there is also an obvious
> way to "group" nodes together such that locks can cover more than one
> physical node if you need that.

I believe the current best choice in concurrent environments is
'skip-lists' since they require no global invarients (or locks) to be
maintained as they are probabalistic. They parallelize very well.

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈