The main thing to learn about btrees is that they have very high branching to ensure shallowness and thus trade off more sequential accesses for fewer random ac

The main thing to learn about btrees is that they have very high branching to ensure shallowness and thus trade off more sequential accesses for fewer random accesses, a good tradeoff for disk I/O. The other thing is to recognise that sorted access is still better than random access even over an index; better for disk / block cache, better for CPU cache, and seemingly redundant sorts can e.g. have outsize constant factor performance wins for some joins over materialized subtable queries.