Database Indexes

B-Tree Index

• Pros:
  • fast read, fast range query
  • no limit on number of keys
• Cons:
  • slow writes

Hash Index

• Pros:
  • O(1) read and write
• Cons:
  • keys needs to fit in memory
  • no range queries allowed

LSM Tree Index

• Red-black tree, balanced binary tree, etc
• WAL for memtable
• Sparse index for SSTable to speed up read (an index to the SSTable)
• bloom filter
• Pros:
  • fast writes to memory
  • supports range queries
• Cons:
  • supports range queries but slow compared to b-trees