The Linux Maple Tree
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, …
| Talk Title | The Linux Maple Tree |
| Speakers | Matthew Wilcox (Programmer, Oracle) |
| Conference | Open Source Summit + ELC North America |
| Conf Tag | |
| Location | San Diego, CA, USA |
| Date | Aug 19-23, 2019 |
| URL | Talk Page |
| Slides | Talk Slides |
| Video | |
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.
