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.