It's probably worth listing the advantages of the Maple Tree over the
rbtree.
- Shallower tree. A 1000-entry rbtree is 10 levels deep. A 1000-entry
Maple Tree is 5 levels deep (I did a more detailed analysis in an
earlier email thread with Laurent and I can present it if needed).
- O(1) prev/next
- Lookups under the RCU lock
There're some second-order effects too; by using externally allocated
nodes, we avoid disturbing other VMAs when inserting/deleting, and we
avoid bouncing cachelines around (eg the VMA which happens to end up
at the head of the tree is accessed by every lookup in the tree because
it's on the way to every other node).