Mentorship Session: The Maple Tree: Structure and Algorithms

Mentor: Liam Howlett, Consulting Member of Technical Staff, Oracle

The Maple Tree is an RCU-safe b-tree variant that stores non-overlapping ranges. Storing ranges allows for greater data density, while RCU-safety reduces lock contention. Introducing ranges to a tree has subtle implementation details that alters many of the methods generally used for b-trees. This session will cover the reasons for the development of the maple tree, benefits, internal tree layout, as well as an overview of common operations such as searching, inserting, splitting, and rebalancing.