Implementing a B-Tree in JavaScript

B-trees are self-balancing tree data structures that are particularly well-suited for disk-based data storage due to their ability to minimize disk access. This challenge asks you to implement a basic B-tree in JavaScript, focusing on core operations like insertion, searching, and deletion. Successfully completing this challenge will demonstrate your understanding of tree structures and algorithms.

Problem Description

You are tasked with creating a B-tree data structure in JavaScript. The B-tree should support the following operations:

• insert(key, value): Inserts a new key-value pair into the B-tree. The key should be unique.
• search(key): Searches for a key in the B-tree and returns its associated value if found. Returns undefined if the key is not found.
• delete(key): Deletes a key-value pair from the B-tree.
• toArray(): Returns an array containing all keys in the B-tree in ascending order.

For simplicity, let's assume a B-tree of order 3 (minimum degree t = 1). This means each node can have at most 2 keys and 3 children. The root can have as few as 1 key. All other nodes (except the root) must have at least t keys.

Key Requirements:

• The B-tree should maintain its balance after insertions and deletions.
• The implementation should handle splitting and merging of nodes appropriately.
• The toArray() method should return a sorted array of keys.

Expected Behavior:

The B-tree should correctly insert, search, and delete key-value pairs while maintaining the B-tree properties. The toArray() method should provide a sorted view of the keys.

Edge Cases to Consider:

• Empty tree: Handle insertion and search operations on an empty tree.
• Duplicate keys: The insert method should not allow duplicate keys.
• Deleting a non-existent key: The delete method should handle this gracefully (e.g., by doing nothing or returning a specific value).
• Deleting the last element: Ensure the tree remains valid after deleting the last element.
• Splitting and merging nodes during insertion and deletion.
• Handling underflow in nodes after deletion.

Examples

Example 1:

Input:
  BTree = new BTree();
  BTree.insert(10, "value10");
  BTree.insert(20, "value20");
  BTree.insert(5, "value5");
Output:
  [5, 10, 20]
Explanation: The keys are inserted and then returned in sorted order.

Example 2:

Input:
  BTree = new BTree();
  BTree.insert(10, "value10");
  BTree.insert(20, "value20");
  BTree.search(15);
Output:
  undefined
Explanation: The key 15 is not present in the tree.

Example 3: (Deletion and Splitting)

Input:
  BTree = new BTree();
  BTree.insert(10, "value10");
  BTree.insert(20, "value20");
  BTree.insert(30, "value30");
  BTree.insert(40, "value40");
  BTree.insert(50, "value50");
  BTree.delete(20);
Output:
  [10, 30, 40, 50]
Explanation: Deleting 20 might cause splitting and rebalancing. The resulting keys are returned in sorted order.

Constraints

• The order of the B-tree is 3 (minimum degree t = 1).
• Keys are assumed to be numbers.
• Values can be any JavaScript data type.
• The toArray() method should have a time complexity of O(n), where n is the number of keys in the tree.
• Insertion and deletion operations should maintain a reasonable level of performance (avoiding excessive recursion or inefficient node traversal).

Notes

• Consider using a Node class to represent each node in the B-tree.
• The insert and delete operations are the most complex parts of the implementation. Pay close attention to how nodes are split and merged to maintain the B-tree properties.
• Think about how to handle underflow (when a node has fewer than the minimum number of keys) after a deletion. This might involve borrowing keys from a sibling node or merging with a sibling.
• Start with the insert operation and then implement search and delete. Testing each operation thoroughly as you go will help you identify and fix errors more easily.
• The toArray() method can be implemented using an in-order traversal of the B-tree.