Database Comparisons

SQL Databases

• Uses B Tree or B+ Tree indexing, where B+ Tree is more common
• Fast reads but slow writes

NoSQL Database

• Some uses B Tree (mongoDB)
• Mostly uses LSM Tree (Memtable + SSTable)
  • Memtable is a balanced binary search tree in memory
• Fast writes to memory
• Search is slow because it may have to search many SSTables for the target key. Each SSTable requires O(Log(n)) to search (binary search because each SSTable is sorted), and O(n) for all the SSTables

What is secondary indexes?

• additional index on top of the primary index

What is 2 phase locking?

• Two phases
  • Growing Phase: the transaction acquires all the necessary locks on data items it needs to access
  • Shrinking Phase: the transaction holds all acquired locks and begins releasing htem
• distributed transactions
• It prevents data anomalies like dirty reads, lost updates, and phantom reads
• but it may lead to deadlocks

What is partitioning and what is sharding?

• partitioning: divide a table into subsets within the same node

• sharding: divide a database into multiple nodes

  • geo-based sharding
  • range-based sharding
  • hash-based sharding

• Sharding is a more advanced and distributed form of horizontal partitioning