Question bank — Indexing — B-tree index, hash index, full-text

False — an index only helps queries that filter/join/sort on the indexed column(s); an unrelated WHERE other_col = ? still does a full scan, and meanwhile every write got slower.

False — it stores the indexed column value(s) plus a row pointer (or the primary key). The full row lives in the heap or clustered file; a non-clustered index just points to it.

False — see Big-O Notation: ${\log }_{m}N$ is ~5 for a billion rows, a tiny constant, while a hash index cannot do ranges, ORDER BY, or prefix LIKE. B-tree wins for most real workloads.

False — in a B+tree only the leaves hold key→pointer pairs; internal nodes hold only separator keys that route the search downward.

True-ish — on a truly read-only table the write cost vanishes, so only the storage cost remains. On any table that gets writes, though, every INSERT/UPDATE/DELETE must maintain that index.

False — hashing deliberately scatters keys across buckets to spread them evenly; there is no global order to exploit for ranges or sorting.

True — B+tree leaves are stored and linked in sorted order, so the database can walk them sequentially instead of running a separate sort step.

False — a B-tree helps col = 'x' or LIKE 'pre%', but searching inside text (CONTAINS 'x') needs an inverted index mapping word→documents; a B-tree cannot do word-inside-text search.

Wrong — the leftmost-prefix rule: a composite index is sorted by last_name first, so it can't jump to a first_name without knowing the last_name. It helps last_name or both, never first_name alone.

Wrong — a leading wildcard gives no known prefix to start the descent, so the B-tree can't pick a starting leaf → full scan. Only LIKE 'son%' (trailing wildcard) can use the index.

Wrong — hashing destroys order, so adjacent prices land in unrelated buckets. Range queries fall back to a full scan on a hash index; use a B-tree.

Wrong — each index costs storage and must be updated on every write. On write-heavy tables, over-indexing makes the system slower. Index only columns you actually filter/join/sort on.

Wrong — with a B-tree of branching factor ~100, height $h=\lceil {\log }_{100}10^9\rceil \approx 5$, so ~5 disk reads (often 1–2 with top levels cached in RAM). See B+ Tree Data Structure.

Wrong — that's a forward index. Full-text uses an inverted index (word→documents) because the query gives you a word and asks which documents contain it.

Mostly wrong — the real bottleneck is disk I/O. Indexes turn $O(N)$ page reads into $O(\log N)$ or $O(1)$; saving seeks matters far more than saving CPU comparisons.

Because reading one node = one disk seek, and seeks are the expensive part. A wide node means high branching factor $m$, which makes the tree shallow ($h={\log }_{m}N$), so fewer levels = fewer seeks.

The table is stored by insertion/clustering order, not by the searched column. A separate sorted or hashed copy is what lets the database jump straight to matches without scanning.

A natural index maps document→words. We invert it to word→documents because the query hands us the word and wants the documents — matching the query's direction makes lookup a direct jump instead of a scan.

Stemming collapses running/ran/runs→run so one lookup matches all forms; stop-word removal drops the/is which appear everywhere and carry no search value, shrinking postings lists.

B+tree leaves are kept sorted and linked, so you find the start then walk the neighbours. Hashing scatters keys with no relationship between hash(99) and hash(100), so there's no neighbour to walk.

Each level down the tree is one node, and each node is one disk page = one read. You touch one node per level from root to leaf, so cost ≈ height ≈ ${\log }_{m}N$.

Still $O({\log }_{m}N)$ comparisons, but ~0 disk seeks — the "disk read per level" cost collapses because pages are cached. The algorithm's shape is unchanged; only the I/O cost drops.

That bucket degrades toward a list, so lookups in it drift from $O(1)$ toward $O(\text{bucket size})$. Good hash functions and enough buckets keep collisions rare; a bad one erases the $O(1)$ advantage.

Rarely — if a column has only 2–3 distinct values, each value still matches a huge fraction of rows, so the database often prefers a full scan anyway. Low selectivity defeats the index.

No meaningful benefit — scanning 0 or 1 rows is already trivial. The index only pays off once $N$ is large enough that $O(\log N)$ or $O(1)$ beats reading everything.

The plain index on email can't be used — the index stores raw values, not LOWER(...) of them. You need a functional/expression index on LOWER(email) to match.

'app%' has a known prefix, so the tree descends to app and walks the range — index-usable. '%app%' has no starting prefix, so it degenerates to a full scan; use a full-text index instead.

$O({\log }_{m}N+k)$: ${\log }_{m}N$ to find the first match, then $k$ steps walking the linked leaves. Returning many rows is dominated by $k$, not by the tree descent.