Exotic Functional Data Structures - Hitchhiker Trees

Explore the world of exotic functional data structures in this 41-minute conference talk from Strange Loop. Dive into the principles of functional data structures, focusing on trees, and learn about B trees and their advantages for storage. Discover the fascinating variant called fractal trees and understand how they can be made functional with exceptional performance. Unify these concepts to grasp the Hitchhiker tree, an open-source functionally persistent fractal tree. Examine an example API for using Hitchhiker trees that enables off-heap storage of application state, inspired by the 2014 paper "Fast Database Restarts at Facebook". Journey through topics such as mutation in an immutable world, pointers and sharing, binary search trees, performance analysis, B+ trees, fractal insertions, path copying, and more. Gain insights into solving limitations of functional data structures, particularly for handling gigabytes to terabytes of data, and explore the potential for scalable functional databases beyond Datomic.

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