Database storage engines

  • LSM storage engine
  • Page oriented storage engine (B-Tree based)

World’s simplest database

Script:

set(key, value) {    echo "${key},${value}" > test.db}get(key) {    grep "^${key}," test.db | sed -e "s/^${key},//" | tail -n 1}
  • A well-chosen index improves the read performance
  • Every index reduces the write performance.

Hash Index

You want to meet your friend, you know his society name but you forgot the apartment number.

  • Bit cask (default storage engine of Riak DB) uses hash-based indexing.
  • Bit cask offers high-performance reads and writes subjected to all keys fits in available RAM.

Segmentation, Merge, and Compaction

Disk out of space

Problems in real database Implementation

File Format: CSV v/s binary format

  • Writes are faster
  • Concurrency and Crash recovery is better
  • Range-based queries are inefficient
  • The hash-based index should fit in memory

SSTable and LSM

SSTable stands for Sorted String Table.

  • Write to memtable
  • Write to segment
  • Read
  • Crash recovery
  • Merging and compaction are easier: Based on merge sort.
  • Index is sparse
  • Range queries and locality of reference

B-Tree

B Tree is a data structure used for disk access

  • In-place update: Create a new data node and update the pointer.
  • Crash recovery: WAL (write-ahead log)
  • Concurrency: Latch
  • Copy on write
  • Abbreviated key
  • Sequential access
  • Sibling links

B-Tree vs LSM Tree

Thumb Rule

  • LSM tree faster for writes
  • B-Tree faster for the read
  • Faster for the write as append-only.
  • The disk has a limited write capacity.
  • Compaction and merging utilize some writes and hence impact external writes.
  • LSM tree stores multiple copies of the same data.

Analytical processing

Commercial transactions

  • Sale
  • Banking
  • Processing an order
  • Look for a few records and updates based on the user input.
  • Scan over a large number of records read a few fields and calculate aggregates.
  • Fact table: very large
  • Dimension table

Column-oriented database

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store