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

Global Index vs Local Index

• Global index is like sharding, where you put relevant data together in the same node, and create an index to reference all nodes in the cluster
  • weak for "hot spot", but optimize for read because data locality
• Local index: data are sharded, but distributed more evenly. Each shard has its own index. Optimize for write, but in order to get a range query, all nodes needs to be queried