Repository files navigation

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 orhow databases work.

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

To start using btree, install Go and rungo get:

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

package mainimport"fmt"funcmain()  {minimumItemsInNode:=DefaultMinItemstree:=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")}

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 thesearch, the ancestors are returned as well. This way we can iterate over them to check which nodes were modified andrebalance by splitting them accordingly. If the root has too many items, then a new root of a new layer iscreated 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 whichnodes were modified and rebalance by rotating or merging the unbalanced nodes. Rotation is done first and if thesiblings doesn't have enough items, then merging occurs. If the root is without items after a split, then the root isremoved and the tree is one level shorter.