When you run a query like this:

SELECT * FROM users WHERE id = 42

the database can avoid scanning the whole table if it has a useful index. It searches the index, follows a small number of page pointers, and lands close to the row it needs.

For ordinary relational database indexes, that access path is commonly built on a B-tree or a close variant such as a B+ tree.

B-trees work well because of their shape: a shallow, sorted tree whose nodes are sized around storage pages. The design fits data that is too large to treat as one in-memory structure.

A binary search tree is a good teaching data structure, but it is a poor model for database storage. A balanced binary tree with a billion keys may have around 30 levels. If each level requires a separate page read, the latency is unacceptable. A B-tree node can hold hundreds of keys, so the same index may be only 3 or 4 levels deep.

A B-tree spends a little CPU searching inside a page to avoid many expensive page reads.