The Linux Maple Tree

Explore the innovative Maple Tree data structure for Linux in this 39-minute conference talk by Matthew Wilcox from Oracle. Discover how this efficient index range storage solution outperforms existing rbtree and radix tree structures while offering RCU-safety and optimization for modern CPUs. Learn about the implementation details, API inspired by XArray, and its ease of use compared to rbtree. Gain insights into various node types, memory consumption, and potential applications such as file descriptor tables and hash tables. Understand the short-term and long-term plans for Maple Tree development, and engage with open questions surrounding this promising new data structure in the Linux ecosystem.

Introduction
Linked Lists
RB Tree
Radix Tree
The Problem
Results
Memory Consumption
Radix Tree Problems
Node Types
API
Shortterm plans
Longerterm plans
File descriptor table
Hash tables
Open questions