AlgoScope

B-Tree

A wide, shallow search tree tuned for block storage. Nodes hold many keys.

Data structures, data structure, advanced
Split 3 8 15 27 40 around 15.3 8 15 27 40

B-Tree: Four keys per node, fewer splits

Decision, step 7 of 18

3 8 15 27 40 has 5 keys and the limit is 4, so it splits. The middle key, 15, moves up to the parent. The keys below it form the left node and the keys above it the right node.

How b-tree works

Cost

Search
O(log n)
Insert
O(log n)
Delete
O(log n)
Space
O(n)

Height is O(log_t n) for minimum degree t. Disk reads scale with height.

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

B-Tree covers these too, in the same run.