B-trees optimize: disk-based sorted data with O(log n) reads per query

How can we quickly find your favorite song in a massive music library?

Imagine you're looking for a song in a huge music collection stored on a computer. You want to find it fast without searching through every song one by one.

Think of organizing songs in a way that you can jump directly to the right section of the library. This method quickly narrows down your search area, making it easier to find your song.

Example

If you have 1,024 songs and the library is divided into 32 sections, you can skip to the section that likely contains your song instead of checking each song individually.

Remember this

B-trees help organize data so you can find information quickly, even in large collections.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

merge sort: O(n log n) always

Ever wondered why sorting your music library takes ages?

Matrix (mathematics)

Ever wondered how computers can predict your favorite songs?

O(n log n) is the lower bound for comparison-based sorting

Ever wonder why sorting can't be faster than a certain point?

LSM trees optimize: write-heavy workloads by buffering writes in memory

Ever wondered how your favorite social media app handles millions of new posts every minute?

Quicksort

Can sorting be faster than you think?

Rate-distortion theory: minimum bits to represent data within distortion D

How many bits do we need to perfectly copy a song?

Swipe through 100 ML concepts daily

Open Pocket Polymath