btree

btree is a Go implementation of a B-Tree. This project is intended for learning purposes so the code is relatively small (<500LOC) and highly documented. It means it can be a good starting point for people interested in data structures or how databases work.

You can checkout my blog post about the implementation and deep cover about B trees and databases

Installing

To start using btree, install Go and run go get:

$ go get -u github.com/amit-davidson/btree

Usage

package main

import "fmt"

func main()  {
	minimumItemsInNode := DefaultMinItems
	tree := NewTree(minimumItemsInNode)
	value := "0"
	tree.Put(value, value)

	retVal := tree.Find(value)
	fmt.Printf("Returned value is key:%s value:%s \n", retVal.key, retVal.value)

	tree.Remove(value)

	retVal = tree.Find(value)
	fmt.Print("Returned value is nil")
}

Reading the source code

The best places to start are the operations on the tree:

• tree.Find() - Find Returns an item according based on the given key by performing a binary search.

• tree.Put() - Put adds a key to the tree. It finds the correct node and the insertion index and adds the item. When performing the search, the ancestors are returned as well. This way we can iterate over them to check which nodes were modified and rebalance by splitting them accordingly. If the root has too many items, then a new root of a new layer is created and the created nodes from the split are added as children.

• tree.Remove() - Remove removes a key from the tree. It finds the correct node and the index to remove the item from and removes it. When performing the search, the ancestors are returned as well. This way we can iterate over them to check which nodes were modified and rebalance by rotating or merging the unbalanced nodes. Rotation is done first and if the siblings doesn't have enough items, then merging occurs. If the root is without items after a split, then the root is removed and the tree is one level shorter.