B-tree Implementation in Go

A B-tree is a self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. B-trees are commonly used in databases and file systems to manage large blocks of data.

Program Structure

The Go program implementing the B-tree is structured into the following components:

1. BTreeNode Struct: This struct represents a node in the B-tree, containing keys, children, and a boolean indicating if the node is a leaf.
2. BTree Struct: This struct represents the B-tree itself, containing the root node and the minimum degree (t), which determines the range of keys each node can hold.
3. NewBTree Function: This function initializes a new B-tree with a specified minimum degree.
4. Search Method: This method searches for a key in the B-tree and returns the node containing the key if found.
5. Insert Method: This method inserts a new key into the B-tree, ensuring the tree remains balanced.
6. SplitChild Method: This helper method splits a full child node during insertion.
7. InsertNonFull Method: This helper method inserts a key into a node that is not full.

Go Code Implementation

package main

import "fmt"

// BTreeNode represents a node in a B-tree
type BTreeNode struct {
    keys     []int       // Array of keys
    children []*BTreeNode // Array of child pointers
    leaf     bool        // Is true when the node is a leaf
}

// BTree represents the B-tree itself
type BTree struct {
    root *BTreeNode // Pointer to the root node
    t    int        // Minimum degree (defines the range for number of keys)
}

// NewBTree creates a new B-tree with a given minimum degree
func NewBTree(t int) *BTree {
    return &BTree{
        root: &BTreeNode{
            keys:     make([]int, 0),
            children: make([]*BTreeNode, 0),
            leaf:     true,
        },
        t: t,
    }
}

// Search searches for a key in the B-tree and returns the node containing the key if found
func (n *BTreeNode) Search(k int) (*BTreeNode, int) {
    i := 0
    // Find the first key greater than or equal to k
    for i < len(n.keys) && k > n.keys[i] {
        i++
    }
    // If the found key is equal to k, return this node
    if i < len(n.keys) && n.keys[i] == k { return n, i } // If the key is not found here and this is a leaf node, return nil if n.leaf { return nil, -1 } // Go to the appropriate child return n.children[i].Search(k) } // Insert inserts a new key into the B-tree func (t *BTree) Insert(k int) { r := t.root // If the root is full, then the tree grows in height if len(r.keys) == 2*t.t-1 { s := &BTreeNode{ children: []*BTreeNode{r}, leaf: false, } t.root = s s.SplitChild(0, r, t.t) s.InsertNonFull(k, t.t) } else { r.InsertNonFull(k, t.t) } } // SplitChild splits the child y of this node func (n *BTreeNode) SplitChild(i int, y *BTreeNode, t int) { z := &BTreeNode{ keys: make([]int, t-1), leaf: y.leaf, children: make([]*BTreeNode, len(y.children)), } // Copy the last (t-1) keys of y to z copy(z.keys, y.keys[t:]) // If y is not a leaf, copy the last t children of y to z if !y.leaf { copy(z.children, y.children[t:]) } y.keys = y.keys[:t-1] // Reduce the number of keys in y n.children = append(n.children[:i+1], append([]*BTreeNode{z}, n.children[i+1:]...)...) n.keys = append(n.keys[:i], append([]int{y.keys[t-1]}, n.keys[i:]...)...) } // InsertNonFull inserts a new key into this node func (n *BTreeNode) InsertNonFull(k int, t int) { i := len(n.keys) - 1 if n.leaf { // Insert the new key into the correct position in this node n.keys = append(n.keys, 0) for i >= 0 && k < n.keys[i] { n.keys[i+1] = n.keys[i] i-- } n.keys[i+1] = k } else { // Find the child which is going to have the new key for i >= 0 && k < n.keys[i] { i-- } i++ // If the child is full, split it if len(n.children[i].keys) == 2*t-1 { n.SplitChild(i, n.children[i], t) if k > n.keys[i] {
                i++
            }
        }
        n.children[i].InsertNonFull(k, t)
    }
}

func main() {
    t := 3 // A B-tree with minimum degree 3
    btree := NewBTree(t)

    // Insert keys into the B-tree
    for _, k := range []int{10, 20, 5, 6, 12, 30, 7, 17} {
        btree.Insert(k)
    }

    // Search for a key in the B-tree
    if node, idx := btree.root.Search(6); node != nil {
        fmt.Printf("Found key %d at index %d in node with keys: %v\n", 6, idx, node.keys)
    } else {
        fmt.Println("Key not found.")
    }
}
    

Explanation of the Code

Here’s a breakdown of the code:

• BTreeNode Struct: The BTreeNode struct holds the keys and child pointers of a node, along with a boolean indicating whether the node is a leaf.
• BTree Struct: The BTree struct represents the B-tree, containing the root node and the minimum degree t. The minimum degree determines the range for the number of keys each node can hold.
• NewBTree Function: This function initializes a B-tree with the specified minimum degree. The root node is initialized as a leaf with an empty list of keys and children.
• Search Method: This method recursively searches for a key in the B-tree. If the key is found, the method returns the node and index where the key is located. If the key is not found, the method returns nil.
• Insert Method: This method inserts a new key into the B-tree. If the root node is full, it is split, and the tree grows in height. The insertion is then performed on the appropriate child.
• SplitChild Method: This method splits a full child node into two nodes, redistributing the keys and children between them. The middle key is moved up to the parent node.
• InsertNonFull Method: This method inserts a key into a node that is not full. If the node is a leaf, the key is inserted into the correct position. If the node is not a leaf, the method finds the appropriate child to insert the key, splitting the child if necessary.

Usage Example

Here’s an example of how you might use this B-tree implementation in a Go program:

func main() {
    t := 3 // A B-tree with minimum degree 3
    btree := NewBTree(t)

    // Insert keys into the B-tree
    for _, k := range []int{10, 20, 5, 6, 12, 30, 7, 17} {
        btree.Insert(k)
    }

    // Search for a key in the B-tree
    if node, idx := btree.root.Search(6); node != nil {
        fmt.Printf("Found key %d at index %d in node with keys: %v\n", 6, idx, node.keys)
    } else {
        fmt.Println("Key not found.")
    }
}
    

Conclusion

This Go program demonstrates a basic implementation of a B-tree, which is a widely used data structure in databases for efficient indexing and search operations. The B-tree maintains a balanced structure, ensuring that operations such as insertion, deletion, and search can be performed efficiently even with large datasets.