shs

README

https://github.com/zcbenz/BPlusTree https://github.com/wspeirs/btree https://blog.csdn.net/weixin_46117680/article/details/140841684 https://www.cnblogs.com/wuzhenzhao/p/10341114.html https://blog.csdn.net/weixin_37870870/article/details/124285834 https://blog.csdn.net/qq_45473439/article/details/123445631

Documentation

Index

• Constants
• Variables
• type BTreeIndex
  • func NewBTreeIndex() *BTreeIndex
  • func (B *BTreeIndex) Delete(key []byte) error
  • func (B *BTreeIndex) Get(key []byte) (uint64, error)
  • func (B *BTreeIndex) Iterator() iter.Seq2[[]byte, uint64]
  • func (B *BTreeIndex) Set(key []byte, value uint64) error
• type DataPage
• type DefaultIndex
  • func NewDefaultIndex() *DefaultIndex
  • func (d *DefaultIndex) Delete(key []byte) error
  • func (d *DefaultIndex) Get(key []byte) (uint64, error)
  • func (d *DefaultIndex) Iterator() iter.Seq2[[]byte, uint64]
  • func (d *DefaultIndex) Set(key []byte, value uint64) error
• type Index
• type Options
• type RBTreeIndex
  • func NewRBTreeIndex() *RBTreeIndex
  • func (R *RBTreeIndex) Delete(key []byte) error
  • func (R *RBTreeIndex) Get(key []byte) (uint64, error)
  • func (R *RBTreeIndex) Iterator() iter.Seq2[[]byte, uint64]
  • func (R *RBTreeIndex) Set(key []byte, value uint64) error
• type Record
• type SkipListIndex
  • func NewSkipListIndex() *SkipListIndex
  • func (s *SkipListIndex) Delete(key []byte) error
  • func (s *SkipListIndex) Get(key []byte) (uint64, error)
  • func (s *SkipListIndex) Iterator() iter.Seq2[[]byte, uint64]
  • func (s *SkipListIndex) Set(key []byte, value uint64) error
• type SortUserRecordByKey
  • func (s SortUserRecordByKey) Len() int
  • func (s SortUserRecordByKey) Less(i, j int) bool
  • func (s SortUserRecordByKey) Swap(i, j int)
• type StorageEngine
  • func NewStorageEngine(opt Options) (*StorageEngine, error)
  • func (se *StorageEngine) Close() error
  • func (se *StorageEngine) Delete(key []byte) error
  • func (se *StorageEngine) Get(key []byte) ([]byte, error)
  • func (se *StorageEngine) Insert(key, value []byte) error
  • func (se *StorageEngine) Modify(key, value []byte) error
• type WalRecord
• type WalRecordType

Constants

const (
	PageSize        = 4096
	PageHeaderSize  = 16
	FileTrailerSize = 8
)

Variables

var (
	ErrKeyNotFound    = fmt.Errorf("key not found")
	ErrKeyEmpty       = fmt.Errorf("key cannot be empty")
	ErrRecordTooLarge = fmt.Errorf("key or value is too large, the size cannot exceed 4056")
)

Types

type BTreeIndex

type BTreeIndex btree.Map[string, uint64]

func NewBTreeIndex

func NewBTreeIndex() *BTreeIndex

func (*BTreeIndex) Delete

func (B *BTreeIndex) Delete(key []byte) error

func (*BTreeIndex) Get

func (B *BTreeIndex) Get(key []byte) (uint64, error)

func (*BTreeIndex) Iterator

func (B *BTreeIndex) Iterator() iter.Seq2[[]byte, uint64]

func (*BTreeIndex) Set

func (B *BTreeIndex) Set(key []byte, value uint64) error

type DataPage

type DataPage struct {
	PageID          uint64   // 页号，页号是PageHeader的一部分
	UserRecordsSize uint64   // 用户记录总大小，是PageHeader的一部分
	UserRecords     []Record // 用户记录
	FileTrailer     [8]byte  // crc
}

DataPage 表示一个数据页

type DefaultIndex

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

func NewDefaultIndex

func NewDefaultIndex() *DefaultIndex

func (*DefaultIndex) Delete

func (d *DefaultIndex) Delete(key []byte) error

func (*DefaultIndex) Get

func (d *DefaultIndex) Get(key []byte) (uint64, error)

func (*DefaultIndex) Iterator

func (d *DefaultIndex) Iterator() iter.Seq2[[]byte, uint64]

func (*DefaultIndex) Set

func (d *DefaultIndex) Set(key []byte, value uint64) error

type Index

type Index interface {
	Get(key []byte) (uint64, error)
	Set(key []byte, value uint64) error
	Delete(key []byte) error
	Iterator() iter.Seq2[[]byte, uint64]
}

type Options

type Options struct {
	DirPath   string
	DataIndex Index
}

type RBTreeIndex

type RBTreeIndex rbtree.RbTree[string, uint64]

func NewRBTreeIndex

func NewRBTreeIndex() *RBTreeIndex

func (*RBTreeIndex) Delete

func (R *RBTreeIndex) Delete(key []byte) error

func (*RBTreeIndex) Get

func (R *RBTreeIndex) Get(key []byte) (uint64, error)

func (*RBTreeIndex) Iterator

func (R *RBTreeIndex) Iterator() iter.Seq2[[]byte, uint64]

func (*RBTreeIndex) Set

func (R *RBTreeIndex) Set(key []byte, value uint64) error

type Record

type Record struct {
	Key   []byte
	Value []byte
}

Record 表示一个记录

type SkipListIndex

type SkipListIndex skiplist.Skiplist[string, uint64]

func NewSkipListIndex

func NewSkipListIndex() *SkipListIndex

func (*SkipListIndex) Delete

func (s *SkipListIndex) Delete(key []byte) error

func (*SkipListIndex) Get

func (s *SkipListIndex) Get(key []byte) (uint64, error)

func (*SkipListIndex) Iterator

func (s *SkipListIndex) Iterator() iter.Seq2[[]byte, uint64]

func (*SkipListIndex) Set

func (s *SkipListIndex) Set(key []byte, value uint64) error

type SortUserRecordByKey

type SortUserRecordByKey []Record

func (SortUserRecordByKey) Len

func (s SortUserRecordByKey) Len() int

func (SortUserRecordByKey) Less

func (s SortUserRecordByKey) Less(i, j int) bool

func (SortUserRecordByKey) Swap

func (s SortUserRecordByKey) Swap(i, j int)

type StorageEngine

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

func NewStorageEngine

func NewStorageEngine(opt Options) (*StorageEngine, error)

NewStorageEngine 创建一个新的存储引擎实例，并从磁盘加载数据

func (*StorageEngine) Close

func (se *StorageEngine) Close() error

func (*StorageEngine) Delete

func (se *StorageEngine) Delete(key []byte) error

Delete 删除一个键值对，并保存到磁盘

func (*StorageEngine) Get

func (se *StorageEngine) Get(key []byte) ([]byte, error)

Get 获取一个键对应的值

func (*StorageEngine) Insert

func (se *StorageEngine) Insert(key, value []byte) error

Insert 插入一个键值对，并保存到磁盘

func (*StorageEngine) Modify

func (se *StorageEngine) Modify(key, value []byte) error

Modify 修改一个键值对

type WalRecord

type WalRecord struct {
	Type   WalRecordType
	Key    []byte
	PageID uint64
}

type WalRecordType

type WalRecordType uint8

const (
	WalOpInsert WalRecordType = iota
	WalOpDelete
)