Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Maple Tree

Linux Plumbers Conference via YouTube

Overview

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.

Syllabus

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

Taught by

Linux Plumbers Conference

Reviews

Start your review of Maple Tree

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.