Gauntlet 08: B-Tree Index with Range Scans
Hash maps provide O(1) point lookups but fail completely at range queries (WHERE age BETWEEN 20 AND 30). A B-Tree index maintains keys in sorted order, providing O(log N) point searches and O(log N + K) contiguous range scans across key sequences.
import bisect
# Binary search index lookup:
idx = bisect.bisect_left(sorted_keys, search_key)
# Gauntlet 08: B-Tree Index with Range Scans Why does PostgreSQL create B-Tree indexes by default instead of Hash indexes? If you query `SELECT * FROM users WHERE id = 42`, a hash table does it in $O(1)$. But what happens when you query: ```sql SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31' ORDER BY created_at; ``` A hash table is completely useless. It has to scan all 10,000,000 records. 🌲📈 A **B-Tree Index** maintains keys in strictly sorted order. Finding the first matching key takes $O(\log N)$ binary search time, and scanning through the subsequent range takes $O(K)$ sequential pointer iterations. In this gauntlet build, you will implement an ordered search index supporting point lookups and sorted range scans. ```python import bisect # Finding start and end boundaries: start_idx = bisect.bisect_left(keys, start_key) end_idx = bisect.bisect_right(keys, end_key) ``` ## Pop Quiz Why do relational database indexes use B-Trees instead of hash tables for indexed columns? - [ ] B-Trees keep keys sorted, enabling efficient range scans, ORDER BY sorting, and prefix queries. - [ ] Hash tables consume 100x more memory than B-Trees. - [ ] B-Trees prevent disk sectors from fragmenting on magnetic hard drives. - [ ] Because hash tables cannot store numerical floating-point values. ## Real-World Challenge Implement `BTreeIndex`: - `insert(key, value)`: Inserts or updates the key while keeping internal elements strictly sorted. - `get(key) -> value | None`: Binary search retrieval in $O(\log N)$ time. - `range_scan(start_key, end_key) -> list[tuple]`: Returns all `(key, value)` pairs where $\text{start\_key} \le \text{key} \le \text{end\_key}$ in ascending sorted order. <details> <summary>Solution</summary> ```python import bisect class BTreeIndex: def __init__(self): self._keys = [] self._values = [] def insert(self, key, value): idx = bisect.bisect_left(self._keys, key) if idx < len(self._keys) and self._keys[idx] == key: # Overwrite existing key value self._values[idx] = value else: # Maintain sorted order self._keys.insert(idx, key) self._values.insert(idx, value) def get(self, key): idx = bisect.bisect_left(self._keys, key) if idx < len(self._keys) and self._keys[idx] == key: return self._values[idx] return None def range_scan(self, start_key, end_key) -> list[tuple]: start_idx = bisect.bisect_left(self._keys, start_key) end_idx = bisect.bisect_right(self._keys, end_key) matched_keys = self._keys[start_idx:end_idx] matched_values = self._values[start_idx:end_idx] return list(zip(matched_keys, matched_values)) # Verification index = BTreeIndex() # Insert unsorted keys items = [(50, "Order 50"), (10, "Order 10"), (90, "Order 90"), (30, "Order 30"), (70, "Order 70")] for k, v in items: index.insert(k, v) # Point lookups assert index.get(30) == "Order 30" assert index.get(999) is None # Overwrite index.insert(30, "Order 30 Updated") assert index.get(30) == "Order 30 Updated" # Range scan [20, 75] -> should return keys 30, 50, 70 in sorted order scan_results = index.range_scan(20, 75) assert scan_results == [ (30, "Order 30 Updated"), (50, "Order 50"), (70, "Order 70") ] ``` </details>