References — SSTable Format

Papers

• O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. "The Log-Structured Merge-Tree (LSM-Tree)." Acta Informatica 33(4), 1996. — Original description of the immutable run / multi-level merge architecture.
• Chang, F. et al. "Bigtable: A Distributed Storage System for Structured Data." OSDI 2006. — Introduces the SSTable term and the blocks-plus-index layout this lab mirrors.

Open-source implementations

• LevelDB table/format.h, table/table_builder.cc, table/block_builder.cc, table/block.cc — canonical reference for this lab. The data block format here is the LevelDB block format with restart-point compression removed for clarity.
• RocksDB table/block_based/block_based_table_builder.cc — adds bloom-filter blocks, compression, and partitioned indices on top of the same skeleton.
• CockroachDB Pebble sstable/writer.go and sstable/reader.go — Go implementation in idiomatic style.

Articles

• LevelDB design doc: https://github.com/google/leveldb/blob/main/doc/table_format.md
• RocksDB BlockBasedTable: https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format
• "Building an LSM Storage Engine: SSTables" — Mini-LSM tutorial, Chen et al.: https://skyzh.github.io/mini-lsm/