btree

README

GO BTree

A fast, simple disk based BTree implementation in Go.

https://pkg.go.dev/github.com/guycipher/btree

Features

• Easy to use API with Put, Get, Delete, Remove, Iterator, Range methods
• Disk based storage with underlying pager
• Supports keys with multiple values
• Supports large keys and values

Extra features

• NGet get's keys not equal to the key
• NRange get's keys not equal to provided range
• GreaterThan get's keys greater than the provided key
• GreaterThanEq get's keys greater than or equal to the provided key
• LessThan get's keys less than the provided key
• LessThanEq get's keys less than or equal to the provided key

goos: linux
goarch: amd64
pkg: github.com/guycipher/btree
cpu: 11th Gen Intel(R) Core(TM) i7-11700K @ 3.60GHz
BenchmarkBTree_Put
BenchmarkBTree_Put-16    	   10000	    125006 ns/op

[!WARNING] Not thread safe. You must handle concurrency control yourself.

Usage

Importing

import "github.com/guycipher/btree"

Creating a new BTree

You can use the Open method to open an existing btree or create a new one. You can specify the file name, flags, file mode, and the degree of the btree.

bt, err := btree.Open("btree.db", os.O_CREATE|os.O_RDWR, 0644, 3)
if err != nil {
..
}

Inserting a key-value pair

You can insert a value into a key using the Put method. Keys can store many values.

err := bt.Put([]byte("key"), []byte("value"))
if err != nil {
..
}

Getting a value

To get a value you can you the Get method. The get method will return all the keys values.

values, err := bt.Get([]byte("key"))
if err != nil {
..
}

NGet

To get all keys not equal to the key you can use the NGet method.

keys, err := bt.NGet([]byte("key"))
if err != nil {
..
}

GreaterThan

To get all keys greater than the key you can use the GreaterThan method.

keys, err := bt.GreaterThan([]byte("key"))
if err != nil {
..
}

GreaterThanEq

To get all keys greater than or equal to the key you can use the GreaterThanEq method.

keys, err := bt.GreaterThanEq([]byte("key"))
if err != nil {
..
}

LessThan

To get all keys less than the key you can use the LessThan method.

keys, err := bt.LessThan([]byte("key"))
if err != nil {
..
}

LessThanEq

To get all keys less than or equal to the key you can use the LessThanEq method.

keys, err := bt.LessThanEq([]byte("key"))
if err != nil {
..
}

Deleting a key

To delete a key and all of it's values you can use the Delete method.

err := bt.Delete([]byte("key"))
if err != nil {
..
}

Removing a value within key

To remove a value from a key you can use the Remove method.

err := bt.Remove([]byte("key"), []byte("value"))
if err != nil {
..
}

Key Iterator

The iterator is used to iterate over values of a key

iterator := key.Iterator()

for {
    value, ok := iterator()
    if !ok {
        break
    }

    fmt.Println(string(value))
}

Result

value1
value2
value3

Range query

Get all keys between key1 and key3

keys, err := bt.Range([]byte("key1"), []byte("key3"))
if err != nil {
..
}

Not Range query

Get all keys not between key1 and key3

keys, err := bt.NRange([]byte("key1"), []byte("key3"))
if err != nil {
..
}

Closing the BTree

You can close the BTree by calling the Close function. This will close the underlying file and free up resources.

err := bt.Close()
if err != nil {
..
}

Technical Details

This is an on disk btree implementation. This btree has an underlying pager that handles reading and writing nodes to disk as well as overflows. When an overflow is required for a page the overflow is created and the data is split between however many pages. When a page gets deleted its page number gets placed into an in-memory slice as well as gets written to disk. These deleted pages are reused when new pages are needed.

A key on this btree can store many values. Mind you a keys values are read into memory; So if you have a key like A with values Alex, Alice, Adam, and you call Get(A) all of those values will be read into memory. You can use a key iterator to iterate over the values of a key.

The btree is not thread safe. You must handle concurrency control yourself.

You can play with page size and degree(T) to see how it affects performance. My recommendation is a smaller page size and smaller degree for faster reads and writes.

License

View the LICENSE file

Documentation

Overview

Package btree pager BSD 3-Clause License

Copyright (c) 2024, Alex Gaetano Padula All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Package btree pager BSD 3-Clause License

Copyright (c) 2024, Alex Gaetano Padula All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• Constants
• type BTree
  • func Open(name string, flag, perm int, t int) (*BTree, error)
  • func (b *BTree) Close() error
  • func (b *BTree) Delete(k []byte) error
  • func (b *BTree) Get(k []byte) (*Key, error)
  • func (b *BTree) GreaterThan(k []byte) ([]*Key, error)
  • func (b *BTree) GreaterThanEq(k []byte) ([]*Key, error)
  • func (b *BTree) InOrderTraversal() ([]*Key, error)
  • func (b *BTree) LessThan(k []byte) ([]*Key, error)
  • func (b *BTree) LessThanEq(k []byte) ([]*Key, error)
  • func (b *BTree) NGet(k []byte) ([]*Key, error)
  • func (b *BTree) NRange(start, end []byte) ([]*Key, error)
  • func (b *BTree) PrintTree() error
  • func (b *BTree) Put(key, value []byte) error
  • func (b *BTree) Range(start, end []byte) ([]interface{}, error)
  • func (b *BTree) Remove(key, value []byte) error
• type Key
  • func (k *Key) Iterator() func() ([]byte, bool)
• type Node
• type Pager
  • func OpenPager(filename string, flag int, perm os.FileMode, syncInterval time.Duration) (*Pager, error)
  • func (p *Pager) Close() error
  • func (p *Pager) Count() int64
  • func (p *Pager) DeletePage(pageID int64) error
  • func (p *Pager) GetDeletedPages() []int64
  • func (p *Pager) GetPage(pageID int64) ([]byte, error)
  • func (p *Pager) Write(data []byte) (int64, error)
  • func (p *Pager) WriteTo(pageID int64, data []byte) error

Constants

const HEADER_SIZE = 16 // next (overflowed)

const PAGE_SIZE = 1024 // Page size

Types

type BTree

type BTree struct {
	Pager *Pager // The pager for the btree
	T     int    // The order of the tree
}

BTree is the main BTree struct ** not thread safe

func Open

func Open(name string, flag, perm int, t int) (*BTree, error)

Open opens a new or existing BTree

func (*BTree) Close

func (b *BTree) Close() error

Close closes the BTree

func (*BTree) Delete

func (b *BTree) Delete(k []byte) error

Delete deletes a key from the BTree

func (*BTree) Get

func (b *BTree) Get(k []byte) (*Key, error)

Get returns the values associated with a key

func (*BTree) GreaterThan

func (b *BTree) GreaterThan(k []byte) ([]*Key, error)

GreaterThan returns all keys greater than k

func (*BTree) GreaterThanEq

func (b *BTree) GreaterThanEq(k []byte) ([]*Key, error)

GreaterThanEq returns all keys greater than or equal to k

func (*BTree) InOrderTraversal

func (b *BTree) InOrderTraversal() ([]*Key, error)

InOrderTraversal returns all keys in the BTree in order

func (*BTree) LessThan

func (b *BTree) LessThan(k []byte) ([]*Key, error)

LessThan returns all keys less than k

func (*BTree) LessThanEq

func (b *BTree) LessThanEq(k []byte) ([]*Key, error)

LessThanEq returns all keys less than or equal to k

func (*BTree) NGet

func (b *BTree) NGet(k []byte) ([]*Key, error)

NGet gets all keys not equal to k

func (*BTree) NRange

func (b *BTree) NRange(start, end []byte) ([]*Key, error)

NRange returns all keys not within the range [start, end]

func (*BTree) PrintTree

func (b *BTree) PrintTree() error

PrintTree prints the tree (for debugging purposes ****)

func (*BTree) Put

func (b *BTree) Put(key, value []byte) error

Put inserts a key into the BTree A key can have multiple values Put inserts a key value pair into the BTree

func (*BTree) Range

func (b *BTree) Range(start, end []byte) ([]interface{}, error)

Range returns all keys in the BTree that are within the range [start, end]

func (*BTree) Remove

func (b *BTree) Remove(key, value []byte) error

Remove removes a value from key

type Key

type Key struct {
	K []byte   // The key
	V [][]byte // The values
}

Key is the key struct for the BTree

func (*Key) Iterator

func (k *Key) Iterator() func() ([]byte, bool)

Iterator returns an iterator for a key

type Node

type Node struct {
	Page     int64   // The page number of the node
	Keys     []*Key  // The keys in node
	Children []int64 // The children of the node
	Leaf     bool    // If the node is a leaf node
}

Node is the node struct for the BTree

type Pager

type Pager struct {
	// contains filtered or unexported fields
}

Pager manages pages in a file

func OpenPager

func OpenPager(filename string, flag int, perm os.FileMode, syncInterval time.Duration) (*Pager, error)

OpenPager opens a file for page management

func (*Pager) Close

func (p *Pager) Close() error

Close closes the file

func (*Pager) Count

func (p *Pager) Count() int64

Count returns the number of pages

func (*Pager) DeletePage

func (p *Pager) DeletePage(pageID int64) error

DeletePage deletes a page

func (*Pager) GetDeletedPages

func (p *Pager) GetDeletedPages() []int64

GetDeletedPages returns the list of deleted pages

func (*Pager) GetPage

func (p *Pager) GetPage(pageID int64) ([]byte, error)

GetPage gets a page and returns the data Will gather all the pages that are linked together

func (*Pager) Write

func (p *Pager) Write(data []byte) (int64, error)

Write writes data to the next available page

func (*Pager) WriteTo

func (p *Pager) WriteTo(pageID int64, data []byte) error

WriteTo writes data to a specific page