Implement B-Tree Delete with Merge and Borrow - The Logger

                      TASK
                    

Implementation

B-Tree deletion is the most complex operation because it must maintain two invariants:

Minimum occupancy: every non-root node must have at least ceil(order/2) - 1 keys
Balance: all leaf nodes remain at the same depth

Delete algorithm:

Find the key in the tree
Delete from leaf: remove the key. If the node still has enough keys, done.
Handle underflow (node has too few keys):
a. Borrow from sibling: if a sibling has more than the minimum keys, rotate through the parent. The sibling gives a key to the parent, and the parent gives its separator key to the deficient node.
b. Merge with sibling: if no sibling can lend, merge the node with a sibling and pull down the parent's separator key. This may cause the parent to underflow (recursion).
Root collapse: if the root has zero keys (because its only two children merged), the merged child becomes the new root.

Request:  {"type": "btree_delete", "msg_id": 1, "key": "user:50"}
Response: {"type": "btree_delete_ok", "in_reply_to": 1, "deleted": true, "rebalance": "none"}

Request:  {"type": "btree_delete", "msg_id": 2, "key": "user:25"}
Response: {"type": "btree_delete_ok", "in_reply_to": 2, "deleted": true, "rebalance": "borrow_from_sibling"}

Request:  {"type": "btree_delete", "msg_id": 3, "key": "user:10"}
Response: {"type": "btree_delete_ok", "in_reply_to": 3, "deleted": true, "rebalance": "merge_with_sibling", "new_depth": 2}

Sample Test Cases

Delete existing key successfullyTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"btree_insert","msg_id":2,"key":"k1","value":"v1"}}
{"src":"c1","dest":"n1","body":{"type":"btree_delete","msg_id":3,"key":"k1"}}
{"src":"c1","dest":"n1","body":{"type":"btree_search","msg_id":4,"key":"k1"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Delete non-existent key returns not foundTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"btree_delete","msg_id":2,"key":"nonexistent"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "btree_delete_ok", "in_reply_to": 2, "deleted": false, "msg_id": 1}}

Hints

Hint 1▾

B-Tree nodes must maintain a minimum number of keys (typically ceil(order/2) - 1)

Hint 2▾

Deletion from a leaf: simply remove the key. If underflow occurs, rebalance.

Hint 3▾

Borrow (rotation): steal a key from a sibling through the parent. Preferred over merging.

Hint 4▾

Merge: if neither sibling can lend a key, merge the node with a sibling and pull down the parent separator key.

Hint 5▾

If the root becomes empty after a merge, the merged child becomes the new root (tree shrinks by 1 level).

Resources

B-Tree Deletion Algorithm

B-Tree deletion with merge, borrow, and root collapse operations explained

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

deleteunderflowmergeborrowrebalancingminimum occupancy

main.py

python