B-tree implementation for Go

Overview

btree

made-with-Go made-with-Go MIT license PRs Welcome amit-davidson

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.

You might also like...
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

an R-Tree library for Go

rtreego A library for efficiently storing and querying spatial data in the Go programming language. About The R-tree is a popular data structure for e

Just an itsy bitsy b-tree in Go

tinybtree Just an itsy bitsy b-tree. Usage Keys are strings, values are interfaces. Functions Get(key string) (value interface{}, gotten bool) Set(key

Tree algorithms in Golang

Tree Algorithms in Golang This is my humble attempt to share some of the tree algorithms in Golang. Pull requests are always welcome! :) Contents Tree

Simple code just to try out and Binary Tree on Golang.

Character counter | ▮▮▮▮▮▮▮▮ Simple code just to try out and Binary Tree on Golang. Count characters to train openning a file and reading it, as well

Golang channel example with equivalent binary tree
Golang channel example with equivalent binary tree

golang_channel_example_with_equivalent_binary_tree Exercise: Equivalent Binary Trees There can be many different binary trees with the same sequence o

Segment tree for bytes in Go

bsegtree Segment tree for bytes in Go Based on Thomas Oberndörfer's int range segment tree with fixing/optimization/modification for bytes ranges. For

A project that deals with implementations of a binary tree

Binary Search Tree This is a project that deals with implementations of a binary tree and the following functions. Print Prints the entire tree. Argum

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

IAVL+ Tree Note: Requires Go 1.13+ A versioned, snapshottable (immutable) AVL+ tree for persistent data. The purpose of this data structure is to prov

Comments
  • Impossible combination after few insertions (2-3 tree)

    Impossible combination after few insertions (2-3 tree)

    	minimumItemsInNode := 1
    	tree := NewTree(minimumItemsInNode)
    
    	for i := 1; i < 100; i++ {
    		value := strconv.Itoa(i)
    		tree.Put(value, value)
    		tree.Find(value)
    	}
    

    used while creating B-tree of 2-3 structure, creates impossible combination of 6 | \ \ (3), (5, 8), (7) Is there something I am missing? This should be contradicted even while it has 1 element at the root (6). Is there an inner constraint for "ignoring" childs without removing the references? That was my guess shot.

    opened by wortelus 3
Owner
Amit Davidson
Gopher, Distributed Systems, Computer Science Student
Amit Davidson
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 31 Nov 3, 2022
An yet-another red-black tree implementation, with a C++ STL-like API.

A red-black tree with an API similar to C++ STL's. INSTALLATION go get github.com/yasushi-saito/rbtree EXAMPLE More examples can be fou

Yasushi Saito 18 Apr 25, 2022
An R-tree implementation for Go

rtree This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacement

Josh Baker 236 Dec 29, 2022
An immutable radix tree implementation in Golang

go-immutable-radix Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimi

HashiCorp 859 Dec 29, 2022
B-tree implementation for Go

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 do

Amit Davidson 214 Dec 31, 2022
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 4 Mar 7, 2022
Go-merkle - Merkle tree implementation in Golang

go-merkle go-merkle implements a simple merkle tree in Golang. It allows to obta

atomixwap 2 Aug 8, 2022
A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees

radixs A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees. This implemen

Bruno Moura 0 Feb 14, 2022
An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

A.Samet İleri 15 Jul 1, 2022
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022