Implementing B-Trees

1. Understanding B-Tree Properties

Property	Description	Details
Order (m)	Maximum number of children per node	Each internal node can have at most m children. Leaf nodes may have fewer.
Minimum Degree (t)	Minimum number of children per internal node	Each internal node (except root) must have at least t children. Root may have 1 or more.
Keys per Node	Number of keys in each node	Internal nodes have between t-1 and 2t-1 keys. Leaf nodes can have between 0 and 2t-1 keys.
Height	Maximum depth of the tree	For a B-tree with n keys, height is at most ⌈log_t(n+1)⌉.
Balanced	All leaf nodes are at the same level	Ensures consistent search, insertion, and deletion times.
Sorted Keys	Keys in each node are sorted	Each key is greater than or equal to the keys in its left subtree and less than or equal to the keys in its right subtree.

Example: B-Tree Node Structure

class BTreeNode {
  constructor(t, isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
    this.maxKeys = 2 * t - 1;
  }

  // Insert key into node
  insertKey(key) {
    this.keys.push(key);
    this.keys.sort((a, b) => a - b);
  }
}

2. Creating BTreeNode Class

Example: BTreeNode Implementation

class BTreeNode {
  constructor(degree, isLeaf = false) {
    this.degree = degree;
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
  }

  // Insert a key into the node
  insertKey(key) {
    let i = this.keys.length - 1;
    while (i >= 0 && this.keys[i] > key) {
      i--;
    }
    this.keys.splice(i + 1, 0, key);
  }

  // Split the node when it's full
  splitChild(index) {
    const child = this.children[index];
    const newNode = new BTreeNode(child.degree, child.isLeaf);
    
    // Move keys and children to the new node
    const splitIndex = Math.floor(child.degree / 2);
    newNode.keys = child.keys.splice(splitIndex + 1);
    
    if (!child.isLeaf) {
      newNode.children = child.children.splice(splitIndex + 1);
    }

    this.children.splice(index + 1, 0, newNode);
    this.keys.splice(index, 0, child.keys[splitIndex]);

    return newNode;
  }

  // Check if node is full
  isFull() {
    return this.keys.length === this.degree - 1;
  }
}

module.exports = BTreeNode;

Property	Description	Values
degree	Maximum number of children a node can have	`number`
keys	Array of keys stored in the node	`Array<number>`
children	Array of child nodes (if not a leaf)	`Array<BTreeNode>`
isLeaf	Indicates if the node is a leaf node	`boolean`

Note: The degree determines the maximum number of keys a node can hold, which is 2 * degree - 1.

3. Searching Keys

Operation	Description	Time Complexity	Notes
Search(key)	Finds a key in the B-tree	`O(log n)`	Traverses from root to leaf, comparing keys at each node
Search(key, node)	Recursive search within a specific node	`O(log n)`	Uses binary search to locate key in node's keys array

Example: Searching for a Key in B-Tree

function search(node, key) {
  let i = 0;
  while (i < node.keys.length && key > node.keys[i]) {
    i++;
  }

  if (i < node.keys.length && key === node.keys[i]) {
    return true; // Key found
  }

  if (node.isLeaf) {
    return false; // Key not found in leaf
  }

  return search(node.children[i], key); // Recurse into child
}

Note: The search operation in a B-tree is similar to binary search but adapted for multi-way trees. It starts at the root and recursively traverses down to a leaf node, comparing keys to determine the correct child to explore.

4. Inserting Keys

Inserting keys into a B-tree involves maintaining the tree's properties:

All leaves are at the same depth
Each node (except root) has between ⌈m/2⌉ and m keys
Keys in each node are sorted

When inserting a key:

If the node is not full, insert the key in sorted order
If the node is full (has m keys), split it into two nodes and promote the median key to the parent node
If the root is split, a new root is created

Example: Inserting a key into a B-tree

class BTreeNode {
  constructor(t, isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
    this.t = t; // Minimum degree
  }

  insertKey(key) {
    if (this.keys.length < this.t * 2 - 1) {
      // Node is not full, insert key in sorted order
      this.keys.push(key);
      this.keys.sort((a, b) => a - b);
    } else {
      // Node is full, split and promote median key
      this.splitNode(key);
    }
  }

  splitNode(key) {
    // Split the node into two nodes and promote median key
    const newChild = new BTreeNode(this.t, this.isLeaf);
    const midIndex = Math.floor(this.keys.length / 2);
    const medianKey = this.keys[midIndex];

    // Move keys to new node
    newChild.keys = this.keys.splice(midIndex + 1);
    newChild.children = this.children.splice(midIndex + 1);

    // Insert the new key in appropriate node
    if (key < medianKey) {
      this.keys.push(key);
      this.keys.sort((a, b) => a - b);
    } else {
      newChild.keys.push(key);
      newChild.keys.sort((a, b) => a - b);
    }

    // Promote median key to parent (if exists)
    if (this.parent) {
      this.parent.insertKey(medianKey);
    } else {
      // Create new root if needed
      const newRoot = new BTreeNode(this.t);
      newRoot.keys.push(medianKey);
      newRoot.children.push(this, newChild);
      this.parent = newRoot;
    }
  }
}

// Example usage:
const root = new BTreeNode(3); // t = 3 (minimum degree)
root.insertKey(10);
root.insertKey(20);
root.insertKey(5);
root.insertKey(6);
root.insertKey(15);

Operation	Description	Time Complexity	Space Complexity
Insert Key	Inserts a key into the B-tree maintaining its properties	`O(log n)`	`O(1)`

5. Splitting Full Nodes

When a node in a B-tree is full (contains the maximum number of keys), inserting a new key requires splitting the node to maintain the B-tree properties.

Operation	Description	Result
Splitting a full node	When a node reaches its maximum capacity (t-1 keys for a B-tree of order t), inserting another key triggers a split.	The node is divided into two nodes, and the middle key is promoted to the parent node.

Example: Splitting a Full Node

// B-tree of order 3 (max 2 keys per node)
// Node before split:
// [10, 20]
// Keys: 5, 10, 15, 20, 25
// Inserting key 30

// After split:
// Left node: [10]
// Right node: [20, 25]
// Promoted key: 15
// Parent node now contains [15]

Note: The split propagates up the tree if the parent node is also full, potentially causing a chain of splits.

6. Deleting Keys

Deleting a key from a B-tree involves maintaining the tree's properties:

All leaves must be at the same depth.
Each node (except root) must have at least ⌈m/2⌉ children.
Each node can hold up to m - 1 keys.

Deletion Process

If the key is in a leaf node:
- Simply remove the key.
- If the node has fewer than ⌈m/2⌉ keys after deletion, redistribute or merge with siblings.
If the key is in an internal node:
- Replace the key with its predecessor or successor (from a leaf).
- Delete the replacement key from the leaf node.

Operation	Description	Notes
Delete(key)	Removes key from tree	May require rebalancing
Redistribute	Move keys between siblings	Maintains node size constraints
Merge	Combine two nodes into one	Used when node underflows

Example: Delete key 40 from a B-tree

class BTreeNode {
  constructor(isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
  }
}

function deleteKey(node, key) {
  const index = node.keys.indexOf(key);
  if (index !== -1) {
    // Key is in this node
    if (node.isLeaf) {
      node.keys.splice(index, 1);
    } else {
      // Replace with predecessor or successor
      const pred = getPredecessor(node, index);
      node.keys[index] = pred;
      deleteKey(getChild(node, index + 1), pred);
    }
  } else {
    // Key is in a child node
    const child = getChild(node, key);
    deleteKey(child, key);
  }
}

Note: The deletion process may require redistribution or merging of nodes to maintain B-tree properties.

Warning: Merging nodes can cause the root to become a leaf, which may reduce the tree's height.

7. Merging Nodes

When a node in a B-tree becomes underfull (has fewer keys than the minimum required), it may need to be merged with neighboring nodes to maintain the tree's structural properties.

Operation	Description	Conditions
Merge	Merges a node with its sibling to maintain minimum key count.	Node has fewer keys than `m/2 - 1`, where `m` is the maximum degree.

Example: Merging Nodes in B-Tree

class BTreeNode {
  constructor(degree, isLeaf = false) {
    this.degree = degree;
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
  }

  // Merge with sibling node
  mergeWithSibling(sibling, parentKey) {
    this.keys.push(parentKey);
    this.keys.push(...sibling.keys);

    if (!this.isLeaf) {
      this.children.push(...sibling.children);
    }

    // Remove the sibling from parent's children list
    const index = this.parent.children.indexOf(sibling);
    if (index !== -1) {
      this.parent.children.splice(index, 1);
    }
  }
}

Note: Merging is performed to ensure that all internal nodes maintain at least m/2 - 1 keys, where m is the maximum degree of the B-tree.

Merging Process Summary

Identify a node with fewer keys than the minimum required.
Find a sibling that can contribute keys or be merged with.
Move the parent's key down to the merged node to balance the structure.
Update child pointers if necessary.

8. Borrowing from Siblings

Operation	Description	Conditions	Result
Borrow from left sibling	Take a key and child from the left sibling	Left sibling has more than minimum keys	Move key to parent, promote left sibling's key to parent
Borrow from right sibling	Take a key and child from the right sibling	Right sibling has more than minimum keys	Move key to parent, promote right sibling's key to parent

Example: Borrowing from Right Sibling

class BTreeNode {
  constructor(isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
  }
}

function borrowFromRight(node, parent, index) {
  const rightSibling = parent.children[index + 1];
  if (rightSibling.keys.length > 0) {
    const keyToMove = rightSibling.keys.shift();
    const childToMove = rightSibling.children.shift();
    
    parent.keys[index] = keyToMove;
    node.keys.push(parent.keys[index]);
    node.children.push(childToMove);
  }
}

Note: Borrowing maintains the B-tree property by redistributing keys among siblings to avoid splitting or merging nodes.

9. Traversing B-Tree

Example: In-order Traversal of B-Tree

class BTreeNode {
  constructor(t, isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.t = t;
    this.isLeaf = isLeaf;
  }
}

function traverse(node) {
  let i = 0;
  for (i = 0; i < node.keys.length; i++) {
    if (!node.isLeaf) {
      traverse(node.children[i]);
    }
    console.log(node.keys[i]);
  }
  if (!node.isLeaf) {
    traverse(node.children[i]);
  }
}

// Example usage:
const root = new BTreeNode(3, false);
root.keys = [10, 20];
root.children = [
  new BTreeNode(3, true),
  new BTreeNode(3, true),
  new BTreeNode(3, true)
];
root.children[0].keys = [5, 7];
root.children[1].keys = [15, 18];
root.children[2].keys = [25, 30];

traverse(root);
// Output: 5, 7, 10, 15, 18, 20, 25, 30

Operation	Description	Time Complexity	Space Complexity
In-order Traversal	Visits keys in sorted order by traversing left subtree, then root, then right subtree	`O(n)`	`O(h)` where `h` is height
Pre-order Traversal	Visits root first, then left subtree, then right subtree	`O(n)`	`O(h)`
Post-order Traversal	Visits left subtree, then right subtree, then root	`O(n)`	`O(h)`

Note: B-tree traversal is similar to binary tree traversal but with multiple children per node.

Traversal Types Summary

In-order: Left subtree → Root → Right subtree
Pre-order: Root → Left subtree → Right subtree
Post-order: Left subtree → Right subtree → Root

10. Implementing B+ Tree Variant

Example: Basic B+ Tree Node Structure

class BPlusTreeNode {
  constructor(isLeaf = false) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
    this.next = null; // For leaf nodes to form linked list
  }
}

Property	Description	Notes
keys	Sorted array of keys stored in the node	Keys are used for searching and indexing
children	Array of child nodes (for internal nodes)	Points to child nodes in the tree
isLeaf	Boolean indicating if node is a leaf	Leaf nodes store data records
next	Pointer to next leaf node (for sequential access)	Used for range queries and iteration

Example: Insert Operation in B+ Tree

function insertBPlusTree(root, key, value) {
  const newNode = insertIntoLeaf(root, key, value);
  if (newNode) {
    return createNewRoot(newNode);
  }
  return root;
}

Key Characteristics of B+ Trees

All data is stored in leaf nodes
Leaf nodes are linked for efficient range queries
Internal nodes only store keys to guide search
High fanout reduces tree height

B+ Tree vs B-Tree

B+ Tree: Data stored only in leaf nodes
B-Tree: Data can be stored in internal and leaf nodes
B+ Tree: Leaf nodes form a linked list for range queries
B-Tree: No direct link between leaf nodes

11. Understanding Database Indexing

Index Type	Description	Use Case	Performance Impact
B-Tree Index	Self-balancing tree structure optimized for disk storage and retrieval.	Primary key, foreign key, and frequently queried columns in relational databases.	Fast lookups, insertions, and deletions with O(log n) complexity.
Hash Index	Uses hash function to map keys to specific locations in memory or disk.	Exact match queries on columns with unique values (e.g., ID fields).	Very fast for equality lookups but not suitable for range queries.
Bitmap Index	Stores a bitmap for each value in the indexed column, indicating which rows contain that value.	Low-cardinality columns (e.g., gender, status) in data warehousing.	Fast for filtering and joins but consumes more storage space.
Full-Text Index	Specialized index for searching text content within documents or fields.	Search engines, content management systems, and document databases.	Efficient for natural language queries but requires additional processing overhead.

Example: Creating a B-Tree Index in SQL

CREATE INDEX idx_user_email ON users (email);

Note: B-Tree indexes are ideal for columns used in WHERE, JOIN, and ORDER BY clauses.

Warning: Adding too many indexes can slow down INSERT and UPDATE operations due to index maintenance.

Key Benefits of B-Tree Indexing

Efficient for range queries and ordered data access.
Supports both exact match and range searches.
Optimized for disk-based storage systems.

12. Comparing B-Tree Orders

Order	Minimum Degree (t)	Max Keys per Node	Min Keys per Node	Notes
t = 2	`2`	`3`	`1`	Standard B-tree with minimum degree 2
t = 3	`3`	`5`	`2`	More keys per node, better for disk I/O
t = 4	`4`	`7`	`3`	Even more keys, higher fanout
t = 5	`5`	`9`	`4`	Optimized for large datasets

Comparison of B-Tree Orders

Smaller t (e.g., t=2): More nodes, less fanout. Better for small datasets or frequent updates.
Higher t (e.g., t=5): Fewer nodes, more fanout. Better for large datasets and read-heavy workloads.
As t increases, the tree height decreases, reducing the number of disk accesses needed to find a key.