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

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

B-trees are designed to minimize the height of the tree, which reduces the number of disk accesses required for operations. This is crucial for disk-based storage systems where latency is high and data is accessed in large blocks.

Example

In a database storing millions of records, a B-tree structure allows for quick retrieval of records with minimal disk reads, significantly speeding up query times compared to a binary search tree.

Remember this

Understanding B-trees' efficiency in disk-based storage systems is essential for designing databases and file systems that perform well under heavy read operations.

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

Related concepts

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

LSM trees buffer writes in memory for write-heavy workloads

merge sort: O(n log n) always

Ever wondered why sorting your music library takes ages?

BFS vs DFS: BFS finds shortest path in unweighted graphs, DFS uses less memory

BFS finds shortest path in unweighted graphs; DFS uses less memory

Binary search

How fast can you find a word in a dictionary?

to use random forests: when you want a strong baseline with minimal hyperparameter tuning

Why not always use the best single tree for predictions?

Swipe through 100 ML concepts daily

Open Pocket Polymath