AlgoScope

B+ Tree

A B-tree where all values live in linked leaves, making range scans sequential.

Data structures, data structure, advanced
Split 10 20 30 around 20.10 20 30

B-Tree: B+ tree: keys stay in the chained leaves

Decision, step 5 of 23

10 20 30 has 3 keys and the limit is 2, so it splits. The middle key, 20, is copied up to the parent and stays in the right leaf. 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)
Range scan
O(log n + k)
Insert
O(log n)
Space
O(n)

Before this

Taught by the same lesson

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