TASK
Implementation
Implement a B-Tree index supporting both point and range queries:
- Internal nodes contain keys and child pointers
- Leaf nodes contain keys and data pointers
- Insert splits full nodes
- All leaves at same depth (balanced)
B-Trees minimize disk I/O with high fanout - each read returns many keys.
Sample Test Cases
B-Tree insert and searchTimeout: 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":"foo","value":100}}
{"src":"c2","dest":"n1","body":{"type":"btree_search","msg_id":3,"key":"foo"}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c1","body":{"type":"btree_insert_ok","in_reply_to":2,"msg_id":1}}
{"src":"n1","dest":"c2","body":{"type":"btree_search_ok","in_reply_to":3,"msg_id":2,"found":true,"value":100}}
Hints
Hint 1▾
Nodes contain multiple keys
Hint 2▾
Keep tree balanced for O(log n)
Hint 3▾
Handle node splits on insert
OVERVIEW
Theoretical Hub
B-Trees
B-Trees are optimized for storage systems. Each node contains many keys (high fanout), reducing tree height. A tree with millions of keys might be only 3-4 levels deep, requiring 3-4 disk reads for any lookup.
B-Tree vs B+Tree
In a B+Tree (most common in databases), all data lives in leaves, and leaves are linked for efficient range scans. Internal nodes contain only keys for routing.
Key Concepts
B-treebalanced treerange queries
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
class BTreeNode:
def __init__(self, leaf=True, order=4):
self.keys = []
self.values = []
self.children = []
self.leaf = leaf
self.order = order
def is_full(self):
return len(self.keys) >= self.order - 1
class BTree:
def __init__(self, order=4):
self.root = BTreeNode(order=order)
self.order = order
def search(self, node, key):
# TODO: Find key in tree
pass
def insert(self, key, value):
# TODO: Insert with splits
pass
def _split_child(self, parent, index):
# TODO: Split full child node
pass
def range_query(self, start, end):
# TODO: Return all keys in range
pass
if __name__ == "__main__":
tree = BTree(order=4)
for i in range(10):
tree.insert(i, f"value_{i}")