lsmt

README

LSM-Tree

A simplified Golang implementation for log structured merge tree. Put and Get are supported. Compaction is also supported. Data is only stored in memory. Disk files are simulated by in-memory byte arrays. See https://eileen-code4fun.medium.com/log-structured-merge-tree-lsm-tree-implementations-a-demo-and-leveldb-d5e028257330 for a more elaborate documentation and how this compares to LevelDB.

Documentation

Index

• func Upsert(tree **TreeNode, elem Element)
• type DiskFile
  • func NewDiskFile(elems []Element) DiskFile
  • func (d DiskFile) AllElements() []Element
  • func (d DiskFile) Empty() bool
  • func (d DiskFile) Search(key string) (Element, error)
• type Element
  • func Find(tree *TreeNode, key string) (Element, error)
  • func JustLarger(tree *TreeNode, key string) (Element, error)
  • func JustSmallerOrEqual(tree *TreeNode, key string) (Element, error)
  • func Traverse(tree *TreeNode) []Element
• type LSMTree
  • func NewLSMTree(flushThreshold int) *LSMTree
  • func (t *LSMTree) Get(key string) (string, error)
  • func (t *LSMTree) Put(key, value string)
• type TreeNode
  • func NewTree(elems []Element) *TreeNode

Functions

func Upsert

func Upsert(tree **TreeNode, elem Element)

Types

type DiskFile

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

func NewDiskFile

func NewDiskFile(elems []Element) DiskFile

func (DiskFile) AllElements

func (d DiskFile) AllElements() []Element

func (DiskFile) Empty

func (d DiskFile) Empty() bool

func (DiskFile) Search

func (d DiskFile) Search(key string) (Element, error)

type Element

type Element struct {
	Key, Value string
}

func Find

func Find(tree *TreeNode, key string) (Element, error)

func JustLarger

func JustLarger(tree *TreeNode, key string) (Element, error)

func JustSmallerOrEqual

func JustSmallerOrEqual(tree *TreeNode, key string) (Element, error)

func Traverse

func Traverse(tree *TreeNode) []Element

Traverse returns all the elements in key order.

type LSMTree

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

func NewLSMTree

func NewLSMTree(flushThreshold int) *LSMTree

func (*LSMTree) Get

func (t *LSMTree) Get(key string) (string, error)

func (*LSMTree) Put

func (t *LSMTree) Put(key, value string)

type TreeNode

type TreeNode struct {
	Elem  Element
	Left  *TreeNode
	Right *TreeNode
	Size  int
}

func NewTree

func NewTree(elems []Element) *TreeNode

NewTree accepts a sorted element slice and returns a binary tree representation.