Maple Tree

Explore the innovative Maple Tree data structure in this Linux Plumbers Conference talk. Delve into the advantages of Maple Tree over Red-Black and Radix trees for storing ranges in the kernel. Learn about its fast, cache-efficient design, simple API, and support for contiguous ranges. Discover how Maple Tree efficiently handles discontiguous ranges and single entries. Examine its potential for tracking free ranges, supporting search marks, and handling reclamation of shadow entries. Gain insights into the tree's structure, including node types, routes, and cache efficiency. Understand the current development status, potential applications like PID allocation, and future plans. Engage with open questions and considerations for implementing Maple Tree in various kernel contexts.

Maple Tree
Agenda
Why another tree
Why the Maple Tree
Tree Nodes
VMA
Node Types
Node Routes
Cache Efficiency
Projections
Memory
Development Status
PID Allocation
Dense Nodes
Hash Tables
Short Term Plan
Interval Tree
Open Questions
Sign my key
Leaf value