关于Google BigTable范围扫描、SST及MemTable的技术疑问

Great questions—these get right to the heart of how BigTable balances write throughput and read efficiency. Let’s break them down one by one:

1. Does BigTable support efficient range scans if SSTables are not globally ordered? #

Nope, you don’t need to scan all SSTables for a range query like SELECT * WHERE id BETWEEN 100 AND 200—here’s why:

• Each SSTable stores metadata about the minimum and maximum primary key it contains. When a range query comes in, the tablet server first filters out any SSTables whose key ranges don’t overlap with your query interval. SSTables that are completely outside the 100-200 range are skipped entirely.
• For the remaining SSTables (those that do overlap with the query range), since each is internally sorted, the server can perform a binary search to jump directly to the first key ≥100, then read sequentially until it hits a key >200.
• Finally, the server merges the sorted results from all relevant SSTables (plus data from the MemTable/Immutable MemTable) using a merge sort-like process. Since each input stream is sorted, this merge is efficient, so the overall range scan performance stays strong.

2. Is your understanding of binary search for single-key queries correct? #

Absolutely! That’s exactly why SSTables are designed to be sorted. When looking up a single primary key:

• BigTable checks the in-memory MemTable first (since it holds the most recent writes), then the Immutable MemTable (a read-only, sorted in-memory structure that’s waiting to be flushed to disk), then the SSTables on disk.
• All of these structures are sorted, so each can use binary search to locate the target key in O(log n) time, avoiding full scans. This makes single-key lookups extremely fast.

3. Is the MemTable sorted, and how does it handle updates? #

Yes, the MemTable is definitely sorted. BigTable uses a skip list to implement it, and here’s why that works so well:

• Skip lists provide O(log n) time complexity for inserts, deletes, and lookups, just like balanced binary trees—but they’re much simpler to implement, especially for concurrent workloads. Since writes to the MemTable are frequent, the simpler concurrency model of skip lists helps maintain high write throughput.
• When the MemTable reaches its memory limit, it’s converted to an Immutable MemTable (read-only, so no more updates), and a new MemTable is created. Later, a background thread flushes the Immutable MemTable to disk as an SSTable: since the skip list is sorted, traversing it produces a stream of key-value pairs in primary key order, which can be written directly to disk as a sorted SSTable. This traversal is O(n) but efficient because it’s a single pass over in-memory data, and the disk write is batch-oriented (which is way faster than random writes).

内容的提问来源于stack exchange，提问作者R Ree