B-Tree
A balanced tree optimized for systems that read and write large blocks of data. Commonly used in databases and file systems.
B-Tree Visualization
Min. degree (t):
SlowFast
🔊 Sound
ReadyEmpty B-Tree (t=3). Insert a value.
Active keyFoundKey cellLeaf marker
empty tree — insert a value
Complexity
Time Complexity:
O(log n)Space Complexity:
O(n)Pseudocode
function search(node, key):
find smallest i such that key <= node.keys[i]
if key == node.keys[i]:
return node
if node is leaf:
return null
return search(node.children[i], key)
function insert(node, key):
if node is full:
split node
insert key into correct child