Skip to main content

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
Back to top