4.13 Self-test

Why is db_get O(n) but db_set fast, and what single data structure fixes reads without changing the write path?

Name the four problems with an in-memory hash index over a log. Which one does an SSTable's sparse index solve, and how?

Why can't you simply append to an SSTable? Describe the memtable→segment→compaction cycle that resolves this.

What exactly does a Bloom filter guarantee, and what does it not guarantee? Why is a false positive harmless in an LSM engine?

You have a read-heavy workload with a large key space. Size-tiered or leveled compaction, and why?

A B-tree page split crashes halfway. What two forms of corruption can result, and what mechanism prevents them?

Why do SSDs — with no moving parts — still prefer sequential writes? Trace the answer through page size, block size, and GC.

Define write amplification. Give one reason LSM is usually lower and one reason a B-tree can be very high for a small update.

Why can taking a consistent snapshot be nearly free in an LSM engine and expensive in a B-tree?

What's the difference between a clustered index, a heap file, and a covering index? When does updating a heap-file row force every index to be rewritten?

Why are in-memory databases fast? (The answer is not "they avoid disk reads.")

Why does sorting rows improve compression most for the first sort key and barely at all for the fourth?

Why must a column store sort whole rows, never individual columns?

Explain how WHERE product_sk = 30 AND store_sk = 3 is answered with two bitmaps. What property of columnar storage makes the bitwise AND valid?

Contrast query compilation with vectorized processing. Name two CPU characteristics both exploit.

Give one query a data cube answers instantly and one it fundamentally cannot answer. Why?

Why can a concatenated (latitude, longitude) index not answer a map-viewport query? Name two index types that can.

Reframe full-text search as a multidimensional query. What is a postings list, and why can it be a bitmap?

Why don't R-trees work for 1536-dimensional embeddings? Compare flat, IVF, and HNSW on accuracy and speed.