🎫 KubeCon + CloudNativeCon India · Dec 11-12 · Delhi REGISTER TODAY

Search

    Join

    Webinar On Demand

    Back to all webinars

    The Maple Tree: Structure and Algorithms

    Recorded October 9, 2024

    View an interactive, complimentary Mentorship Session exploring The Maple Tree: Structure and Algorithms with Liam Howlett, Consulting Member of Technical Staff, Oracle

    The Maple Tree is an RCU-safe b-tree variant that stores non-overlapping ranges.  Storing ranges allows for greater data density, while RCU-safety reduces lock contention.  Introducing ranges to a tree has subtle implementation details that alters many of the methods generally used for b-trees.  This session will cover the reasons for the development of the maple tree, benefits, internal tree layout, as well as an overview of common operations such as searching, inserting, splitting, and rebalancing.

    Download Slides
    Liam R. Howlett

    Consulting Member of Technical Staff, Oracle

    Speaker

    Liam R. Howlett is a computer engineer at Oracle and has been coding for more than 25 years, with the majority of the last decade focused on low level kernel development.  Liam is the maintainer of the maple tree, which he designed and wrote in collaboration with Matthew Wilcox for vma management.  The maple tree is now used in several key areas of the kernel including: irq descriptors, filesystems, and GPU drivers.  Liam is also a co-maintainer of the vma and mmap files in the memory management area of the Linux kernel.  He was the largest contributor to the v6.1 kernel.  Liam fills the rest of his time traveling, hiking, and playing music or mystery games with his wife and two young children.

    Stay Connected with the Linux Foundation