Kleppman ch. 3 -- Storage and Retrieval

Chapter 3 of (Kleppman) Designing Data-Intensive Systems

• Database log (124)
• Database indexes
  • Read-write tradeoff (124-5)
  • Hash index (125)
• Log compaction (128-9)
• Tombstone (data stores) (129)
• Sorted string table (SSTable) (131-5)
• Memtable (134)
• Log-structured merge-tree (LSM-Tree) (135)
• Algorithms
  • Bloom filter
  • Red-black tree
  • Trie
• B-Tree (137-141)
  • Branching factor (139)
  • Write-ahead log (WAL, “redo log”) (141)
  • Latches (141)
• Copy-on-write vs copy-on-read (141)
• B-tree vs LSM-tree (142-146)
• Database indexes (146) <— main distinction is uniqueness
• Concatenated index (149)
• In-memory database
  • memcache (151)
  • In-memory relational database (151)
    • eg VoltDB, MemSQL, Oracle TimesTen
  • Anti-caching
• OLTP vs OLAP (155)
• Data warehouse (156)
• Redshift
• Star schema (aka dimensional modeling) (158-162)
  • Fact table
  • Dimension table
• Columnar database
  • Column compression (164)
  • Bitmap encoding (165)
  • Sort ordering considerations (168-170)
• Materialized aggregate (171)
  • Materialized view
  • Data cube (OLAP cube)