indexing
B-tree Indexes
Speed up lookups, range scans, and ordered reads on a column by maintaining a balanced tree of sorted values.
Without an index, finding rows that match a condition means a sequential scan — the database reads every row in the table and checks each one. That is fine for a hundred rows and catastrophic for a hundred million. A B-tree index is the standard structure that turns those linear scans into logarithmic lookups, and it is the default index type in virtually every relational database for good reason: one structure serves equality, ranges, prefixes, and ordering.
A book's alphabetical index — jump straight to "Photosynthesis" instead of reading every page.
Key Concepts
1
A B-tree (balanced tree) keeps the indexed column's values sorted, in a shallow, wide, multi-way tree whose leaf nodes point to the actual row locations. Because it stays balanced, any value is reachable in O(log n) steps — a billion-row table is only a handful of levels deep. The sorted structure is what makes one index so versatile: it answers equality (=), range conditions (<, >, BETWEEN), prefix matches (LIKE 'abc%'), and ORDER BY on the indexed column without a separate sort step, and it can satisfy MIN/MAX by reading an end of the tree. A query that can be answered entirely from the index's columns (a covering index) avoids touching the table at all.
=<>BETWEENLIKE 'abc%'
2
The trade-off that interviews probe is that indexes are not free. Every INSERT, UPDATE, or DELETE must also update each affected index, so over-indexing slows writes and consumes storage. Indexes help selective queries — those returning a small fraction of rows — but the optimiser will rightly ignore an index and scan when a query would return most of the table. And a B-tree cannot help a leading-wildcard search (LIKE '%abc') because the sort order is useless when the prefix is unknown, which is where full-text or trigram indexes come in.
INSERTUPDATEDELETELIKE '%abc'