Skip to content

Disk-Based Binary Search Tree (BST) for LSM Key-Value Store

Notifications You must be signed in to change notification settings

ashwaniYDV/diskbst

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Disk-Based Binary Search Tree (BST) for LSM Key-Value Store

This implementation provides a simple disk-based binary search tree (BST) that can be used in an LSM key-value store to serialize a memtable to disk.

1. Node Structure (node.go)

  • Each node in the BST contains:
    • key: The key as a byte slice.
    • value: The value associated with the key.
    • leftChild: Offset in the file where the left child node is stored.
    • rightChild: Offset in the file where the right child node is stored.
  • Nodes can be serialized to a byte slice for storage on disk and deserialized from a byte slice when reading from disk.

2. Writer (writer.go)

  • The writer handles inserting key-value pairs into the BST and writing them to a file.
  • Key Functions:
    • OpenWriter(pathName string): Opens or creates a new file for writing the BST. The file is validated with a magic number to ensure it's a valid BST file.
    • Put(key []byte, value []byte): Inserts a key-value pair into the BST. It writes the new node to the disk and links it to its parent.
    • findPos(key []byte): Finds the position in the file where a new node should be inserted.
    • Close(): Closes the file after writing.

3. Reader (reader.go)

  • The reader uses memory-mapped I/O for fast access to the data, allowing the file to be accessed through a byte slice in memory
  • Key Functions:
    • OpenReader(pathName string): Opens the file for reading and validates it with a magic number.
    • Get(key []byte): Searches the BST for a key and returns the associated value.
    • Close(): Unmaps the memory-mapped file.

Example usage:

package main

import (
	"fmt"
	"github.com/ashwaniYDV/diskbst"
)

func main() {
	memtable := map[string][]byte{
		"key1": []byte("value1"),
		"key2": []byte("value2"),
		"key3": []byte("value3"),
	}

	// Open a new file to store the tree
	writer, _ := diskbst.OpenWriter("./test.bst")

	// Store all key-value pairs in the tree
	for key, val := range memtable {
		_ = writer.Put([]byte(key), val)
	}

	writer.Close()

	// Open a reader for the tree
	// the tree file will be memory-mapped
	reader, _ := diskbst.OpenReader("./test.bst")
	defer reader.Close()

	val, _ := reader.Get([]byte("key1"))
	fmt.Println(string(val)) // value1

	_, err := reader.Get([]byte("non_existent_key"))
	fmt.Println(err.Error()) // key not found
}

Limitations of current approach (Further improvements)

  • If a key already exists, then it's not overwritten
  • Binary tree is not self-balanced

About

Disk-Based Binary Search Tree (BST) for LSM Key-Value Store

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages