A B+ Tree in Go

This is an effort to create an example B+Tree library in go.

Here is a good B Tree visualization

Why do this?

• Interesting intellectual exercise
• Opportunity to think about design choices
• Good way to learn about how btrees work
  • B+Trees and their associated methods are fundamental to databases and filesystems.
  • SQL Databases need proper indexes (btrees). Go here
• Very good way to practice writing Go code
• Opportunity to learn how to do the tricky things the Go way
  • Granular locking
  • Smart disk IO
  • Concurrency
  • Message passing
• Practice rewriting big chunks of code. Good code is always the product of iteration.
• Maybe create something that someone finds useful

Architecture and approach to design

It's fairly primitive. I read and studied algorithms and then made a stab at implementation.

• Layout like a very plain Go library
• Implement some testing early on
• Choose public-facing and private methods
• Use recursion (it's a tree, after all)
• Get something working.
  • Doesn't have to be pretty to start with.
  • It is just code. You can change it.

To Do List

1. Get Find working (done)
2. Insert working (done)
3. Implement locking and concurrent access
4. Get delete working
5. Get update working
6. Implement some range queries
7. Some better encapsulation (get rid of Init())
8. Move to disk-based storage