Exotic Functional Data Structures: Hitchhiker Trees
summary
Hitchhiker trees are an open‑source, functionally persistent fractal tree that uses path copying plus per‑node buffers on index nodes to turn many small writes into batched IO and cut average IOs (demo goes from 12 to 5 total IOs for a sample workload). Implementation lives in the datacrypt project on GitHub, written in Clojure with pluggable backends (Redis, JDBC, S3). The outboard API stores application state off‑heap in Redis enabling free snapshots and much faster process restarts.
AI-written summary · about
chapters (28)
- 0:00Intro
- 0:44Functional Data Structures
- 1:46How to fix this?
- 2:18A List of Fruit
- 2:34Mutation in an Immutable World
- 3:39Pointers!
- 4:41Pointers and Sharing
- 5:37Editing the Linked List
- 6:09Worse Case Performance
- 6:36Philosophy of Identity
- 8:24Binary Search Trees
- 10:44Performance Analysis/Algebra
- 13:45Properties of Trees
- 17:43B Trees are Optimal for Reads
- 21:09B+ Tree
- 22:49Fractal Trees
- 23:44Appending to a Log
- 24:49Fractal Insertion
- 25:17Walking Through Insertions
- 28:34Find the Path
- 28:50Project Pending Operations
- 29:40Broken for Scans
- 30:26Only Project Values Within Range
- 31:07Path Copying or Not!
- 32:22Flush Control
- 35:24Real Branching Factors
- 37:15Datacrypt is Pluggable
- 38:41Outboard
related talks
48mA Helicopter Tour of Purely Functional Data Structures
01h 16mOn-Disk Data Structures: B-Trees, LSM-Trees and Fractal Trees
40m"Gaining Constant time Lookup over Unorganized Data"
55mHazelcast - Hitchhiker’s Guide. Grzegorz Piwowarek. Java Fest 2020 Online
26mFiretomic
20mAlternative Data Structures in Ruby
34mLightweight Relations
01h 08mDistributed Java Databases Under the Hood