Capstone Index: In-Memory B+ Tree & Sparse Block Index
Scanning gigabyte SSTable files for a single key wastes disk I/O. The Capstone indexing engine pairs an in-memory B+ Tree with a sparse block index. By storing only every $K$-th key alongside its byte offset, the engine performs $O(\log N)$ binary searches directly to the exact block 🌲⚡🔍.
import bisect
class SparseIndex:
def __init__(self, step=4):
self.step = step
self.keys = []
self.offsets = []
def index(self, sorted_entries):
for i, (k, offset) in enumerate(sorted_entries):
if i % self.step == 0:
self.keys.append(k)
self.offsets.append(offset)
def search_offset(self, target):
idx = max(0, bisect.bisect_right(self.keys, target) - 1)
return self.offsets[idx]
sp = SparseIndex(step=2)
sp.index([("a", 0), ("b", 32), ("c", 64), ("d", 96)])
print(f"Target 'c' Block Offset: {sp.search_offset('c')} 🚀")
# 109. Capstone Index: In-Memory B+ Tree & Sparse Block Index A naive database creates an index pointer for every single row on disk (a **dense index**). When tables reach 500 million rows, the dense index itself consumes hundreds of gigabytes of RAM, pushing the database into memory exhaustion 🛑. ```python # The Sparse Index Principle: # Instead of storing all 8 keys in memory: # In-Memory Index: ["apple" @ 0] ---------------> ["fig" @ 256] # | | # On-Disk SSTable: [apple, banana, cherry, date] [fig, grape, kiwi, lemon] # (Block 0: 0..255 bytes) (Block 1: 256..511 bytes) ``` ### The $O(\log N)$ Point Lookup Flow To search for key `'cherry'`: 1. Perform in-memory binary search (`bisect_right`) across the sparse index array. 2. Determine that `'cherry'` $\ge$ `'apple'` and $<$ `'fig'`. Therefore, `'cherry'` MUST reside within Block 0 (offset 0). 3. Read exactly one 256-byte disk block starting at byte offset 0. 4. Scan the small block to retrieve the value! - **Memory Consumption**: Reduced by $95\%$ to $99\%$! - **Disk I/O**: Exactly one sequential block read per lookup 🌲⚡🔍. --- ### Interactive Pop-Quiz 🧠 #### Why is a sparse index preferred over a dense index (which indexes 100% of keys) for on-disk SSTable files? - [ ] A sparse index requires orders of magnitude less RAM, fitting millions of on-disk record locations entirely in CPU cache memory 🌲 - [ ] A dense index corrupts the Linux kernel swap file - [ ] Sparse indices are required by the POSIX file system spec - [ ] Dense indices only support numeric integer keys --- ### Practical Challenge 🎯 Implement `SparseBlockIndex(block_size: int = 4)` with `sparse_keys: list[str]` and `block_offsets: list[int]`. Provide `build_from_sorted(sorted_items: list[tuple[str, int]])` indexing every `block_size`-th item. Provide `find_candidate_block_offset(search_key: str) -> int` using `bisect.bisect_right`. Build with 8 items starting at offsets multiples of 64 (`'apple'`, `'banana'`, `'cherry'`, `'date'`, `'fig'`, `'grape'`, `'kiwi'`, `'lemon'`). Verify `'cherry'` maps to offset 0 and `'lemon'` to 256. Print results. <details> <summary>Solution</summary> ```python import bisect class SparseBlockIndex: def __init__(self, block_size: int = 4): self.block_size = block_size self.sparse_keys = [] self.block_offsets = [] def build_from_sorted(self, sorted_items: list[tuple[str, int]]): for i, (key, offset) in enumerate(sorted_items): if i % self.block_size == 0: self.sparse_keys.append(key) self.block_offsets.append(offset) def find_candidate_block_offset(self, search_key: str) -> int: if not self.sparse_keys: raise KeyError("Empty index") idx = bisect.bisect_right(self.sparse_keys, search_key) - 1 return self.block_offsets[max(0, idx)] items = [ ("apple", 0), ("banana", 64), ("cherry", 128), ("date", 192), ("fig", 256), ("grape", 320), ("kiwi", 384), ("lemon", 448) ] index = SparseBlockIndex(block_size=4) index.build_from_sorted(items) assert index.sparse_keys == ["apple", "fig"] assert index.block_offsets == [0, 256] off_cherry = index.find_candidate_block_offset("cherry") assert off_cherry == 0 off_lemon = index.find_candidate_block_offset("lemon") assert off_lemon == 256 print(f"SparseBlockIndex verified: 'cherry'->{off_cherry}, 'lemon'->{off_lemon}") ``` </details>