Skip to content

Instantly share code, notes, and snippets.

@scottcagno

scottcagno/bplus.go

Last active March 26, 2021 17:02
Show Gist options
  • Save scottcagno/52f02dab8f83a0807e8d to your computer and use it in GitHub Desktop.
Save scottcagno/52f02dab8f83a0807e8d to your computer and use it in GitHub Desktop.
Download ZIP
b+ tree, hand transposed from c
Raw
bplus.go
/*
* // Copyright (c) 2021. Scott Cagno. All rights reserved.
* // Use of this source code is governed by a BSD-style (clause 3)
* // license that can be found in the root of this project in the LICENSE file.
*/
package bptree
import (
"bytes"
"log"
"unsafe"
)
const ORDER = 32
type KeyType = []byte
type ValType = []byte
/*
* node represents a node of the Tree
*/
type node struct {
numKeys int
keys [ORDER - 1]KeyType
pointers [ORDER]unsafe.Pointer
parent *node
isLeaf bool
}
func (n *node) hasKey(key KeyType) bool {
if n.isLeaf {
for i := 0; i < n.numKeys; i++ {
if bytes.Equal(key, n.keys[i]) {
return true
}
}
}
return false
}
func (n *node) record(key KeyType) (*Record, bool) {
if n.isLeaf {
for i := 0; i < n.numKeys; i++ {
if bytes.Equal(key, n.keys[i]) {
return (*Record)(n.pointers[i]), true
}
}
}
return nil, false
}
/*
* Record represents a Record pointed to by a leaf node
*/
type Record struct {
Key KeyType
Value ValType
}
/*
* Tree represents the root of a b+tree
*/
type Tree struct {
root *node
}
// NewTree creates and returns a new tree
func NewTree() *Tree {
return new(Tree)
}
// Has returns a boolean indicating weather or not
// the provided key and associated record exists.
func (t *Tree) Has(key KeyType) bool {
return t.findRecord(key) != nil
}
// Add inserts a new record using the provided key. It
// only inserts and entry if the key does not already exist.
func (t *Tree) Add(key KeyType, value ValType) {
// If the tree is empty, start a new one and return.
if t.root == nil {
t.root = startNewTree(key, &Record{key, value})
return
}
// If the tree already exists, let's see what we
// get when we try to find the correct leaf.
leaf := findLeaf(t.root, key)
if leaf.hasKey(key) {
return // Key already exists! So lets just return.
}
// If the tree already exists and the key has not been
// found, then let's insert it into the tree and return!
if leaf.numKeys < ORDER-1 {
insertIntoLeaf(leaf, key, &Record{key, value})
return
}
// Otherwise, insert, split and balance returning the updated root.
t.root = insertIntoLeafAfterSplitting(t.root, leaf, key, &Record{key, value})
}
// Set inserts a new record using the provided key. It
// only inserts and entry if the key does not already exist.
func (t *Tree) Set(key KeyType, value ValType) {
t.insert(key, value)
}
// Get returns the record for a given key if it exists
func (t *Tree) Get(key KeyType) *Record {
return t.findRecord(key)
}
func (t *Tree) Del(key KeyType) {
t.delete(key)
}
func (t *Tree) Range(iter func(r *Record) bool) {
c := findFirstLeaf(t.root)
if c == nil {
return
}
var record *Record
for {
for i := 0; i < c.numKeys; i++ {
record = (*Record)(c.pointers[i])
if record != nil && !iter(record) {
continue
}
}
if c.pointers[ORDER-1] != nil {
c = (*node)(c.pointers[ORDER-1])
} else {
break
}
}
}
func (t *Tree) Min() *Record {
c := findFirstLeaf(t.root)
if c == nil {
return nil
}
return (*Record)(c.pointers[0])
}
func (t *Tree) Max() *Record {
c := findLastLeaf(t.root)
if c == nil {
return nil
}
return (*Record)(c.pointers[c.numKeys-1])
}
func (t *Tree) Len() int {
var count int
for n := findFirstLeaf(t.root); n != nil; n = n.nextLeaf() {
count += n.numKeys
}
return count
}
func (t *Tree) Close() {
//t.destroyTree()
t.root = nil
}
/*
* insert is the "master" insertion function.
* Inserts a key and an associated Value into
* the B+ tree, causing the tree to be adjusted
* however necessary to maintain the B+ tree
* properties
*/
func (t *Tree) insert(key KeyType, value ValType) {
/*
* CASE: Tree does not exist yet, start a new tree
*/
if t.root == nil {
t.root = startNewTree(key, &Record{key, value})
return
}
/*
* The current implementation ignores duplicates (will treat it kind of like a set operation)
*/
leaf, recordPointer := t.find(key)
if recordPointer != nil {
/*
* If the key already exists in this tree then proceed to update Value and return
*/
recordPointer.Value = value
return
}
/*
* No Record found, so create a new Record for the Value
*/
//recordPointer = makeRecord(Value)
/*
* CASE: Tree already exists (continue through the rest of the function)
*/
/*
* Leaf has room for the key and recordPointer--insert into leaf and return
*/
if leaf.numKeys < ORDER-1 {
insertIntoLeaf(leaf, key, &Record{key, value})
return
}
/*
* Leaf does not have enough room and needs to be split
*/
t.root = insertIntoLeafAfterSplitting(t.root, leaf, key, &Record{key, value})
return
}
/*
* startNewTree first insertion case: starts a new tree
*/
func startNewTree(key KeyType, pointer *Record) *node {
root := makeLeaf()
root.keys[0] = key
root.pointers[0] = unsafe.Pointer(pointer)
root.pointers[ORDER-1] = nil
root.parent = nil
root.numKeys++
return root
}
/*
* insertIntoNewRoot creates a new root for two subtrees and inserts the appropriate key into the new root
*/
func insertIntoNewRoot(left *node, key KeyType, right *node) *node {
root := makeNode()
root.keys[0] = key
root.pointers[0] = unsafe.Pointer(left)
root.pointers[1] = unsafe.Pointer(right)
root.numKeys++
root.parent = nil
left.parent = root
right.parent = root
return root
}
/*
* insertIntoParent inserts a new node (leaf or internal node) into the tree--returns the root of
* the tree after insertion is complete
*/
func insertIntoParent(root *node, left *node, key KeyType, right *node) *node {
/*
* Case: new root
*/
if left.parent == nil {
return insertIntoNewRoot(left, key, right)
}
/*
* Case: leaf or node. (Remainder of function body.)
* Find the parents pointer to the left node
*/
leftIndex := getLeftIndex(left.parent, left)
/*
* Simple case: the new key fits into the node.
*/
if left.parent.numKeys < ORDER-1 {
return insertIntoNode(root, left.parent, leftIndex, key, right)
}
/* Harder case: split a node in ORDER
* to preserve the B+ tree properties.
*/
return insertIntoNodeAfterSplitting(root, left.parent, leftIndex, key, right)
}
/*
* getLeftIndex helper function used in insertIntoParent to find the index of the parents
* pointer to the node to the left of the key to be inserted
*/
func getLeftIndex(parent, left *node) int {
var leftIndex int
for leftIndex <= parent.numKeys && (*node)(parent.pointers[leftIndex]) != left {
leftIndex++
}
return leftIndex
}
/*
* insertIntoNode inserts a new key and pointer to a node into a node into which these can fit without violating the
* tree's properties
*/
func insertIntoNode(root, n *node, leftIndex int, key KeyType, right *node) *node {
// Consider using copy, it might be better
copy(n.pointers[leftIndex+2:], n.pointers[leftIndex+1:])
copy(n.keys[leftIndex+1:], n.keys[leftIndex:])
/* // ORIG
for i := n.numKeys; i > leftIndex; i-- {
n.pointers[i+1] = n.pointers[i]
n.keys[i] = n.keys[i-1]
}
*/
n.pointers[leftIndex+1] = unsafe.Pointer(right)
n.keys[leftIndex] = key
n.numKeys++
return root
}
/*
* insertIntoNodeAfterSplitting inserts a new key and pointer to a node into a node, causing the nodes
* size to exceed the ORDER, and causing the node to split in two
*/
func insertIntoNodeAfterSplitting(root, oldNode *node, leftIndex int, key KeyType, right *node) *node {
/*
* First create a temp set of keys and pointers to hold everything in ORDER, including
* the new key and pointer, inserted in their correct places--then create a new node
* and copy half of the keys and pointers to the old node and the other half to the new
*/
var i, j int
var tempKeys [ORDER]KeyType //tempKeys := make([]int, ORDER)
var tempPointers [ORDER + 1]unsafe.Pointer //tempPointers := make([]interface{}, ORDER+1)
for i, j = 0, 0; i < oldNode.numKeys+1; i, j = i+1, j+1 {
if j == leftIndex+1 {
j++
}
tempPointers[j] = oldNode.pointers[i]
}
for i, j = 0, 0; i < oldNode.numKeys; i, j = i+1, j+1 {
if j == leftIndex {
j++
}
tempKeys[j] = oldNode.keys[i]
}
tempPointers[leftIndex+1] = unsafe.Pointer(right)
tempKeys[leftIndex] = key
/*
* copy half the keys and pointers to the old node...
*/
split := cut(ORDER)
oldNode.numKeys = 0
for i = 0; i < split-1; i++ {
oldNode.pointers[i] = tempPointers[i]
oldNode.keys[i] = tempKeys[i]
oldNode.numKeys++
}
oldNode.pointers[i] = tempPointers[i]
kPrime := tempKeys[split-1]
/*
* ...create the new node and copy the other half the keys and pointers
*/
newNode := makeNode()
for i, j = i+1, 0; i < ORDER; i, j = i+1, j+1 {
newNode.pointers[j] = tempPointers[i]
newNode.keys[j] = tempKeys[i]
newNode.numKeys++
}
newNode.pointers[j] = tempPointers[i]
newNode.parent = oldNode.parent
/*
* Free up tempPointers and tempKeys
*/
for i = 0; i < ORDER; i++ {
tempKeys[i] = nil // zero values
tempPointers[i] = nil // zero values
}
tempPointers[ORDER] = nil
var child *node
for i = 0; i <= newNode.numKeys; i++ {
child = (*node)(newNode.pointers[i])
child.parent = newNode
}
/* Insert a new key into the parent of the two
* nodes resulting from the split, with
* the old node to the left and the new to the right.
*/
return insertIntoParent(root, oldNode, kPrime, newNode)
}
// insertIntoLeaf inserts a new pointer to a Record and its
// corresponding key into a leaf.
func insertIntoLeaf(leaf *node, key KeyType, pointer *Record) /* *node */ {
var i, insertionPoint int
for insertionPoint < leaf.numKeys && bytes.Compare(leaf.keys[insertionPoint], key) == -1 {
insertionPoint++
}
for i = leaf.numKeys; i > insertionPoint; i-- {
leaf.keys[i] = leaf.keys[i-1]
leaf.pointers[i] = leaf.pointers[i-1]
}
leaf.keys[insertionPoint] = key
leaf.pointers[insertionPoint] = unsafe.Pointer(pointer)
leaf.numKeys++
//return leaf // might not need to return this leaf
}
/*
* insertIntoLeafAfterSplitting inserts a new key and pointer to a new Record into a leaf so as to exceed the tree's
* ORDER, causing the leaf to be split in half
*/
func insertIntoLeafAfterSplitting(root, leaf *node, key KeyType, pointer *Record) *node {
var insertionIndex int
for insertionIndex < ORDER-1 && bytes.Compare(leaf.keys[insertionIndex], key) == -1 {
insertionIndex++
}
var i, j int
var tempKeys [ORDER]KeyType
var tempPointers [ORDER]unsafe.Pointer
for i, j = 0, 0; i < leaf.numKeys; i, j = i+1, j+1 {
if j == insertionIndex {
j++
}
tempKeys[j] = leaf.keys[i]
tempPointers[j] = leaf.pointers[i]
}
tempKeys[insertionIndex] = key
tempPointers[insertionIndex] = unsafe.Pointer(pointer)
leaf.numKeys = 0
split := cut(ORDER - 1)
for i = 0; i < split; i++ {
leaf.keys[i] = tempKeys[i]
leaf.pointers[i] = tempPointers[i]
leaf.numKeys++
}
newLeaf := makeLeaf()
for i, j = split, 0; i < ORDER; i, j = i+1, j+1 {
newLeaf.keys[j] = tempKeys[i]
newLeaf.pointers[j] = tempPointers[i]
newLeaf.numKeys++
}
// free temps
for i = 0; i < ORDER; i++ {
tempKeys[i] = nil // zero Value
tempPointers[i] = nil // zero Value
}
newLeaf.pointers[ORDER-1] = leaf.pointers[ORDER-1]
leaf.pointers[ORDER-1] = unsafe.Pointer(newLeaf)
for i = leaf.numKeys; i < ORDER-1; i++ {
leaf.pointers[i] = nil
}
for i = newLeaf.numKeys; i < ORDER-1; i++ {
newLeaf.pointers[i] = nil
}
newLeaf.parent = leaf.parent
newKey := newLeaf.keys[0]
return insertIntoParent(root, leaf, newKey, newLeaf)
}
/*
* findRecord finds and returns the Record to which a key refers
*/
func (t *Tree) find(key KeyType) (*node, *Record) {
leaf := findLeaf(t.root, key)
if leaf == nil {
return nil, nil
}
/*
* If root/leaf != nil, leaf must have a Value, even if it does not contain the desired key.
* The leaf holds the range of keys that would include the desired key
*/
var i int
for i = 0; i < leaf.numKeys; i++ {
if bytes.Equal(leaf.keys[i], key) {
break
}
}
if i == leaf.numKeys {
return leaf, nil
}
return leaf, (*Record)(leaf.pointers[i])
}
/*
* findRecord finds and returns the Record to which a key refers
*/
func (t *Tree) findRecord(key KeyType) *Record {
leaf := findLeaf(t.root, key)
if leaf == nil {
return nil
}
/*
* If root/leaf != nil, leaf must have a Value, even if it does not contain the desired key.
* The leaf holds the range of keys that would include the desired key
*/
var i int
for i = 0; i < leaf.numKeys; i++ {
if bytes.Equal(leaf.keys[i], key) {
break
}
}
if i == leaf.numKeys {
return nil
}
return (*Record)(leaf.pointers[i])
}
/*
* findLeaf traces the path from the root to a leaf, searching by key and displaying information about the path if the
* verbose flag is set--findLeaf returns the leaf containing the given key
*/
func findLeaf(root *node, key KeyType) *node {
if root == nil {
return root
}
i, c := 0, root
for !c.isLeaf {
i = 0
for i < c.numKeys {
if bytes.Compare(key, c.keys[i]) >= 0 {
i++
} else {
break
}
}
c = (*node)(c.pointers[i])
}
// c is the found leaf node
return c
}
/*
* findFirstLeaf traces the path from the root to the leftmost leaf in the tree
*/
func findFirstLeaf(root *node) *node {
if root == nil {
return root
}
c := root
for !c.isLeaf {
c = (*node)(c.pointers[0])
}
return c
}
func findLastLeaf(root *node) *node {
if root == nil {
return root
}
c := root
for !c.isLeaf {
c = (*node)(c.pointers[c.numKeys])
}
return c
}
/*
* nextLeaf returns the next non-nil leaf in the chain (to the right) of the current leaf
*/
func (n *node) nextLeaf() *node {
if p := (*node)(n.pointers[ORDER-1]); p != nil && p.isLeaf {
return p
}
return nil
}
/*
* delete is the master delete function
*/
func (t *Tree) delete(key KeyType) {
keyLeaf, keyRecord := t.find(key)
if keyRecord != nil && keyLeaf != nil {
t.root = deleteEntry(t.root, keyLeaf, key, unsafe.Pointer(keyRecord))
keyRecord = nil
}
}
/*
* getNeighborIndex is a utility function for deletion. It gets the index of a node's nearest
* sibling (that exists) to the left. If not then node is already the leftmost child and (in
* such a case the node) will return -1
*/
func getNeighborIndex(n *node) int {
var i int
for i = 0; i <= n.parent.numKeys; i++ {
if (*node)(n.parent.pointers[i]) == n {
return i - 1
}
}
log.Panicf("getNeighborIndex: Search for nonexistent pointer to node in parent.\nNode: %#v\n", n)
return i
}
/*
* removeEntryFromNode does just that
*/
func removeEntryFromNode(n *node, key KeyType, pointer unsafe.Pointer) *node {
/*
* Remove the key and shift the other keys accordingly
*/
var i, numPointers int
for !bytes.Equal(n.keys[i], key) {
i++
}
for i++; i < n.numKeys; i++ { // was for i+=1;
n.keys[i-1] = n.keys[i]
}
/*
* Remove the pointer and shift other pointers accordingly
*/
if n.isLeaf {
numPointers = n.numKeys
} else {
numPointers = n.numKeys + 1
}
i = 0
for n.pointers[i] != pointer {
i++
}
for i++; i < numPointers; i++ { // was for i+=1;
n.pointers[i-1] = n.pointers[i]
}
/*
* One key fewer
*/
n.numKeys--
/*
* Set the other pointers to nil for tidiness. A leaf uses
* the last pointer to point to the next leaf
*/
if n.isLeaf {
for i = n.numKeys; i < ORDER-1; i++ {
n.pointers[i] = nil
}
} else {
for i = n.numKeys + 1; i < ORDER; i++ {
n.pointers[i] = nil
}
}
return n
}
/*
* deleteEntry deletes and entry from the tree. Removes the Record and it's key and pointer from
* the leaf, and then makes all appropriate changes to preserve the tree's properties
*/
func deleteEntry(root, n *node, key KeyType, pointer unsafe.Pointer) *node {
var minKeys, kPrimeIndex, capacity int
/*
* Remove key and pointer from node
*/
n = removeEntryFromNode(n, key, pointer)
/*
* CASE: deletion from the root node
*/
if n == root {
return adjustRoot(root)
}
/*
* CASE: deletion from a node below the root (continue rest of function)
*
* Determine minimum allowable size of node to be preserved after deletion
*/
if n.isLeaf {
minKeys = cut(ORDER - 1)
} else {
minKeys = cut(ORDER) - 1
}
/*
* CASE: node stays at or above minimum (simple case)
*/
if n.numKeys >= minKeys {
return root
}
/*
* CASE: node falls below minimum. Either coalescence or redistribution is needed
*
* Find the appropriate neighbor node with which to coalesce. Also find the key (kPrime)
* in the parent between the pointer to node n and the pointer to the neighbor
*/
neighborIndex := getNeighborIndex(n)
if neighborIndex == -1 {
kPrimeIndex = 0
} else {
kPrimeIndex = neighborIndex
}
kPrime := n.parent.keys[kPrimeIndex]
var neighbor *node
if neighborIndex == -1 {
neighbor = (*node)(n.parent.pointers[1])
} else {
neighbor = (*node)(n.parent.pointers[neighborIndex])
}
if n.isLeaf {
capacity = ORDER
} else {
capacity = ORDER - 1
}
/*
* Coalescence
*/
if neighbor.numKeys+n.numKeys < capacity {
return coalesceNodes(root, n, neighbor, neighborIndex, kPrime)
}
/*S
* Redistribution
*/
return redistributeNodes(root, n, neighbor, neighborIndex, kPrimeIndex, kPrime)
}
/*
* adjustRoot does some magic in the root node (not really)
*/
func adjustRoot(root *node) *node {
/*
* CASE: nonempty root. key and pointer have already been deleted, so nothing to be done
*/
if root.numKeys > 0 {
return root
}
/*
* CASE: empty root. If it has a child, promote the first (only) child as the new root
*/
var newRoot *node
if !root.isLeaf {
newRoot = (*node)(root.pointers[0])
newRoot.parent = nil
} else {
/*
* If it is a leaf (has no children), then the whole tree is in fact empty
*/
newRoot = nil // free
}
root = nil
return newRoot
}
/*
* coalesceNodes coalesces a node that has become too small after deletion with a
* neighboring node that can accept the additional entries without exceeing the maximum
*/
func coalesceNodes(root, n, neighbor *node, neighborIndex int, kPrime KeyType) *node {
var tmp *node
/*
* Swap neighbor with node if node is on the extreme left and neighbor is to it's right
*/
if neighborIndex == -1 {
tmp = n
n = neighbor
neighbor = tmp
}
/*
* Starting point in the neighbor for copying keys and pointers from n. Recall that n and
* neighbor have swapped places in the special case of n being a leftmost child
*/
neighborInsertionIndex := neighbor.numKeys
var i, j, nEnd int
/*
* CASE: Nonleaf node. Append kPrime and the following pointer and append all pointers and keys from the neighbor
*/
if !n.isLeaf {
/*
* Append kPrime
*/
neighbor.keys[neighborInsertionIndex] = kPrime
neighbor.numKeys++
nEnd = n.numKeys
// TODO: THIS MIGHT BE WRONG - NEVERMIND
for i, j = neighborInsertionIndex+1, 0; j < nEnd; i, j = i+1, j+1 {
neighbor.keys[i] = n.keys[j]
neighbor.pointers[i] = n.pointers[j]
neighbor.numKeys++
n.numKeys--
}
/*
* The number of pointers is always one more than the number of keys
*/
neighbor.pointers[i] = n.pointers[j]
/*
* All children must now point up to the same parent
*/
for i = 0; i < neighbor.numKeys+1; i++ {
tmp = (*node)(neighbor.pointers[i])
tmp.parent = neighbor
}
/*
* CASE: In a leaf, append the keys and pointers of n to the neighbor.
* Set the neighbor's last pointer to point to what had been n's right neighbor.
*/
} else {
for i, j = neighborInsertionIndex, 0; j < n.numKeys; i, j = i+1, j+1 {
neighbor.keys[i] = n.keys[j]
neighbor.pointers[i] = n.pointers[j]
neighbor.numKeys++
}
neighbor.pointers[ORDER-1] = n.pointers[ORDER-1]
}
root = deleteEntry(root, n.parent, kPrime, unsafe.Pointer(n))
n = nil // free
return root
}
/*
* redistributeNodes redistributes entries between two nodes when one has become too small
* after deletion but its neighbor is too big to append the small node's entries without
* exceeding the maximum
*/
func redistributeNodes(root, n, neighbor *node, neighborIndex, kPrimeIndex int, kPrime KeyType) *node {
var i int
var tmp *node
/*
* CASE: n has a neighbor to the left. Pull the neighbor's last key-pointer pair over
* from the neighbor's right end to n's lef end
*/
if neighborIndex != -1 {
if !n.isLeaf {
n.pointers[n.numKeys+1] = n.pointers[n.numKeys]
}
for i = n.numKeys; i > 0; i-- {
n.keys[i] = n.keys[i-1]
n.pointers[i] = n.pointers[i-1]
}
if !n.isLeaf {
n.pointers[0] = neighbor.pointers[neighbor.numKeys]
tmp = (*node)(n.pointers[0])
tmp.parent = n
neighbor.pointers[neighbor.numKeys] = nil
n.keys[0] = kPrime
n.parent.keys[kPrimeIndex] = neighbor.keys[neighbor.numKeys-1]
} else {
n.pointers[0] = neighbor.pointers[neighbor.numKeys-1]
neighbor.pointers[neighbor.numKeys-1] = nil
n.keys[0] = neighbor.keys[neighbor.numKeys-1]
n.parent.keys[kPrimeIndex] = n.keys[0]
}
/*
* CASE: n is the leftmost child. Take a key-pointer pair from the neighbor
* to the right. Move the neighbor's leftmost key-pointer pair to n's rightmost position
*/
} else {
if n.isLeaf {
n.keys[n.numKeys] = neighbor.keys[0]
n.pointers[n.numKeys] = neighbor.pointers[0]
n.parent.keys[kPrimeIndex] = neighbor.keys[1]
} else {
n.keys[n.numKeys] = kPrime
n.pointers[n.numKeys+1] = neighbor.pointers[0]
tmp = (*node)(n.pointers[n.numKeys+1])
tmp.parent = n
n.parent.keys[kPrimeIndex] = neighbor.keys[0]
}
for i = 0; i < neighbor.numKeys-1; i++ {
neighbor.keys[i] = neighbor.keys[i+1]
neighbor.pointers[i] = neighbor.pointers[i+1]
}
if !n.isLeaf {
neighbor.pointers[i] = neighbor.pointers[i+1]
}
}
/*
* n now has one more key and one more pointer; the neighbor has one fewer of each
*/
n.numKeys++
neighbor.numKeys--
return root
}
func destroyTreeNodes(n *node) {
if n == nil {
return
}
if n.isLeaf {
for i := 0; i < n.numKeys; i++ {
n.pointers[i] = nil
}
} else {
for i := 0; i < n.numKeys+1; i++ {
destroyTreeNodes((*node)(n.pointers[i]))
}
}
n = nil
}
func (t *Tree) destroyTree() {
destroyTreeNodes(t.root)
}
/*
* cut finds the appropriate place to split a node that is too big
*/
func cut(length int) int {
if length%2 == 0 {
return length / 2
}
return length/2 + 1
}
// makeRecord create a new Record to hold the Value to which a key refers
func makeRecord(value ValType) *Record {
return &Record{
Value: value,
}
}
// makeNode creates a new general node, which can be adapted to serve as either a leaf or internal node
func makeNode() *node {
return &node{}
}
// makeLeaf creates a new leaf by creating a node and then adapting it appropriately
func makeLeaf() *node {
leaf := makeNode()
leaf.isLeaf = true
return leaf
}
func Btoi(b []byte) int64 {
return int64(b[7]) |
int64(b[6])<<8 |
int64(b[5])<<16 |
int64(b[4])<<24 |
int64(b[3])<<32 |
int64(b[2])<<40 |
int64(b[1])<<48 |
int64(b[0])<<56
}
func Itob(i int64) []byte {
return []byte{
byte(i >> 56),
byte(i >> 48),
byte(i >> 40),
byte(i >> 32),
byte(i >> 24),
byte(i >> 16),
byte(i >> 8),
byte(i),
}
}
Raw
bpt.go
package bpt
import (
"bytes"
"fmt"
"log"
)
const ORDER = 64
type record struct {
value []byte
}
type node struct {
num_keys int
keys [][]byte
ptrs []interface{}
parent *node
next *node
is_leaf bool
}
var queue *node = nil
// helper function for printing the
// tree out. (see print_tree)
func enqueue(new_node *node) {
var c *node
if queue == nil {
queue = new_node
queue.next = nil
} else {
c = queue
for c.next != nil {
c = c.next
}
c.next = new_node
new_node.next = nil
}
}
// helper function for printing the
// tree out. (see print_tree)
func dequeue() *node {
var n *node = queue
queue = queue.next
n.next = nil
return n
}
// prints the bottom row of keys of the tree
func print_leaves(root *node) {
var i int
var c *node = root
if root == nil {
fmt.Printf("Empty tree.\n")
return
}
for !c.is_leaf {
c = c.ptrs[0].(*node)
}
for {
for i = 0; i < c.num_keys; i++ {
fmt.Printf("%s ", c.keys[i])
}
if c.ptrs[ORDER-1] != nil {
fmt.Printf(" | ")
c = c.ptrs[ORDER-1].(*node)
} else {
break
}
}
fmt.Printf("\n")
}
// utility to give the height of the tree
func height(root *node) int {
var h int
var c *node = root
for !c.is_leaf {
c = c.ptrs[0].(*node)
h++
}
return h
}
// utility function to give the length in edges
// for the path from any node to the root
func path_to_root(root, child *node) int {
var length int
var c *node = child
for c != root {
c = c.parent
length++
}
return length
}
// print tree out
func print_tree(root *node) {
var n *node = nil
var i, rank, new_rank int
if root == nil {
fmt.Printf("Empty tree.\n")
return
}
queue = nil
enqueue(root)
for queue != nil {
n = dequeue()
if n.parent != nil && n == n.parent.ptrs[0] {
new_rank = path_to_root(root, n)
if new_rank != rank {
rank = new_rank
fmt.Printf("\n")
}
}
for i = 0; i < n.num_keys; i++ {
fmt.Printf("%s ", n.keys[i])
}
if !n.is_leaf {
for i = 0; i <= n.num_keys; i++ {
enqueue(n.ptrs[i].(*node))
}
}
fmt.Printf("| ")
}
fmt.Printf("\n")
}
// find leaf type node for a given key
func find_leaf(root *node, key []byte) *node {
var c *node = root
if c == nil {
return c
}
var i int
for !c.is_leaf {
i = 0
for i < c.num_keys {
if bytes.Compare(key, c.keys[i]) >= 0 {
i++
} else {
break
}
}
// TODO: DEBUG LINE
if c.ptrs[i] == nil {
log.Printf(">> i=%d, c.num_keys=%d, c.ptrs=%+v\n", i, c.num_keys, c.ptrs)
}
c = c.ptrs[i].(*node)
}
return c
}
// find first leaf
func find_first_leaf(root *node) *node {
if root == nil {
return root
}
var c *node = root
for !c.is_leaf {
c = c.ptrs[0].(*node)
}
return c
}
// find record for a given key
func find(root *node, key []byte) *record {
var c *node = find_leaf(root, key)
if c == nil {
return nil
}
var i int
for i = 0; i < c.num_keys; i++ {
if bytes.Equal(c.keys[i], key) {
break
}
}
if i == c.num_keys {
return nil
}
return c.ptrs[i].(*record)
}
// find split point of full node
func cut(length int) int {
if length%2 == 0 {
return length / 2
}
return length/2 + 1
}
// create a record to hold a value for a given key
func make_record(val []byte) *record {
return &record{
value: val,
}
}
// create a new general node... can be adapted
// to serve as either an internal or leaf node
func make_node() *node {
return &node{
num_keys: 0,
keys: make([][]byte, ORDER-1),
ptrs: make([]interface{}, ORDER),
parent: nil,
next: nil,
is_leaf: false,
}
}
// create a new leaf node by addapting a general node
func make_leaf() *node {
var leaf *node
leaf = make_node()
leaf.is_leaf = true
return leaf
}
// helper->insert_into_parent
// used to find index of the parent's ptr to the
// node to the left of the key to be inserted
func get_left_index(parent, left *node) int {
left_index := 0
for left_index <= parent.num_keys && parent.ptrs[left_index] != left {
left_index++
}
return left_index
}
// inserts a new key and *record into a leaf, then returns leaf
func insert_into_leaf(leaf *node, key []byte, ptr *record) *node {
var i, insertion_point int
for insertion_point < leaf.num_keys && bytes.Compare(leaf.keys[insertion_point], key) == -1 {
insertion_point++
}
for i = leaf.num_keys; i > insertion_point; i-- {
leaf.keys[i] = leaf.keys[i-1]
leaf.ptrs[i] = leaf.ptrs[i-1]
}
leaf.keys[insertion_point] = key
leaf.ptrs[insertion_point] = ptr
leaf.num_keys++
return leaf
}
// inserts a new key and *record into a leaf, so as
// to exceed the order, causing the leaf to be split
func insert_into_leaf_after_splitting(root, leaf *node, key []byte, ptr *record) *node {
var new_leaf *node
var tmp_keys [ORDER][]byte
var tmp_ptrs [ORDER]interface{}
var insertion_index, split, i, j int
var new_key []byte
new_leaf = make_leaf()
for insertion_index < ORDER-1 && bytes.Compare(leaf.keys[insertion_index], key) == -1 {
insertion_index++
}
for i < leaf.num_keys {
if j == insertion_index {
j++
}
tmp_keys[j] = leaf.keys[i]
tmp_ptrs[j] = leaf.ptrs[i]
i++
j++
}
tmp_keys[insertion_index] = key
tmp_ptrs[insertion_index] = ptr
leaf.num_keys = 0
split = cut(ORDER - 1)
for i = 0; i < split; i++ {
leaf.ptrs[i] = tmp_ptrs[i]
leaf.keys[i] = tmp_keys[i]
leaf.num_keys++
}
j = 0
for i = split; i < ORDER; i++ {
new_leaf.ptrs[j] = tmp_ptrs[i]
new_leaf.keys[j] = tmp_keys[i]
new_leaf.num_keys++
j++
}
// freeing tmps...
for i = 0; i < ORDER; i++ {
tmp_ptrs[i] = nil
tmp_keys[i] = nil
}
new_leaf.ptrs[ORDER-1] = leaf.ptrs[ORDER-1]
leaf.ptrs[ORDER-1] = new_leaf
for i = leaf.num_keys; i < ORDER-1; i++ {
leaf.ptrs[i] = nil
}
for i = new_leaf.num_keys; i < ORDER-1; i++ {
new_leaf.ptrs[i] = nil
}
new_leaf.parent = leaf.parent
new_key = new_leaf.keys[0]
return insert_into_parent(root, leaf, new_key, new_leaf)
}
// insert a new key, ptr to a node
func insert_into_node(root, n *node, left_index int, key []byte, right *node) *node {
var i int
for i = n.num_keys; i > left_index; i-- {
n.ptrs[i+1] = n.ptrs[i]
n.keys[i] = n.keys[i-1]
}
n.ptrs[left_index+1] = right
n.keys[left_index] = key
n.num_keys++
return root
}
// insert a new key, ptr to a node causing node to split
func insert_into_node_after_splitting(root, old_node *node, left_index int, key []byte, right *node) *node {
var i, j, split int
var new_node, child *node
var tmp_keys [ORDER][]byte
var tmp_ptrs [ORDER + 1]interface{}
var k_prime []byte
for i < old_node.num_keys+1 {
if j == left_index+1 {
j++
}
tmp_ptrs[j] = old_node.ptrs[i]
i++
j++
}
i = 0
j = 0
for i < old_node.num_keys {
if j == left_index {
j++
}
tmp_keys[j] = old_node.keys[i]
i++
j++
}
tmp_ptrs[left_index+1] = right
tmp_keys[left_index] = key
split = cut(ORDER)
new_node = make_node()
old_node.num_keys = 0
for i = 0; i < split-1; i++ {
old_node.ptrs[i] = tmp_ptrs[i]
old_node.keys[i] = tmp_keys[i]
old_node.num_keys++
}
old_node.ptrs[i] = tmp_ptrs[i]
k_prime = tmp_keys[split-1]
j = 0
for i += 1; i < ORDER; i++ {
new_node.ptrs[j] = tmp_ptrs[i]
new_node.keys[j] = tmp_keys[i]
new_node.num_keys++
j++
}
new_node.ptrs[j] = tmp_ptrs[i]
// free tmps...
for i = 0; i < ORDER; i++ {
tmp_keys[i] = nil
tmp_ptrs[i] = nil
}
tmp_ptrs[ORDER] = nil
new_node.parent = old_node.parent
for i = 0; i <= new_node.num_keys; i++ {
child = new_node.ptrs[i].(*node)
child.parent = new_node
}
return insert_into_parent(root, old_node, k_prime, new_node)
}
// insert a new node (leaf or internal) into tree, return root of tree
func insert_into_parent(root, left *node, key []byte, right *node) *node {
var left_index int
var parent *node
parent = left.parent
if parent == nil {
return insert_into_new_root(left, key, right)
}
left_index = get_left_index(parent, left)
if parent.num_keys < ORDER-1 {
return insert_into_node(root, parent, left_index, key, right)
}
return insert_into_node_after_splitting(root, parent, left_index, key, right)
}
// creates a new root for two sub-trees and inserts the key into the new root
func insert_into_new_root(left *node, key []byte, right *node) *node {
var root *node = make_node()
root.keys[0] = key
root.ptrs[0] = left
root.ptrs[1] = right
root.num_keys++
root.parent = nil
left.parent = root
right.parent = root
return root
}
// first insertion, start a new tree
func start_new_tree(key []byte, ptr *record) *node {
var root *node = make_leaf()
root.keys[0] = key
root.ptrs[0] = ptr
root.ptrs[ORDER-1] = nil
root.parent = nil
root.num_keys++
return root
}
// master insert function
func insert(root *node, key []byte, val []byte) *node {
var ptr *record
var leaf *node
if find(root, key) != nil {
return root
}
ptr = make_record(val)
if root == nil {
return start_new_tree(key, ptr)
}
leaf = find_leaf(root, key)
if leaf.num_keys < ORDER-1 {
leaf = insert_into_leaf(leaf, key, ptr)
return root
}
return insert_into_leaf_after_splitting(root, leaf, key, ptr)
}
// helper for delete methods... returns index of
// a nodes nearest sibling to the left if one exists
func get_neighbor_index(n *node) int {
var i int
for i = 0; i <= n.parent.num_keys; i++ {
if n.parent.ptrs[i] == n {
return i - 1
}
}
log.Fatalf("Search for nonexistent ptr to node in parent.\nNode: %p\n", n)
return 1
}
func remove_entry_from_node(n *node, key []byte, ptr interface{}) *node {
var i, num_ptrs int
// remove key and shift over keys accordingly
for !bytes.Equal(n.keys[i], key) {
i++
}
for i += 1; i < n.num_keys; i++ {
n.keys[i-1] = n.keys[i]
}
// remove ptr and shift other ptrs accordingly
// first determine the number of ptrs
if n.is_leaf {
num_ptrs = n.num_keys
} else {
num_ptrs = n.num_keys + 1
}
i = 0
for n.ptrs[i] != ptr {
i++
}
//for n.ptrs[i].(*node) != ptr {
// i++
//}
for i += 1; i < num_ptrs; i++ {
n.ptrs[i-1] = n.ptrs[i]
}
// one key has been removed
n.num_keys--
// set other ptrs to nil for tidiness; remember leaf
// nodes use the last ptr to point to the next leaf
if n.is_leaf {
for i = n.num_keys; i < ORDER-1; i++ {
n.ptrs[i] = nil
}
} else {
for i = n.num_keys + 1; i < ORDER; i++ {
n.ptrs[i] = nil
}
}
return n
}
func adjust_root(root *node) *node {
// if non-empty root key and ptr
// have already been deleted, so
// nothing to be done here
if root.num_keys > 0 {
return root
}
var new_root *node
// if root is empty and has a child
// promote first (only) child as the
// new root node. If it's a leaf then
// the while tree is empty...
if !root.is_leaf {
new_root = root.ptrs[0].(*node)
new_root.parent = nil
} else {
new_root = nil
}
root = nil // free root
return new_root
}
// merge (underflow)
func coalesce_nodes(root, n, neighbor *node, neighbor_index int, k_prime []byte) *node {
var i, j, neighbor_insertion_index, n_end int
var tmp *node
// swap neight with node if nod eis on the
// extreme left and neighbor is to its right
if neighbor_index == -1 {
tmp = n
n = neighbor
neighbor = tmp
}
// starting index for merged pointers
neighbor_insertion_index = neighbor.num_keys
// case nonleaf node, append k_prime and the following ptr.
// append all ptrs and keys for the neighbors.
if !n.is_leaf {
// append k_prime (key)
neighbor.keys[neighbor_insertion_index] = k_prime
neighbor.num_keys++
n_end = n.num_keys
i = neighbor_insertion_index + 1
j = 0
for j < n_end {
neighbor.keys[i] = n.keys[j]
neighbor.ptrs[i] = n.ptrs[j]
neighbor.num_keys++
n.num_keys--
i++
j++
}
neighbor.ptrs[i] = n.ptrs[j]
for i = 0; i < neighbor.num_keys+1; i++ {
tmp = neighbor.ptrs[i].(*node)
tmp.parent = neighbor
}
} else {
// in a leaf; append the keys and ptrs.
i = neighbor_insertion_index
j = 0
for j < n.num_keys {
neighbor.keys[i] = n.keys[j]
neighbor.ptrs[i] = n.ptrs[j]
neighbor.num_keys++
i++
j++
}
neighbor.ptrs[ORDER-1] = n.ptrs[ORDER-1]
}
root = delete_entry(root, n.parent, k_prime, n)
n.keys = nil
n.ptrs = nil
n = nil // free n
return root
}
// merge / redistribute
func redistribute_nodes(root, n, neighbor *node, neighbor_index, k_prime_index int, k_prime []byte) *node {
var i int
var tmp *node
// case: node n has a neighnor to the left
if neighbor_index != -1 {
if !n.is_leaf {
n.ptrs[n.num_keys+1] = n.ptrs[n.num_keys]
}
for i = n.num_keys; i > 0; i-- {
n.keys[i] = n.keys[i-1]
n.ptrs[i] = n.ptrs[i-1]
}
if !n.is_leaf {
n.ptrs[0] = neighbor.ptrs[neighbor.num_keys]
tmp = n.ptrs[0].(*node)
tmp.parent = n
neighbor.ptrs[neighbor.num_keys] = nil
n.keys[0] = k_prime
n.parent.keys[k_prime_index] = neighbor.keys[neighbor.num_keys-1]
} else {
n.ptrs[0] = neighbor.ptrs[neighbor.num_keys-1]
neighbor.ptrs[neighbor.num_keys-1] = nil
n.keys[0] = neighbor.keys[neighbor.num_keys-1]
n.parent.keys[k_prime_index] = n.keys[0]
}
} else {
// case: n is left most child (n has no left neighbor)
if n.is_leaf {
n.keys[n.num_keys] = neighbor.keys[0]
n.ptrs[n.num_keys] = neighbor.ptrs[0]
n.parent.keys[k_prime_index] = neighbor.keys[1]
} else {
n.keys[n.num_keys] = k_prime
n.ptrs[n.num_keys+1] = neighbor.ptrs[0]
tmp = n.ptrs[n.num_keys+1].(*node)
tmp.parent = n
n.parent.keys[k_prime_index] = neighbor.keys[0]
}
for i = 0; i < neighbor.num_keys-1; i++ {
neighbor.keys[i] = neighbor.keys[i+1]
neighbor.ptrs[i] = neighbor.ptrs[i+1]
}
if !n.is_leaf {
neighbor.ptrs[i] = neighbor.ptrs[i+1]
}
}
n.num_keys++
neighbor.num_keys--
return root
}
// deletes an entry from the tree; removes record, key, and ptr from leaf and rebalances tree
func delete_entry(root, n *node, key []byte, ptr interface{}) *node {
var min_keys, neighbor_index, k_prime_index, capacity int
var neighbor *node
var k_prime []byte
// remove key, ptr from node
n = remove_entry_from_node(n, key, ptr)
//switch ptr.(type) {
//case *node:
// n = remove_entry_from_node(n, key, ptr.(*node))
//case *record:
// n = remove_entry_from_node(n, key, ptr.(*record))
//}
if n == root {
return adjust_root(root)
}
// case: delete from inner node
if n.is_leaf {
min_keys = cut(ORDER - 1)
} else {
min_keys = cut(ORDER) - 1
}
// case: node stays at or above min order
if n.num_keys >= min_keys {
return root
}
// case: node is bellow min order; coalescence or redistribute
neighbor_index = get_neighbor_index(n)
if neighbor_index == -1 {
k_prime_index = 0
} else {
k_prime_index = neighbor_index
}
k_prime = n.parent.keys[k_prime_index]
if neighbor_index == -1 {
neighbor = n.parent.ptrs[1].(*node)
} else {
neighbor = n.parent.ptrs[neighbor_index].(*node)
}
if n.is_leaf {
capacity = ORDER
} else {
capacity = ORDER - 1
}
// coalescence
if neighbor.num_keys+n.num_keys < capacity {
return coalesce_nodes(root, n, neighbor, neighbor_index, k_prime)
}
return redistribute_nodes(root, n, neighbor, neighbor_index, k_prime_index, k_prime)
}
// master delete
func delete(root *node, key []byte) *node {
var key_leaf *node
var key_record *record
key_record = find(root, key)
key_leaf = find_leaf(root, key)
if key_record != nil && key_leaf != nil {
root = delete_entry(root, key_leaf, key, key_record)
key_record = nil // free key_record
}
return root
}
func destroy_tree_nodes(root *node) {
var i int
if root.is_leaf {
for i = 0; i < root.num_keys; i++ {
root.ptrs[i] = nil
}
} else {
for i = 0; i < root.num_keys+1; i++ {
destroy_tree_nodes(root.ptrs[i].(*node))
}
}
root.ptrs = nil // free
root.keys = nil // free
root = nil // free
}
func destroy_tree(root *node) {
destroy_tree_nodes(root)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment