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

Linux Foundation

The Linux Maple Tree

Linux Foundation via YouTube

Overview

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.

Syllabus

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

Taught by

Linux Foundation

Reviews

Start your review of The Linux 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.