AlgoScope

2-3-4 Tree

Nodes hold one to three keys. Isomorphic to red-black trees.

Data structures, data structure, advanced
Split 10 20 50 70 around 50.10 20 50 70

B-Tree: A 2-3-4 tree: three keys per node

Decision, step 6 of 18

10 20 50 70 has 4 keys and the limit is 3, so it splits. The middle key, 50, 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)

Before this

Taught by the same lesson

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