"Exotic Functional Data Structures: Hitchhiker Trees" by David Greenberg

Functional data structures are awesome--they're the foundation of many functional programming languages, allowing us to express complex logic immutably and efficiently. There is one unfortunate limitation: these data structures must fit on the heap, limiting their lifetime to that of the process. Several years ago, Datomic appeared as the first functional database that addresses these limitations. However, there hasn't been much activity in the realm of scalable (gigabytes to terabytes) functional data structures.
In this talk, we'll first review some of the fundamental principles of functional data structures, particularly trees. Next, we'll review what a B tree is and why it's better than other trees for storage. Then, we'll learn about a cool variant of a B tree called a fractal tree, how it can be made functional, and why it has phenomenal performance. Finally, we'll unify these concepts to understand the Hitchhiker tree, an open-source functionally persistent fractal tree. We'll also briefly look at an example API for using Hitchhiker trees that allows your application's state to be stored off-heap, in the spirit of the 2014 paper "Fast Database Restarts at Facebook".

[@AsotXxlS2000]

Such a good talk David. Thanks

[@frechjo]

3:27 intro to explaining pointers
5:21 intro to linked lists
6:50 intro to equality vs identity
8:25 intro to trees
11:00 intro to complexity analysis
13:00 intro to functional binary trees
17:00 intro to b-trees
...
I'm by half the talk and haven't seen any "Exotic Functional Data Structures" yet...

[@declup]

21:09 intro to B+ trees
22:42 intro to fractal trees
30:58 comparison of hitchhiker trees and fractal trees
35:25 comparison of fan-out of B+ trees and of hitchhiker trees
36:58 real-world use

[@14janvier86]

I am working on implementing a fractal tree in java, the DB iam working on is using B+ tree, is there any java implementation for fractal trees? i will be thankful for any help.