B+ Trees

The database index. Every record lives in a leaf, the leaves are linked, and a range query walks sideways instead of climbing back up the tree.

Order 4

Records in leaves only

Linked leaf chain

Range scan: O(log n + k)

Keys to insert, in order

Range scan

–

Speed: 1000ms

Step 1 of 0—

visitingsplittingin range scanmatched key

Click Play to begin

Search:O(log n)

Insert:O(log n)

Range of k:O(log n + k)

Space:O(n)

Question 1 of 3

In a B+ tree, where do the actual records live?

Indexing

Hashing your keys…

DSAverse