The Linux Maple Tree - Matthew Wilcox, Oracle
Channel: The Linux Foundation
Date: 2019-10-02

The Linux Maple Tree - Matthew Wilcox, Oracle

The Maple Tree is a new data structure for Linux that provides an efficient way to store index ranges which map to a single pointer. It is RCU-safe and optimised for modern CPUs. For this application, it outperforms both the existing rbtree and radix tree data structures. The API is inspired by the XArray, and is significantly easier to use than the rbtree. This talk will cover the details of the implementation and show examples of users.