Implement a B-Tree Data Structure in JavaScript

This challenge asks you to implement a B-tree data structure in JavaScript. B-trees are self-balancing search trees that maintain sorted data and allow searches, sequential access, insertions, and deletions in logarithmic time. They are commonly used in databases and file systems due to their efficiency in handling large amounts of data on disk.

Problem Description

Your task is to create a BTree class in JavaScript that supports insertion and search operations. You will need to manage the structure of the B-tree, including splitting nodes when they become full and merging or redistributing keys when nodes become too sparse. For this challenge, we will focus on a simplified version of a B-tree, often referred to as a 2-3-4 tree, where each node can have between 2 to 4 children.

Key Requirements:

1. BTree Class: Create a BTree class with a constructor that takes an order parameter (e.g., 4 for a 2-3-4 tree). This order defines the maximum number of children a node can have.
2. Node Class: Implement a Node class to represent individual nodes in the B-tree. Each Node should store:
   • keys: An array of keys (numbers) stored in sorted order.
   • children: An array of child nodes.
   • isLeaf: A boolean indicating whether the node is a leaf node.
3. insert(key) Method: Implement a method to insert a new key into the B-tree. This method should handle:
   • Finding the appropriate leaf node for insertion.
   • Inserting the key into the leaf node while maintaining sorted order.
   • Node Splitting: If a node becomes full (i.e., has order - 1 keys and order children), it needs to be split. The middle key is promoted to the parent node, and the remaining keys are divided into two new child nodes. This splitting process can propagate upwards if the parent node also becomes full.
4. search(key) Method: Implement a method to search for a given key in the B-tree. This method should efficiently traverse the tree, leveraging the sorted nature of keys within nodes. It should return true if the key is found and false otherwise.

Expected Behavior:

• The B-tree should always maintain its structural properties (balance and key ordering).
• Insertion of a key should result in a valid B-tree structure.
• Searching for an existing key should return true.
• Searching for a non-existent key should return false.

Edge Cases to Consider:

• Inserting into an empty tree.
• Inserting keys that cause multiple node splits.
• Searching for the smallest or largest key in the tree.
• Handling duplicate keys (for this challenge, assume unique keys or decide on a strategy for duplicates, e.g., ignore or allow). We will assume unique keys.

Examples

Example 1:

// Assume order = 4 (2-3-4 tree)
const btree = new BTree(4);
btree.insert(10);
btree.insert(20);
btree.insert(5);
btree.insert(15);
btree.insert(25); // This will cause a split

Expected Tree Structure (Conceptual - root might change):

        [15]
       /    \
     [5,10] [20,25]

Explanation: Initially, keys are inserted into the root. When 25 is inserted, the root [5, 10, 15, 20] becomes full. It splits, promoting 15 to become the new root. 5 and 10 form the left child, and 20 and 25 form the right child.

Example 2:

// Continuing from Example 1
const btree = new BTree(4);
btree.insert(10);
btree.insert(20);
btree.insert(5);
btree.insert(15);
btree.insert(25);
btree.insert(30);
btree.insert(35); // This will cause another split and potentially root split
btree.insert(40);
btree.insert(45);
btree.insert(50);

Expected Tree Structure (Conceptual - after more insertions and splits):

        [25]
       /    \
     [10,15] [35,40]
    /  |  \   /   |   \
 [5] [20] [30] [45] [50]

(Note: The exact structure can vary slightly based on the splitting algorithm, but the B-tree properties should hold. This is one possible valid structure.)

Explanation: As more keys are inserted, nodes will split. For instance, inserting 30 into the node [20, 25] would fill it. If 35 is then inserted and the node [20, 25, 30] is split, 25 is promoted. If the root [15] already has a key, then 25 becomes the new root, and 15 becomes a child. Further insertions like 40, 45, 50 will lead to more splits and potential rebalancing.

Example 3:

const btree = new BTree(4);
btree.insert(10);
btree.insert(20);

console.log(btree.search(15)); // Output: false
console.log(btree.search(10)); // Output: true

Explanation: Searching for a key that does not exist returns false. Searching for an existing key returns true.

Constraints

• The order parameter for the BTree constructor will be an integer greater than or equal to 3.
• Keys to be inserted and searched will be integers.
• The number of keys and operations will not exceed limits that would cause excessive memory usage or extremely long execution times for a typical implementation (assume reasonable limits for typical JavaScript environments).
• The B-tree should be implemented using standard JavaScript features, without relying on external libraries.

Notes

• Consider how you will handle the root node, especially when it splits. The root itself might change.
• The splitting logic is crucial. You'll need a recursive or iterative approach to handle splits that propagate up the tree.
• For insertion, you'll typically traverse down to find the correct leaf, insert, and then handle potential splits on the way back up or through recursion.
• Think about the state of a node when it has order - 1 keys. This means it has order children and is considered "full" for insertion purposes.
• When splitting a node with order - 1 keys, the (order - 1) / 2 (integer division) key is promoted. The keys before this index go to the left child, and keys after go to the right child. The children also need to be distributed correctly.