In-memory data structure that holds data before it’s flushed into an SStable, the implementation may use a RB Tree, a skiplist, a HashLinkList


An immutable data structure that stores a large number of key:value pairs sorted by key

Advantages over simple hash indexes

  • Merging SSTables is similar to doing a merge sort
  • To find if a key exists we don’t need an index of all the keys in memory, instead we can keep an index for every few kilobytes and then perform a scan (sparse index)
  • range queries can be compressed before writing to disk, the sparse index would only need to find the starting position of the compressed segment