Exotic Functional Data Structures - Hitchhiker Trees

This talk develops the Hitchhiker tree, an open-source functionally persistent fractal tree for scalable storage. It reviews functional data structures and B-trees before examining performance, insertion, persistence, and an API for storing application state off-heap.

Syllabus

Intro
Functional Data Structures
How to fix this?
A List of Fruit
Mutation in an Immutable World
Pointers!
Pointers and Sharing
Editing the Linked List
Worse Case Performance
Philosophy of Identity
Binary Search Trees
Performance Analysis/Algebra
Properties of Trees
B Trees are Optimal for Reads
B+ Tree
Fractal Trees
Appending to a Log
Fractal Insertion
Walking Through Insertions
Find the Path
Project Pending Operations
Broken for Scans
Only Project Values Within Range
Path Copying or Not!
Flush Control
Real Branching Factors
Datacrypt is Pluggable
Outboard