DIY an on-disk B+ Tree

/*
Simple Persistent B Plus Tree.
Node keys are assumed to be signed integers and values also.
Persistence is achieved using a naive bufio.Writer + flush.
Concurrency control using a simple globally blocking RWMutex lock.

B-Tree implementations have many implementation specific details 
and optimisations before they're 'production' ready, notably they 
may use a free-list to hold 'free' pages and employ 
sophisticated concurrency control. 
see also: CoW semantics, buffering, garbage collection etc

// learn more:
// etcd: https://pkg.go.dev/github.com/google/btree
// sqlite: https://sqlite.org/src/file/src/btree.c
// wiki: https://en.wikipedia.org/wiki/B%2B_tree
*/

const (
	MAX_DEGREE = 3
)

const (
	ROOT_NODE NodeType = iota + 1
	INTERNAL_NODE
	LEAF_NODE
)

type BTree struct {
	root *Node
}

type Node struct {
	kind     NodeType
	// maintaining a parent pointer is expensive
	// in internal nodes especially
	parent   *Node
	keys     []int
	children []*Node
	data     []int

	// sibling pointers these help with deletions + range queries
	next     *Node
	previous *Node
}

func (n *Node) basicSearch(key int) *Node {
	if len(n.children) == 0 {
// you are at a leaf Node and can now access stuff
// or this is the leaf node that should contain stuff
		return n
	}

	low, high := 0, len(n.keys)-1
	for low <= high {
		mid := low + (high-low)/2
		if n.keys[mid] == key {
			return n
		} else if n.keys[mid] < key {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}

	return n.children[low]
}

func (n *node) split(midIdx int) error {
// first find a leaf node.
// every node except the root node must respect the inquality:
// branching factor - 1 <= num keys < (2 * branching factor) - 1

// if this doesn't make sense ignore it. The take away:
// every node except root has a min/max num keys or it's invalid.

// edge case, how to handle the root node?

// node is full: promotion time, split keys into two halves
	splitPoint := n.keys[midIdx]
	leftKeys := n.keys[:midIdx]
	rightKeys := n.keys[midIdx:]

	n.keys = []int{splitPoint}

	leftNode := &node{kind: LEAF_NODE, keys: leftKeys}
	rightNode := &node{kind: LEAF_NODE, keys: rightKeys}
	n.children = []*node{leftNode, rightNode}


// -- LEAF
//  (internal node(left))  (internal node(right))
//   \               /
//   (current leaf node)


// recurse UP from curr to node which may overflow,
// check that we're not full if full, we split
// again allocate a new node(s)
// --snipped for clarity
	return nil
}

func (n *Node) merge(sibling *Node, key int) error {
	// delete data from leaf node
	// steal sibiling fist, if underfull --snipped
	// do stuff to prepare for merging, assume we _can_ merge

	// deallocate/collapse underflow node
	sibling.data = append(sibling.data, n.data...)

	for i, node := range sibling.parent.children {
		if node == n {
			n.parent.children = append(n.parent.children[:i], n.parent.children[i+1:]...)
		}
	}

	// recurse UPWARD and check for underflow
	for i, k := range sibling.parent.keys {
		if k == key {
			sibling.parent.keys = cut(i, sibling.parent.keys)

			if len(n.parent.keys) < int(math.Ceil(float64(MAX_DEGREE)/2)) {
					f sibling, _, err := sibling.parent.preMerge(); err == nil {
					return n.parent.mergeSibling(t, sibling, key)
				}
			} else {
				return nil
			}
		}

	return nil
}

// Page is (de)serialised disk block similar to: https://doxygen.postgresql.org/bufpage_8h_source.html
// It is a contigous 4kiB chunk of memory, both a logical and physical representation of data.
type Page struct {
	header header

	cellPointers []int16
	cells        []cell
}

type pageHeader struct {
	// Represents a marker value to indicate that a file is a Bolt DB.
	// copy/pasta as a magic number is 'magic' and kind of madeup.
	magic     uint32 // 4 bytes
	PageID    uint32 // 4 bytes
	Reserve   uint32 // 4 bytes

	FreeSlots uint16 // 2 bytes
	// the physical offset mapping to the begining
	// and end of an allocated block on the datafile for this page
	PLower    uint16 // 2 bytes
	PHigh     uint16 // 2 bytes
	NumSlots  byte   // 1 byte (uint8)

	// all cells are of type CellLayout ie is key/pointer or key/value cell?
	CellLayout byte // 1 byte (uint8)
	pageType   byte

}

type cell struct {
	cellId    int16
	keySize   uint64
	valueSize uint64
	keys      []byte
	data      []byte
}

func (p *Page) Flush(datafile *os.File) error {
	buf := new(bytes.Buffer)

	_, _ := datafile.Seek(int64(p.PLower), io.SeekStart)

	binary.Write(buf, binary.LittleEndian, &p.pageHeader)
	binary.Write(buf, binary.LittleEndian, &p.cellPointers)
	binary.Write(buf, binary.LittleEndian, &p.cells)

	buf.WriteTo(datafile)
	datafile.Sync()

	log.Printf("written %v bytes to disk at pageID %v", n, p.PageID)
	return nil
}

const pageDictionary map[int]int 
// --snipped, tldr; hashmap conceptually
// maps the page ID to an actual offset

func Fetch(pageId int, datafile *os.File) (Page, error) {
	var page Page

	datafile.Seek(pageDictionary[pageID], io.SeekStart)
	err := binary.Read(datafile, binary.LittleEndian, &page.pageHeader)

	return page, nil
}

const magic uint32 = 0xED0CDAED